为什么Haskell不接受我的组合"zip"定义？

Question

这是教科书的zip功能:

zip :: [a] -> [a] -> [(a,a)]
zip [] _ = []
zip _ [] = []
zip (x:xs) (y:ys) = (x,y) : zip xs ys

我在#haskell上问过早期的"zip"可以单独使用"foldr"实现,没有递归,没有模式匹配.经过一番思考,我们注意到可以使用continuation消除递归:

zip' :: [a] -> [a] -> [(a,a)]
zip' = foldr cons nil
    where
        cons h t (y:ys) = (h,y) : (t ys)
        cons h t []     = []
        nil             = const []

我们仍然留有模式匹配.在进行了一些神经元烘烤之后,我想出了一个我认为合乎逻辑的不完整答案:

zip :: [a] -> [a] -> [a]
zip a b = (zipper a) (zipper b) where
    zipper = foldr (\ x xs cont -> x : cont xs) (const [])

它返回一个平面列表,但是会进行压缩.我确信它有道理,但Haskell抱怨这种类型.我继续在一个无类型的lambda计算器上测试它,它工作.为什么Haskell不能接受我的功能？

错误是:

zip.hs:17:19:
    Occurs check: cannot construct the infinite type:
      t0 ~ (t0 -> [a]) -> [a]
    Expected type: a -> ((t0 -> [a]) -> [a]) -> (t0 -> [a]) -> [a]
      Actual type: a
                   -> ((t0 -> [a]) -> [a]) -> (((t0 -> [a]) -> [a]) -> [a]) -> [a]
    Relevant bindings include
      b ? [a] (bound at zip.hs:17:7)
      a ? [a] (bound at zip.hs:17:5)
      zip ? [a] -> [a] -> [a] (bound at zip.hs:17:1)
    In the first argument of ‘foldr’, namely ‘cons’
    In the expression: ((foldr cons nil a) (foldr cons nil b))

zip.hs:17:38:
    Occurs check: cannot construct the infinite type:
      t0 ~ (t0 -> [a]) -> [a]
    Expected type: a -> (t0 -> [a]) -> t0 -> [a]
      Actual type: a -> (t0 -> [a]) -> ((t0 -> [a]) -> [a]) -> [a]
    Relevant bindings include
      b ? [a] (bound at zip.hs:17:7)
      a ? [a] (bound at zip.hs:17:5)
      zip ? [a] -> [a] -> [a] (bound at zip.hs:17:1)
    In the first argument of ‘foldr’, namely ‘cons’
    In the fourth argument of ‘foldr’, namely ‘(foldr cons nil b)’

Answer 1

至于为什么不接受你的定义:看看这个:

?> :t \ x xs cont -> x : cont xs
 ... :: a -> r -> ((r -> [a]) -> [a])

?> :t foldr
foldr :: (a' -> b' -> b') -> b' -> [a'] -> b'

所以如果你想使用第一个函数作为foldr你得到的参数(如果你匹配foldr第一个参数的类型:

a' := a
b' := r
b' := (r -> [a]) -> [a]

这当然是一个问题(作为r和(r -> [a]) -> [a]相互递归,应该都是相同的b')

这就是编译器告诉你的

如何修复它

您可以使用修复您的想法

newtype Fix a t = Fix { unFix :: Fix a t -> [a] }

我借用它原来的用途.

有了这个你可以写:

zipCat :: [a] -> [a] -> [a]
zipCat a b = (unFix $ zipper a) (zipper b) where
  zipper = foldr foldF (Fix $ const [])
  foldF x xs = Fix (\ cont -> x : (unFix cont $ xs))

你得到:

?> zipCat [1..4] [5..8]
[1,5,2,6,3,7,4,8]

这是你想要的(我想的).

但很明显,这两个列表需要属于同一类型,所以我不知道这是否真的对你有帮助