Haskell在ADT上的递归问题。

Question

我已经看完了第8章代数数据类型的内容。LYAHFGG 而我在尝试实现类似Scheme的列表操作时遇到了一个麻烦。

我的想法是尝试在Pair adt上建立cons、car、cdr，然后写一个标准递归来计算长度。

data Pair a b =  NullPair | Pair { thisCar :: a, thisCdr :: b} deriving (Eq)

cons :: a -> b -> Pair a b
cons x y = Pair { thisCar = x, thisCdr = y}

car :: Pair a b -> a
car (Pair {thisCar = x, thisCdr = y}) = x

cdr :: Pair a b -> b
cdr (Pair {thisCar = x, thisCdr = y}) = y

instance (Show a, Show b) => Show (Pair a b) where
  show NullPair = "()"
  show (Pair { thisCar=x, thisCdr=y}) = "(" ++ show x ++ " . " ++ show y ++ ")" 

到目前为止还不错

l1 = NullPair   -- ()
l2 = cons 3 NullPair  -- (3)
l3 = cons (cons 2 NullPair) (cons 3 (cons 4 NullPair))  -- ((2) 3 4)

λ> l1
()
λ> l2
(3 . ())
λ> l3
((2 . ()) . (3 . (4 . ())))
λ> car l2
3
λ> car l3
(2 . ())
λ> cdr l2
()
λ> cdr l3
(3 . (4 . ()))
λ> cdr (cdr l3)
(4 . ())

请注意，当我输入cdr（cdr l3）时，REPL没有抱怨。 稍后再谈这个问题...

所以这里是我的 length 函数（我们假设输入是一组嵌套的对，其最里面的 thisCdr 是 NullPair），以及我试图编译它时得到的错误。

len :: Pair a b -> Integer
len NullPair = 0
len p = 1 + len $ thisCdr p

lists.hs:117:19-27: error: …
    • Couldn't match expected type ‘Pair a0 b0’ with actual type ‘b’
      ‘b’ is a rigid type variable bound by
        the type signature for:
          len :: forall a b. Pair a b -> Integer
        at /home/nate/Documents/haskell/ProblemSets/lists.hs:115:8
    • In the second argument of ‘($)’, namely ‘thisCdr p’
      In the expression: 1 + len $ thisCdr p
      In an equation for ‘len’: len p = 1 + len $ thisCdr p
    • Relevant bindings include
        p :: Pair a b
          (bound at /home/nate/Documents/haskell/ProblemSets/lists.hs:117:5)
        len :: Pair a b -> Integer
          (bound at /home/nate/Documents/haskell/ProblemSets/lists.hs:116:1)
Compilation failed.

我的解释是，我告诉编译器寻找类型为 Pair a b 的东西，但它却找到了类型为 b 的东西，并且不相信我的 b 真的会是 Pair a b 的替身。同样令人费解的是，它对 cdr (cdr l3) 没有任何问题，即使 cdr 返回一个类型为 b 的值，但却期望一个类型为 Pair a b 的值。

那么。

1. 谁能用技术术语解释一下这到底是怎么回事？很明显，我没有掌握类型系统的一些知识。或者很可能是我的代码有缺陷。
2. 有什么办法可以解决这个问题吗？也许有更好的方法来执行这种递归？

非常感谢你的帮助。

Answer 1

我认为你的解释大部分是正确的! 让我澄清几件事。

为什么你的定义中没有 len 工作？

首先，当你声明一个带有类型变量的函数时（如 a 和 b 在 Pair a b)，你的函数必须适用于任何选择的 a 或 b. 这就是为什么在你看到的错误信息中，编译器说

...
        the type signature for:
          len :: forall a b. Pair a b -> Integer
...

该 forall 是Haskell中隐含的东西，当我们写下了 Pair a b.

所以编译器对你很生气，因为你想使用一种特殊的 b (即a Pair a0 b0)，但如果你的函数在以下情况下无法工作 b 是，说。Int.

为什么 cdr (cdr l3) 工作？

那是因为编译器知道什么是 l3 是。当你申请 cdr 的东西，你就会得到这样的形式 Pair a b所以第二个应用程序可以工作。

你可以要求编译器推断这些函数的类型是什么。请注意，它们需要的类型比单纯的 Pair a b.

Prelude> cddr x = cdr (cdr x)
Prelude> :t cddr
cddr :: Pair a1 (Pair a2 b) -> b
Prelude> caddr x = car (cdr (cdr x))
Prelude> :t caddr
caddr :: Pair a1 (Pair a2 (Pair a3 b)) -> a3

由于编译器会推断出 NullPair 具有非常一般的类型 forall a b. Pair a b. 当它作为一个 争论జజజజజజజజజజజజజజజజజజజజజజజజజజజజజజజజజజజజజజజ a 和 b 可以选择这样的表达式类型检查。因此，任何任意使用 car 和 cdr在 NullPair 喜欢 car (car (cdr NullPair)) 会打字检查。这两者之间有一个双重性 forall的时候，以及被函数期望的时候。但如果这个解释让人困惑，你可以暂时忽略它。

如何绕过它呢？

我建议让你的数据类型显式递归。这就失去了一些通用性，你可以如何使用你的 Pair 数据类型，但很难写出 len 否则。

data Pair a = NullPair | Pair{ thisCar :: a, thisCdr :: Pair a }

现在你写的任何函数都会知道 thisCdr 是具有以下形式 Pair a.

你可能会注意到，这只是不同名称的列表的定义）。

如果你真的想保留 Pair 一样

我不建议这样做，但如果你真的想保持你的定义的。Pair 相同，下面是如何解决这个问题。

定义数据类型

data Fix f = Fix (f (Fix f))

名称 Fix 是习惯性的（据我所知），像这样的数据类型；我不这么叫是因为它是你问题的解决方案。你可以把它看作是一个 "递归 "数据类型（如果你对 功能 fix这是它对类型的类似物）。)

现在我们可以用它来把递归放到 Pair.

len :: Fix (Pair a) -> Integer
len (Fix NullPair) = 0
len (Fix p) = 1 + (len $ thisCdr p)

如果我们要检查的类型。p我们会看到，它是 p :: Pair a (Fix (Pair a)). 一般来说，以下类型的东西 Fix (Pair a) 看起来

Fix (Pair a) = Fix (Pair a (Fix (Pair a)))
             = Fix (Pair a (Fix (Pair a (Fix (Pair a)))))
             = ...

这就给了我们 "无限类型"，编译器在你的第一个定义中抱怨的是 len. 虽然我使用了引号，因为类型可以有限地写出来。

请注意 Fix (Pair a) 相当于显式递归定义的 Pair 我在上一节中建议过。所以从某种意义上来说，这也是同样的解决方案，只是递归数据类型更加明确（或者说更加混乱）。

Answer 2

1 + len $ thisCdr p

解析为

(1 + len) $ (thisCdr p)

正如你所猜测的那样，试图在函数len上加1是没有意义的，而且将结果作为函数应用也是毫无意义的。你想要的是

1 + len (thisCdr p)