如何为Haskell自定义Expr类型实现<*>运算符并满足Applicative定律

你的Functor实例实现是正确的，完全符合Functor定律。现在来看Applicative实例的补全，核心是处理Val构造器参与<*>的情况，同时要严格遵循Applicative的四条基本定律。

核心思路 #

首先明确Expr类型的语义：

• Var a是携带变量的表达式
• Val Int是常量表达式，不受映射函数影响（这从你的Functor实现中可以看出）
• Add e1 e2是两个表达式的加法组合

Applicative的<*>需要将一个返回函数的表达式（Expr (a->b)）作用于一个返回值的表达式（Expr a），得到返回结果的表达式（Expr b）。结合语义和定律，我们可以这样定义各个情况：

1. pure的实现：你写的pure x = Var x是正确的，因为pure需要构造一个“最小上下文”的表达式，Var是唯一携带类型参数a的构造器，符合要求。
2. Var f <*> e：直接复用fmap实现，因为Applicative的基本性质要求pure f <*> e = fmap f e，而pure f就是Var f，这条可以覆盖Var f和任意Expr a的组合（包括Var x、Val n、Add e1 e2）。
3. Add fe1 fe2 <*> e：你写的Add (fe1 <*> e) (fe2 <*> e)是正确的，加法表达式的函数作用应该是两个子表达式分别作用于e后再相加。
4. Val n <*> _：常量表达式作为函数上下文时，无论右边是什么表达式，结果都应该是原常量。因为Val n本身不携带任何函数逻辑，且根据Functor的定义，fmap对Val无影响，这条也符合Applicative的定律（比如交换律、组合律）。

完整实现代码 #

instance Functor Expr where
  --fmap :: (a -> b) -> Expr a -> Expr b
  fmap f (Var x) = Var $ f x
  fmap f (Val i) = Val i
  fmap f (Add e e') = Add (fmap f e) (fmap f e')

instance Applicative Expr where
  --pure :: a -> Expr a
  pure x = Var x

  --(<*>) :: Expr (a -> b) -> Expr a -> Expr b
  (Var f) <*> e = fmap f e
  (Add fe1 fe2) <*> e = Add (fe1 <*> e) (fe2 <*> e)
  (Val n) <*> _ = Val n

验证Applicative定律 #

我们可以快速验证核心定律：

• Identity：pure id <*> v = Var id <*> v = fmap id v = v，符合恒等律。
• Homomorphism：pure f <*> pure x = Var f <*> Var x = fmap f (Var x) = Var (f x) = pure (f x)，成立。
• Interchange：比如当u = Val n时，u <*> pure y = Val n <*> Var y = Val n，而pure ($ y) <*> u = Var ($ y) <*> Val n = fmap ($ y) (Val n) = Val n，两边相等；其他情况也可同理验证。
• Composition：当u = Val n时，pure (.) <*> u <*> v <*> w = Val n，u <*> (v <*> w) = Val n，相等；其他组合也符合要求。

内容的提问来源于stack exchange，提问作者TRP