如何在 Haskell 中实现 <*> 自定义类型

Question

我正在阅读 Graham Hutton 的书 Programming in Haskell。 我有一个关于练习 12.7 的问题。任务是展示如何制作该类型

data Expr a = Var a | Val Int | Add (Expr a) (Expr a)

到 Functor 和 Applicative 类的实例中。

将其变成 Functor 的实例很简单：

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')

但是，我不确定如何实现

<*>

运算符，特别是当它的一个或两个输入具有构造函数 Val 时，我不清楚如何定义它：

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

  --(<*>) :: Expr (a -> b) -> Expr a -> Expr b
 (Var f) <*> (Var x) = Var (f x)
 (Var f) <*> (Add e1 e2) = Add (fmap f e1) (fmap f e2)
 (Add fe1 fe2) <*> e = Add (fe1 <*> e) (fe2 <*> e)
 _ <*> _ = ???

我的问题是：我怎样才能完成

<*>

的实施以使适用法律成立？

Answer 1

我只会给你一个提示。我相信

要定义

t1 <*> t2

，请扫描表达式树

t1

并找到存在变量的位置，即某些函数

Var f

的

f

。将

t1

中的每个变量替换为新的表达式树

fmap f t2

。将

t1

中的非变量保留原样。

您不需要在

t2

中扫描

<*>

（除非通过

fmap

隐式扫描）。

请注意，这尊重类型。我们有

t1 :: Tree (a -> b)

，因此

f :: a -> b

。此外，

t2 :: Tree a

，因此

fmap f t2 :: Tree b

如所愿。

非正式示例：

(f+(4 + g)) <*> ((1+x)+y) = ( ((1+f x)+f y) + (4 + ((1+g x)+g y)) )