为什么 Haskell 不接受我的组合 "zip" 定义？
Why Haskell doesn't accept my combinatoric "zip" definition?
这是课本压缩函数：
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 [])
它 returns 是一个平面列表，但可以压缩。我确信它是有道理的，但 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)’
至于为什么你的定义不被接受：看这个：
λ> :t \ x xs cont -> x : cont xs
... :: a -> r -> ((r -> [a]) -> [a])
λ> :t foldr
foldr :: (a' -> b' -> b') -> b' -> [a'] -> b'
所以如果你想使用第一个函数作为 foldr 的参数，你会得到（如果你匹配 foldr 的类型第一个 argument :
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]
这就是（我认为的）你想要的。
但是很明显，您的两个列表都必须是同一类型，所以我不知道这是否真的对您有帮助
我们可以通过定义一个函数来消除显式模式匹配。
这是作弊吗？不是 maybe and bool are allowed, as they are; then we should also allow list (also in extra 的 Data.List.Extra),
list :: b -> (a -> [a] -> b) -> [a] -> b
list n c [] = n
list n c (x:xs) = c x xs
一样；这样我们就可以在您的 zip' 定义中得到
cons h t = list [] (\y ys -> (h,y) : t ys)
或例如
= list [] (uncurry ((:).(h,).fst <*> t.snd))
= list [] (curry $ uncurry (:) . ((h,) *** t))
= list [] (flip ((.) . (:) . (h,)) t)
= list [] ((. t) . (:) . (h,))
如果你更喜欢这种东西。
关于你的错误，“infinite type”往往表示自己应用；事实上，无论您的 zipper returns 是什么，您都在自己应用它，在您的
zip a b = (zipper a) (zipper b) where ....
我试图调整你的定义并想出了
zipp :: [a] -> [b] -> [(a,b)]
zipp xs ys = zip1 xs (zip2 ys)
where
-- zip1 :: [a] -> tq -> [(a,b)] -- zip1 xs :: tr ~ tq -> [(a,b)]
zip1 xs q = foldr (\ x r q -> q x r ) n xs q
-------- c --------
n q = []
-- zip2 :: [b] -> a -> tr -> [(a,b)] -- zip2 ys :: tq ~ a -> tr -> [(a,b)]
zip2 ys x r = foldr (\ y q x r -> (x,y) : r q ) m ys x r
---------- k --------------
m x r = []
{-
zipp [x1,x2,x3] [y1,y2,y3,y4]
= c x1 (c x2 (c xn n)) (k y1 (k y2 (k y3 (k y4 m))))
--------------- ----------------------
r q
= k y1 (k y2 (k y3 (k y4 m))) x1 (c x2 (c xn n))
---------------------- ---------------
q r
-}
它在纸面上似乎正确地减少了，但我在这里也遇到了无限的类型错误。
现在没有（立即可见的）自应用程序，但第一个 zip 获得的延续类型取决于第一个 zip 本身的类型；所以仍然存在循环依赖：tq 在 tq ~ a -> tr -> [(a,b)] ~ a -> (tq -> [(a,b)]) -> [(a,b)].
类型等价的两边
确实这是我得到的两个类型错误，（第一个是关于 tr 类型），
Occurs check: cannot construct the infinite type:
t1 ~ (a -> t1 -> [(a, b)]) -> [(a, b)] -- tr
Occurs check: cannot construct the infinite type:
t0 ~ a -> (t0 -> [(a, b)]) -> [(a, b)] -- tq
在通常使用 foldr 和延续的定义中，这些延续的类型是独立的；我想这就是它在那里工作的原因。
- 另见我的
here, and
我可以为您提供一个略有不同的观点（我认为）以得出与 Carsten 类似的解决方案（但类型更简单）。
这里又是你的代码，你的 "weaving zip"（我写 tr 代表 "the type of r"，类似地 tq 代表 "the type of q"；我总是使用"r" 用于递归结果参数的组合函数在foldr定义中，作为助记符）：
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].但它是一种特定类型，而不是任意类型。
所以我们就这么声明，按照上面的"equation":
newtype TR a = Pack { unpack :: TR a -> [a] }
-- unpack :: TR a -> TR a -> [a]
什么是 Tree a 类型？ "something" 进入 Branch，即 Tree a。给定的树不必无限构造，因为 undefined 也有类型 Tree a。
什么是 TR a 类型？ "something" 进入 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 必须 return — "packed" 列表生成函数。 foldr 组合函数必须 return zipper 调用的 returns（根据 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 [])
这是课本压缩函数：
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 [])
它 returns 是一个平面列表，但可以压缩。我确信它是有道理的，但 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)’
至于为什么你的定义不被接受：看这个：
λ> :t \ x xs cont -> x : cont xs
... :: a -> r -> ((r -> [a]) -> [a])
λ> :t foldr
foldr :: (a' -> b' -> b') -> b' -> [a'] -> b'
所以如果你想使用第一个函数作为 foldr 的参数，你会得到（如果你匹配 foldr 的类型第一个 argument :
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]
这就是（我认为的）你想要的。
但是很明显，您的两个列表都必须是同一类型，所以我不知道这是否真的对您有帮助
我们可以通过定义一个函数来消除显式模式匹配。
这是作弊吗？不是 maybe and bool are allowed, as they are; then we should also allow list (also in extra 的 Data.List.Extra),
list :: b -> (a -> [a] -> b) -> [a] -> b
list n c [] = n
list n c (x:xs) = c x xs
一样；这样我们就可以在您的 zip' 定义中得到
cons h t = list [] (\y ys -> (h,y) : t ys)
或例如
= list [] (uncurry ((:).(h,).fst <*> t.snd))
= list [] (curry $ uncurry (:) . ((h,) *** t))
= list [] (flip ((.) . (:) . (h,)) t)
= list [] ((. t) . (:) . (h,))
如果你更喜欢这种东西。
关于你的错误，“infinite type”往往表示自己应用；事实上，无论您的 zipper returns 是什么，您都在自己应用它，在您的
zip a b = (zipper a) (zipper b) where ....
我试图调整你的定义并想出了
zipp :: [a] -> [b] -> [(a,b)]
zipp xs ys = zip1 xs (zip2 ys)
where
-- zip1 :: [a] -> tq -> [(a,b)] -- zip1 xs :: tr ~ tq -> [(a,b)]
zip1 xs q = foldr (\ x r q -> q x r ) n xs q
-------- c --------
n q = []
-- zip2 :: [b] -> a -> tr -> [(a,b)] -- zip2 ys :: tq ~ a -> tr -> [(a,b)]
zip2 ys x r = foldr (\ y q x r -> (x,y) : r q ) m ys x r
---------- k --------------
m x r = []
{-
zipp [x1,x2,x3] [y1,y2,y3,y4]
= c x1 (c x2 (c xn n)) (k y1 (k y2 (k y3 (k y4 m))))
--------------- ----------------------
r q
= k y1 (k y2 (k y3 (k y4 m))) x1 (c x2 (c xn n))
---------------------- ---------------
q r
-}
它在纸面上似乎正确地减少了，但我在这里也遇到了无限的类型错误。
现在没有（立即可见的）自应用程序，但第一个 zip 获得的延续类型取决于第一个 zip 本身的类型；所以仍然存在循环依赖：tq 在 tq ~ a -> tr -> [(a,b)] ~ a -> (tq -> [(a,b)]) -> [(a,b)].
确实这是我得到的两个类型错误，（第一个是关于 tr 类型），
Occurs check: cannot construct the infinite type:
t1 ~ (a -> t1 -> [(a, b)]) -> [(a, b)] -- tr
Occurs check: cannot construct the infinite type:
t0 ~ a -> (t0 -> [(a, b)]) -> [(a, b)] -- tq
在通常使用 foldr 和延续的定义中，这些延续的类型是独立的；我想这就是它在那里工作的原因。
- 另见我的
我可以为您提供一个略有不同的观点（我认为）以得出与 Carsten 类似的解决方案（但类型更简单）。
这里又是你的代码，你的 "weaving zip"（我写 tr 代表 "the type of r"，类似地 tq 代表 "the type of q"；我总是使用"r" 用于递归结果参数的组合函数在foldr定义中，作为助记符）：
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].但它是一种特定类型，而不是任意类型。
所以我们就这么声明，按照上面的"equation":
newtype TR a = Pack { unpack :: TR a -> [a] }
-- unpack :: TR a -> TR a -> [a]
什么是 Tree a 类型？ "something" 进入 Branch，即 Tree a。给定的树不必无限构造，因为 undefined 也有类型 Tree a。
什么是 TR a 类型？ "something" 进入 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 必须 return — "packed" 列表生成函数。 foldr 组合函数必须 return zipper 调用的 returns（根据 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 [])