-- Hask 范畴中的组合和单位元
-- 态射：函数
f :: Int -> String   -- 从 Int 对象到 String 对象的态射
g :: String -> Bool  -- 从 String 对象到 Bool 对象的态射

-- 组合：函数组合
g . f :: Int -> Bool

-- 单位元
id :: a -> a

-- 结合律
h . (g . f) ≡ (h . g) . f

-- 单位元律
id . f ≡ f
f . id ≡ f

// 组合满足结合律
const f = x => x + 1;
const g = x => x * 2;
const h = x => x - 3;

const compose = (...fns) => x => fns.reduceRight((acc, fn) => fn(acc), x);

// 结合律
compose(h, compose(g, f))(5) === compose(compose(h, g), f)(5);  // true

// 单位元
const id = x => x;
compose(id, f)(5) === compose(f, id)(5) === f(5);  // true

-- 在 Hask 范畴中，endofunctor 将 Hask 映射到自身
class Functor f where
  fmap :: (a -> b) -> f a -> f b

-- 定律
fmap id      ≡ id           -- 保持单位元
fmap (g . h) ≡ fmap g . fmap h  -- 保持组合

-- Maybe 函子
-- 对象映射: a → Maybe a
-- 态射映射: (a → b) → (Maybe a → Maybe b)
instance Functor Maybe where
  fmap _ Nothing  = Nothing
  fmap f (Just a) = Just (f a)

// Functor 定律验证
const Maybe = {
  of: x => ({ type: 'Just', value: x }),
  nothing: () => ({ type: 'Nothing' }),
  map: (fn, m) => m.type === 'Nothing' ? m : Maybe.of(fn(m.value)),
};

const id = x => x;
const f = x => x + 1;
const g = x => x * 2;

// 定律 1: fmap id ≡ id
assert.deepEqual(Maybe.map(id, Maybe.of(5)), Maybe.of(5));

// 定律 2: fmap (g . f) ≡ fmap g . fmap f
const m = Maybe.of(5);
assert.deepEqual(
  Maybe.map(x => g(f(x)), m),
  Maybe.map(g, Maybe.map(f, m))
);

-- 自然变换的类型签名
-- ∀ f. Functor f => f a -> g a
-- 必须对所有 a 成立，不关心 f 的内部结构

-- 从 Maybe 到列表的自然变换
maybeToList :: Maybe a -> [a]
maybeToList Nothing  = []
maybeToList (Just x) = [x]

-- 从 Maybe 到 Either 的自然变换
maybeToEither :: Maybe a -> Either () a
maybeToEither Nothing  = Left ()
maybeToEither (Just x) = Right x

-- 自然性条件验证
-- maybeToList . fmap f ≡ fmap f . maybeToList
-- 对于任何 f 都成立

// 自然变换：Maybe → Array
const maybeToArray = (m) =>
  m.type === 'Nothing' ? [] : [m.value];

// 验证自然性：maybeToArray . map(f) = map(f) . maybeToArray
const f = x => x * 2;
const m = Maybe.of(5);

// 两种路径等价
const path1 = maybeToArray(Maybe.map(f, m));   // [10]
const path2 = maybeToArray(m).map(f);           // [10]
assert.deepEqual(path1, path2);  // 成立

-- 函数组合的结合律
-- (h . g) . f  ≡  h . (g . f)

-- 实际验证
let f = (+1)
let g = (*2)
let h = (^3)

((h . g) . f) 3 == h . (g . f) $ 3  -- True

-- 在 Functor 中
fmap (h . g . fmap f) ≡ fmap h . fmap g . fmap (fmap f)

-- Monad 是自函子范畴上的幺半群
-- 这句话的含义：

-- 1. "自函子"：Functor (Hask → Hask)
--    Monad 的 kind 是 (* -> *)
--    它将类型映射到类型

-- 2. "幺半群"：有单位元和结合律的代数结构
--    单位元：return :: a -> m a
--    结合：  (>>=) :: m a -> (a -> m b) -> m b

-- 3. "范畴上"：在自函子范畴中
--    对象：Functor（如 Maybe, [], IO, Either e）
--    态射：Natural Transformation
--    组合：Monad 组合（通过 Kleisli 范畴）

-- Kleisli 范畴
-- 对象：类型
-- 态射：a → m b（Kleisli 箭头）
-- 组合：(>=>) :: (a -> m b) -> (b -> m c) -> (a -> m c)
-- 单位元：return

(>=>) :: Monad m => (a -> m b) -> (b -> m c) -> (a -> m c)
f >=> g = \x -> f x >>= g

-- 定律
return >=> f  ≡  f
f >=> return  ≡  f
(f >=> g) >=> h  ≡  f >=> (g >=> h)

// Kleisli 组合
const kleisliCompose = (f, g) => x => f(x).flatMap(g);

// Maybe 的 Kleisli 组合
const safeSqrt = x => x >= 0 ? Maybe.of(Math.sqrt(x)) : Maybe.nothing();
const safeDiv = a => b => b === 0 ? Maybe.nothing() : Maybe.of(a / b);

const sqrtOfDiv = kleisliCompose(safeDiv(100), safeSqrt);
sqrtOfDiv(4);   // Maybe(5)
sqrtOfDiv(-1);  // Nothing（除法结果为负数）
sqrtOfDiv(0);   // Nothing（除以零）

class Semigroup a where
  (<>) :: a -> a -> a
  -- 满足结合律：(a <> b) <> c == a <> (b <> c)

-- 实例
instance Semigroup [a] where
  (<>) = (++)  -- 列表连接

instance Semigroup Int where
  (<>) = (+)   -- 加法（或 *）

instance Semigroup String where
  (<>) = (++)

class Semigroup a => Monoid a where
  mempty :: a
  -- 满足单位元律：
  -- mempty <> x == x
  -- x <> mempty == x

instance Monoid [a] where
  mempty = []

instance Monoid Int where
  mempty = 0   -- 加法单位元

-- 使用
mconcat :: Monoid m => [m] -> m
mconcat = foldr (<>) mempty

mconcat [[1,2], [3,4], [5,6]]  -- [1,2,3,4,5,6]

trait Semigroup {
    fn combine(self, other: Self) -> Self;
}

trait Monoid: Semigroup {
    fn empty() -> Self;
}

impl Semigroup for String {
    fn combine(mut self, other: Self) -> Self {
        self.push_str(&other);
        self
    }
}

impl Monoid for String {
    fn empty() -> Self { String::new() }
}

// MapReduce = Functor Map + Monoid Reduce
const mapReduce = (mapFn, reduceFn, empty) => (data) =>
  data.map(mapFn).reduce(reduceFn, empty);

// 单词计数
const wordCount = mapReduce(
  line => line.split(' ').reduce((acc, word) => ({ ...acc, [word]: 1 }), {}),
  (a, b) => Object.entries(b).reduce((acc, [k, v]) => ({ ...acc, [k]: (acc[k] || 0) + v }), a),
  {}
);