Почему Haskell не принимает мое комбинаторное определение zip?

zipw :: [a] -> [a] -> [a]
zipw xs ys = (zipper xs) (zipper ys) where
    zipper xs q = foldr (\ x r q -> x : q r) (const []) xs q
                        --- c -------------- --- n ----

 -- zipper [x1,x2,x3] (zipper ys) =
 -- c x1 (c x2 (c x3 n)) (zipper ys)
         --- r --------  --- q -----  tr ~ tq ; q r :: [a]
                                      --     => r r :: [a]
                                      -- => r :: tr -> [a] 
                                      --   tr ~  tr -> [a]    

Итак, это бесконечный тип. Haskell не допускает этого для произвольного типа (это то, что означают переменные типа).

Но типы данных Haskell действительно допускают рекурсию. Списки, деревья и т. д. — все обычные типы рекурсивны. Это разрешено:

data Tree a = Branch (Tree a) (Tree a)

Здесь у нас действительно один и тот же тип в обеих частях уравнения, точно так же, как у нас есть tr в обеих частях эквивалентности типов, tr ~ tr -> [a]. Но это особый тип, а не произвольный.

Поэтому мы просто объявляем это так, следуя приведенному выше «уравнению»:

newtype TR a = Pack { unpack :: TR a -> [a] } 
           -- unpack :: TR a -> TR a -> [a]

Что такое тип Tree a? Это «что-то», что входит в Branch, то есть в Tree a. Данное дерево не обязательно должно строиться бесконечно, потому что undefined тоже имеет тип Tree a.

Что такое тип TR a? Это «что-то», что входит в TR a -> [a], то есть TR a. Заданное TR a не обязательно должно конструироваться бесконечно, потому что const [] может быть и типа TR a.

Наш подражатель рекурсивному типу tr ~ tr -> [a] стал настоящим определением рекурсивного типа newtype TR a = Pack { TR a -> [a] }, скрывающимся за конструктором данных Pack (от которого компилятор избавится благодаря использованию ключевого слова newtype, но это лишняя деталь; он работает с data слишком).

Здесь Haskell обрабатывает рекурсивность. Теоретики шрифтов любят заниматься этим сами, с Fix и еще чем-то; но пользователь Haskell уже имеет это на языке. Нам не нужно понимать, как он реализован, чтобы уметь его использовать. Не нужно изобретать велосипед, пока мы сами не захотим построить его.

Итак, zipper xs имел тип tr; теперь он становится TR a, так что это то, что новое zipper xs должно возвращать "упакованную" функцию создания списка. Комбинирующая функция foldr должна возвращать то, что возвращает вызов zipper (в силу определения foldr). Чтобы применить упакованную функцию, нам нужно сначала ее unpack:

zipw :: [a] -> [a] -> [a]
zipw xs ys = unpack (zipper xs) (zipper ys)
    where
    zipper :: [a] -> TR a
    zipper = foldr (\ x r -> Pack $ \q -> x : unpack q r)
                   (Pack $ const [])