为什么Haskell不接受我的组合“zip”定义？ [英] Why Haskell doesn't accept my combinatoric "zip" definition?

问题描述

这是教科书的zip函数：

  zip :: [a]  - > [a]  - > [（a，a）] 
 zip [] _ = [] 
 zip _ [] = [] 
 zip（x：xs）（y：ys）=（x，y） ：zip xs ys 
  

我之前问#haskell可以使用foldr单独，没有递归，没有模式匹配。经过一番思考，我们注意到递归可以使用continuation来消除：

  zip':: [a]  - > [a]  - > [（a，a）] 
 zip'= foldr cons nil 
其中
 cons ht（y：ys）=（h，y）：（t ys）
 cons ht [] = [] 
 nil = const [] 
  

。在一些神经元敬酒后，我想出了一个不完整的答案，我认为这是合乎逻辑的：

  zip :: [a]  - > ; [a]  - > [a] 
 zip ab =（zipper a）（zipper b）其中
 zipper = foldr（\ x xs cont  - > x：cont xs）（const []）
  

它会返回一个扁平列表，但会进行压缩。我确信这是有道理的，但Haskell抱怨这种类型。我开始在一个无类型的lambda计算器上测试它，并且它工作。为什么Haskell不能接受我的函数？

错误是：

  zip.hs：17：19：
发生检查：无法构造无限类型：
 t0〜（t0  - > [a]） - > [a] 
预期类型：a  - > （（t0→[a]）→> [a]）→> （t0→[a]）→> [a] 
实际类型：a 
  - > （（t0→[a]）→> [a]）→> （（（t 0  - > [a]） - > [a]） - > [a]） - > [a] 
相关绑定包括
b∷[a]（以zip.hs为界限：17：7）
a∷[a]（以zip.hs为界限：17：5）
 zip∷[a]  - > [a]  - > 
在'foldr'的第一个参数中，即'cons'
在表达式中：（（foldr cons nil a）（foldr cons nil b））
 
 zip.hs：17：38：
发生检查：无法构造无限类型：
 t0〜（t0  - > [a]） - > [a] 
预期类型：a  - > （t0→[a]）→> t0  - > [a] 
实际类型：a  - > （t0→[a]）→> （（t0→[a]）→> [a]）→> [a] 
相关绑定包括
b∷[a]（以zip.hs为界限：17：7）
a∷[a]（以zip.hs为界限：17：5）
 zip∷[a]  - > [a]  - > 
在'foldr'的第一个参数中，即'cons'
在'foldr'的第四个参数中，''（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 第一个参数的类型：

  a'：= a 
 b'：= r 
 b'：=（r  - > [a]） - > [a] 
  

这当然是一个问题（如 r 和（r - > [a]） - > [a] mutual-recursive，并且应该都等于 b' ）



这是编译器告诉你的信息



如何修复

您可以使用

  newtype修复您的想法Fix at = Fix { unFix :: Fix at  - > [a]} 
  

我借用 >形成原始使用。

有了这个，你可以这样写：

  zipCat :: [a] - > [a]  - > [a] 
 zipCat ab = （unFix $ zipper a）（zipper b）其中
 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] 
   
 
 
  BUT 在这里显而易见你的名单必须是同一类型，所以我不知道这是否真的能帮助你 
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)’

解决方案
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

                        
这篇关于为什么Haskell不接受我的组合“zip”定义？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！