class Functor f where
  fmap :: (a -> b) -> f a -> f b

-- 等价于 JavaScript 的 .map()

-- Maybe Functor
instance Functor Maybe where
  fmap _ Nothing  = Nothing
  fmap f (Just x) = Just (f x)

fmap (+1) (Just 5)    -- Just 6
fmap (+1) Nothing     -- Nothing

-- List Functor
instance Functor [] where
  fmap = map

fmap (*2) [1, 2, 3]   -- [2, 4, 6]

-- Either Functor
instance Functor (Either a) where
  fmap _ (Left x)  = Left x
  fmap f (Right x) = Right (f x)

fmap (+1) (Right 5)   -- Right 6
fmap (+1) (Left "err") -- Left "err"

-- IO Functor
instance Functor IO where
  fmap f action = do
    result <- action
    return (f result)

// 手写 Maybe Functor
class Maybe {
  constructor(value) { this.value = value; }
  static of(value) { return new Maybe(value); }
  static nothing() { return new Maybe(null); }

  isNothing() { return this.value === null || this.value === undefined; }

  map(fn) {
    return this.isNothing() ? this : Maybe.of(fn(this.value));
  }
}

Maybe.of(5).map(x => x + 1).map(x => x * 2);  // Maybe(12)
Maybe.nothing().map(x => x + 1);               // Maybe(null)

// Array 是 Functor（内置 .map）
[1, 2, 3].map(x => x * 2);  // [2, 4, 6]

// Promise 是 Functor（.then 就是 map）
Promise.resolve(5).then(x => x + 1).then(x => x * 2);

// Option 是 Functor
let x: Option<i32> = Some(5);
let y = x.map(|v| v + 1);  // Some(6)

let x: Option<i32> = None;
let y = x.map(|v| v + 1);  // None

// Result 是 Functor
let x: Result<i32, &str> = Ok(5);
let y = x.map(|v| v + 1);  // Ok(6)

// Iterator 是 Functor
let v: Vec<i32> = vec![1, 2, 3].iter().map(|x| x * 2).collect();

class Functor f => Applicative f where
  pure  :: a -> f a                    -- 将值放入容器
  (<*>) :: f (a -> b) -> f a -> f b   -- 在容器中应用函数

-- Maybe Applicative
instance Applicative Maybe where
  pure = Just
  Nothing <*> _ = Nothing
  (Just f) <*> something = fmap f something

-- 应用多参数函数
pure (+) <*> Just 3 <*> Just 5    -- Just 8
pure (+) <*> Nothing <*> Just 5   -- Nothing

-- 实用场景：验证
validateUser :: String -> String -> Maybe User
validateUser name email = User <$> validateName name <*> validateEmail email

-- List Applicative
pure (+) <*> [1, 2] <*> [10, 20]  -- [11, 21, 12, 22]

// Maybe Applicative
class Maybe {
  // ... 之前的代码 ...

  ap(maybeFn) {
    if (this.isNothing() || maybeFn.isNothing()) return Maybe.nothing();
    return Maybe.of(maybeFn.value(this.value));
  }
}

// 使用
const add = (a) => (b) => a + b;
Maybe.of(5).ap(Maybe.of(add).ap(Maybe.of(3)));  // Maybe(8)

// 更实用：lift2
const lift2 = (fn, ma, mb) =>
  ma.map(fn).ap(mb);

lift2((a, b) => a + b, Maybe.of(3), Maybe.of(5));  // Maybe(8)

class Applicative m => Monad m where
  return :: a -> m a            -- 同 pure
  (>>=)  :: m a -> (a -> m b) -> m b  -- bind/flatMap

  -- 等价定义
  join :: m (m a) -> m a        -- 展平嵌套的 Monad

-- Maybe Monad：优雅处理可能失败的计算
instance Monad Maybe where
  return = Just
  Nothing >>= _ = Nothing
  Just x  >>= f = f x

-- 使用 do notation
safeDivide :: Double -> Double -> Maybe Double
safeDivide _ 0 = Nothing
safeDivide a b = Just (a / b)

calculation :: Double -> Maybe Double
calculation x = do
  a <- safeDivide x 2      -- 如果除以 0 返回 Nothing
  b <- safeDivide a 3      -- 链式可能失败的计算
  c <- safeDivide b 4
  return (c + 10)          -- 所有步骤都成功才计算

-- calculation 24  → Just 11
-- calculation 0   → Just 10 (0/2=0, 0/3=0, 0/4=0, 0+10=10)
-- 但 safeDivide 0 0 → Nothing

// Maybe Monad
class Maybe {
  static of(value) { return new Just(value); }
  static nothing() { return new Nothing(); }
}

