Почему Haskell не принимает мое комбинаторное определение «zip»?
Это функция 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 []
Мы все еще остались с сопоставлением с образцом. После еще одного поджаривания нейрона я получил неполный ответ, который мне показался логичным:
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)’