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

Question

这是教科书的zip函数:

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

我之前在#haskell 上询问“zip”是否可以单独使用“foldr”来实现，没有递归，没有模式匹配。经过一番思考，我们注意到可以使用延续来消除递归:

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

我们仍然剩下模式匹配。经过更多的神经元 toast 之后，我想出了一个不完整的答案，我认为这是合乎逻辑的:

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] }

我从它那里借来的original use .

用这个你可以写:

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]

这就是(我认为的)你想要的。

但是很明显，您的两个列表都需要具有相同的类型，所以我不知道这是否真的会对您有帮助