了解 "Programming In Haskell" 第 12 章中的应用问题（#7）

Question

我一直在努力 Programming in Haskell (2nd ed)。不过，我对 Applicatives 的问题有点困惑。

给定以下类型：

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

问题是编写 Functor、Applicative 和 Monad 类.

的实现

Functor 和 Monad 一样简单（至少它可以编译，我还没有完全理解它，但我首先更担心这一点）。

我想出了这个，可以编译，但我有顾虑：

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

    -- (<*>) :: Expr (a -> b) -> Expr a -> Expr b
    (Var fab) <*> fa = fmap fab fa

pure 很好，但我担心实际的应用运算符 <*>。据我所知，它只对 Var 有意义——对 Val 或 Add 没有意义。对我来说，你有一个类型来表达可以爆炸的东西是合法的，这对我来说似乎很奇怪——例如，你可以有 Add (Var ord) (Val 10) 类型 Expr (Char -> Int)，所以将类型检查作为lhs 在 <*> 表达式中，但是（就目前而言）会爆炸。我不清楚递归定义是如何工作的——因为一旦你点击 (Val 10)，你就被塞满了——没有办法将 rhs 转换为必要的类型。

我在这里错过了什么？我如何完成 <*> 的定义，这样事情就不会爆炸，而且它仍然是一个有效的应用程序？ thinking/feeling 我说的对吗，实际上你不会设计这样的类型？

谢谢！

Answer 1

Val :: Int -> Expr a

对于任何 a。所以

Val x <*> _ = Val x

有效，原样

_ <*> Val y = Val y

原样

Val x <*> Val y = Val (something about x and y)

所以不幸的是现在你有一个选择，这意味着你即将做出错误的选择。幸运的是，其中只有一个与 Monad 实例兼容（哪个？）。

至于递归的情况，你有

Add e e' <*> fb = ...
     -- e :: Expr (a -> b)
     -- e' :: Expr (a -> b)
     -- fb :: Expr a

并且您应该使用所有传入的信息来制作 Expr b，并保留 "structure" (Add)。您可以从中创建 Expr b 的所有方法是什么（记住您可以递归地使用应用运算符）？

了解 "Programming In Haskell" 第 12 章中的应用问题（#7）

Understand the Applicative problem (#7) in Chapter 12 of "Programming In Haskell"

haskell

functional-programming

applicative