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

Question

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

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 [])

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]

这就是（我认为）你想要的。

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