我已经完成了LYAHFGG中关于代数数据类型的第8章,但是当我尝试实现类似Scheme的列表操作时遇到了问题。
我的想法是在Pair adt上构建cons、car、cdr,然后编写标准递归来计算长度:
到目前为止一切顺利:
请注意,当我输入cdr(cdr l3)时,REPL没有抱怨。稍后会详细讲解...
所以这是我的长度函数(我们假设输入是一组嵌套的对,其最内层的thisCdr为NullPair),以及我尝试编译它时得到的错误。
我的理解是,我告诉编译器要寻找一个类型为Pair a b的东西,但它找到了一个类型为b的东西,并且不相信b实际上会成为Pair a b的替代。令人困惑的是,它对cdr(cdr l3)没有问题,即使cdr返回一个类型为b的值,但期望一个类型为Pair a b的值。
因此:
1.有人能用技术术语解释这里发生了什么吗?显然,我对类型系统的某些方面还没有掌握。或者可能我的代码有缺陷。
2.是否有方法绕过这个问题?也许有更好的执行这种递归的方法?
非常感谢您的帮助。
我的想法是在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没有抱怨。稍后会详细讲解...
所以这是我的长度函数(我们假设输入是一组嵌套的对,其最内层的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.是否有方法绕过这个问题?也许有更好的执行这种递归的方法?
非常感谢您的帮助。
len(cons True False)
是什么? - Joseph Sible-Reinstate MonicathisCdr :: b
的类型变量不能保证是Pair
类型。请记住,len
仅接受Pair
类型。 - Redulen :: Pair a b -> Integer
,你可以这样做,这就是编译器关心的。因此,你需要重新考虑你的类型。 - Joseph Sible-Reinstate Monica