Why Haskell doesn't accept my combinatoric "zip" definition?

Question

This is the textbook zip function:

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

I asked on #haskell earlier wether "zip" could be implemented using "foldr" alone, no recursion, no pattern matching. After some thinking, we noticed the recursion could be eliminated using continuations:

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

We are still left with pattern matching. After some more neuron toasting I came up with an incomplete answer that I thought was logical:

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

It returns a flat list, but does the zipping. I was certain it made sense, but Haskell complained about the type. I proceeded to test it on a untyped lambda calculator, and it worked. Why can't Haskell accept my function?

The error is:

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

As to why your definition is not accepted: look at this:

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

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

so if you want to use the first function as an argument for foldr you get (if you match the types of foldrs first argument:

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

which of course is a problem (as r and (r -> [a]) -> [a] mutual-recursive and should both be equal to b' )

That is what the compiler tells you

how to repair it

You can repair your idea using

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

which I borrowed form it original use.

With this you can write:

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

and you get:

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

which is (what I think) you wanted.

BUT obvious here both of your lists needs to be of the same type so I don't know if this will really help you