class Just extends Maybe {
  constructor(value) { super(); this.value = value; }
  map(fn) { return Maybe.of(fn(this.value)); }
  flatMap(fn) { return fn(this.value); }  // 这就是 bind/>>=
  ap(m) { return this.isNothing() ? m : m.map(this.value); }
  isNothing() { return false; }
  toString() { return `Just(${this.value})`; }
}

class Nothing extends Maybe {
  map(fn) { return this; }
  flatMap(fn) { return this; }
  ap(m) { return this; }
  isNothing() { return true; }
  toString() { return 'Nothing'; }
}

// 使用 flatMap 链式可能失败的计算
const safeDivide = (a, b) => b === 0 ? Maybe.nothing() : Maybe.of(a / b);

const calculation = (x) =>
  safeDivide(x, 2).flatMap(a =>
    safeDivide(a, 3).flatMap(b =>
      safeDivide(b, 4).map(c => c + 10)
    )
  );

calculation(24);  // Just(11)
calculation(0);   // Just(10)

// Option 就是 Maybe Monad
fn calculation(x: f64) -> Option<f64> {
    let a = safe_divide(x, 2.0)?;
    let b = safe_divide(a, 3.0)?;
    let c = safe_divide(b, 4.0)?;
    Some(c + 10.0)
}

fn safe_divide(a: f64, b: f64) -> Option<f64> {
    if b == 0.0 { None } else { Some(a / b) }
}

// ? 运算符就是 flatMap/bind 的语法糖

from typing import TypeVar, Generic, Callable, Optional

T = TypeVar('T')
U = TypeVar('U')

class Maybe(Generic[T]):
    @staticmethod
    def of(value: T) -> 'Maybe[T]':
        return Just(value)

    @staticmethod
    def nothing() -> 'Maybe[T]':
        return Nothing()

    def flat_map(self, fn: Callable[[T], 'Maybe[U]']) -> 'Maybe[U]':
        raise NotImplementedError

class Just(Maybe[T]):
    def __init__(self, value: T):
        self.value = value

    def flat_map(self, fn):
        return fn(self.value)

    def __repr__(self):
        return f"Just({self.value})"

class Nothing(Maybe[T]):
    def flat_map(self, fn):
        return self

    def __repr__(self):
        return "Nothing"

# 使用
def safe_divide(a, b):
    return Maybe.nothing() if b == 0 else Maybe.of(a / b)

result = (safe_divide(24, 2)
    .flat_map(lambda a: safe_divide(a, 3))
    .flat_map(lambda b: safe_divide(b, 4)))
# Just(2.0)

data Either a b = Left a | Right b

instance Functor (Either a) where
  fmap _ (Left x)  = Left x
  fmap f (Right x) = Right (f x)

instance Monad (Either a) where
  return = Right
  Left x  >>= _ = Left x
  Right x >>= f = f x

-- 使用：带错误信息的计算
safeDivide :: String -> Double -> Double -> Either String Double
safeDivide _ _ 0 = Left "Division by zero"
safeDivide _ a b = Right (a / b)

calculation :: Double -> Either String Double
calculation x = do
  a <- safeDivide "step 1" x 2
  b <- safeDivide "step 2" a 3
  c <- safeDivide "step 3" b 4
  return (c + 10)

-- calculation 24 → Right 11.0
-- calculation 0  → Right 10.0

class Left {
  constructor(value) { this.value = value; }
  map(fn) { return this; }
  flatMap(fn) { return this; }
  fold(fnL, fnR) { return fnL(this.value); }
  toString() { return `Left(${this.value})`; }
}

class Right {
  constructor(value) { this.value = value; }
  map(fn) { return new Right(fn(this.value)); }
  flatMap(fn) { return fn(this.value); }
  fold(fnL, fnR) { return fnR(this.value); }
  toString() { return `Right(${this.value})`; }
}

const either = { left: (v) => new Left(v), right: (v) => new Right(v) };

// 使用
const safeDivide = (a, b) =>
  b === 0 ? either.left('Division by zero') : either.right(a / b);

const result = safeDivide(10, 2)
  .flatMap(a => safeDivide(a, 3))
  .fold(
    err => `Error: ${err}`,
    val => `Result: ${val}`
  );
// "Result: 1.666..."

-- IO 是一个描述副作用的数据类型，不是直接执行
-- 类型签名告诉你这个操作有副作用
getLine :: IO String           -- 读取一行（有副作用）
putStrLn :: String -> IO ()    -- 打印一行（有副作用）

-- IO Monad 的 bind 将 IO 操作串联起来
greet :: IO ()
greet = do
  name <- getLine            -- IO String → String
  putStrLn ("Hello, " ++ name)  -- IO ()

// IO Monad：延迟执行副作用
class IO {
  constructor(effect) {
    this.effect = effect;  // 存储但不执行
  }

  static of(value) {
    return new IO(() => value);
  }

  map(fn) {
    return new IO(() => fn(this.effect()));
  }

  flatMap(fn) {
    return new IO(() => fn(this.effect()).effect());
  }

  run() {
    return this.effect();
  }
}

// 使用
const readEnv = (key) => new IO(() => process.env[key]);
const writeLog = (msg) => new IO(() => { console.log(msg); return msg; });

const program = readEnv('USER')
  .flatMap(user => writeLog(`Hello, ${user}`));

// 纯函数代码——直到调用 run() 才执行副作用
program.run();

newtype State s a = State { runState :: s -> (a, s) }

instance Functor (State s) where
  fmap f (State g) = State $ \s -> let (a, s') = g s in (f a, s')

instance Monad (State s) where
  return a = State $ \s -> (a, s)
  (State g) >>= f = State $ \s ->
    let (a, s') = g s
    in runState (f a) s'

get :: State s s
get = State $ \s -> (s, s)

put :: s -> State s ()
put s = State $ \_ -> ((), s)

modify :: (s -> s) -> State s ()
modify f = State $ \s -> ((), f s)

class State {
  constructor(runState) {
    this.runState = runState;
  }

  static of(value) {
    return new State(state => [value, state]);
  }

  static get() {
    return new State(state => [state, state]);
  }

  static put(newState) {
    return new State(() => [undefined, newState]);
  }

  map(fn) {
    return new State(state => {
      const [value, newState] = this.runState(state);
      return [fn(value), newState];
    });
  }

  flatMap(fn) {
    return new State(state => {
      const [value, newState] = this.runState(state);
      return fn(value).runState(newState);
    });
  }
}

// 使用示例：栈操作
const push = (x) => State.get().flatMap(stack =>
  State.put([...stack, x]).map(() => x)
);

const pop = () => State.get().flatMap(stack => {
  const [top, ...rest] = stack;
  return State.put(rest).map(() => top);
});

const stackProgram = push(1)
  .flatMap(() => push(2))
  .flatMap(() => push(3))
  .flatMap(() => pop());

const [result, finalState] = stackProgram.runState([]);
// result = 3, finalState = [1, 2]

-- 组合 Maybe 和 IO
type App a = MaybeT IO a

liftIO :: IO a -> App a
liftIO = lift

-- 使用
app :: App Int
app = do
  input <- liftIO getLine
  case readMaybe input of
    Nothing -> MaybeT (return Nothing)
    Just n  -> return (n * 2)

-- do notation 是 >>= 的语法糖
do
  x <- action1
  y <- action2 x
  return (x + y)

-- 等价于
action1 >>= \x ->
  action2 x >>= \y ->
    return (x + y)

// async/await 就是 Promise monad 的 do notation
async function program() {
  const user = await getUser();        // flatMap
  const posts = await getPosts(user);  // flatMap
  const comments = await getComments(posts[0]); // flatMap
  return comments.length;
}

// 等价于
function program() {
  return getUser()
    .then(user => getPosts(user))
    .then(posts => getComments(posts[0]))
    .then(comments => comments.length);
}

// 使用 Either 进行表单验证
const validate = (validators) => (input) =>
  validators.reduce(
    (result, validator) => result.flatMap(
      valid => validator(input).map(v => [...valid, v])
    ),
    either.right([])
  );

const validateEmail = (input) =>
  input.email.includes('@')
    ? either.right(input.email)
    : either.left('Invalid email');

const validateAge = (input) =>
  input.age >= 0 && input.age <= 150
    ? either.right(input.age)
    : either.left('Invalid age');

const validateName = (input) =>
  input.name.length > 0
    ? either.right(input.name)
    : either.left('Name required');

const validateUser = validate([validateEmail, validateAge, validateName]);

validateUser({ email: 'alice@example.com', age: 30, name: 'Alice' });
// Right(['alice@example.com', 30, 'Alice'])

validateUser({ email: 'invalid', age: -1, name: '' });
// Left('Invalid email')

-- 使用 EitherT 处理 API 请求
handleRequest :: Request -> EitherT ApiError IO Response
handleRequest req = do
  user    <- authenticate req
  order   <- liftIO $ getOrder (orderId req)
  valid   <- validateOrder order user
  payment <- processPayment valid
  receipt <- liftIO $ sendReceipt payment
  return $ successResponse receipt
  where
    authenticate req =
      case lookup "Authorization" (headers req) of
        Nothing -> left Unauthorized
        Just token -> case decodeToken token of
          Nothing -> left InvalidToken
          Just user -> right user