仅在使用foldr定义zip时出现无限类型错误;它可以修复吗？ [英] Infinite type error when defining zip with foldr only; can it be fixed?

问题描述

（对于上下文，请参阅最近的SO条目

a>）。

我试图用 foldr来定义 zip only：

  zipp :: [a]  - > [b]  - > [（a，b）] 
 zipp xs ys = zip1 xs（zip2 ys）
其中
  -  zip1 :: [a]  - > tq  - > [（a，b）]  -  zip1 xs :: tr〜tq  - > [（a，b）] 
 zip1 xs q = foldr（\ xrq  - > qxr）n xs q 
 -------- c -------- 
nq = [] 
 
  -  zip2 :: [b]  - > a  - > tr  - > [（a，b）]  -  zip2 ys :: tq〜a  - > tr  - > [（a，b）] 
 zip2 ys xr = foldr（\ yqxr  - >>（x，y）：rq）m ys xr 
 ---------- k  - ------------- 
mxr = [] 
 { -  
 zipp [x1，x2，x3] [y1，y2，y3，y4] 
 
 = c x1（c x2（c xn n））（k y1（k y2（k y3（k y4 m））））
 ------------ --- ---------------------- 
rq 
 
 = k y1（k y2（k y3（k y4 m ）））x1（c x2（c xn n））
 ---------------------- ----------- ---- 
qr 
  - } 
  

但给出了两个无限类型的错误：

$ $ $ $ p $ $ $ $ $ $>发生检查：不能构造无限类型
t1〜（a - > t1 - > [（a，b）]） - > [（a，b）] - tr

发生检查：无法构造无限类型：
t0〜a - > （t 0 - > [（a，b）]） - > [（a，b）] - tq


显然，每个类型 tr ， tq ，以循环的方式依赖于另一个。

任何方式使其工作，通过某种类型的巫术或什么？

我在Win7上使用Haskell Platform 2014.2.0.0和GHCi 7.8.3。

解决方案 div>

运用来自我的其他答案的见解，我能够

   -  tr〜tq  - > [（a，b）] 
  -  tq〜a  - > tr  - > [（a，b）] 
 
 newtype Tr a b = PackR {unpackR :: Tq a b  - > [（a，b）]} 
 newtype Tq a b = PackQ {unpackQ :: a  - > Tr a b  - > [（a，b）]} 
 
 zipp :: [a]  - > [b]  - > [（a，b）] 
 zipp xs ys = unpackR（zip1 xs）（zip2 ys）
其中
 zip1 = foldr（\ xr  - > PackR $ \q  - > ; unpackQ qxr）n 
n = PackR（\_-> []）
 
 zip2 = foldr（\ yq  - > PackQ $ \xr  - >（x， y）：unpackR rq）m 
m = PackQ（\__-> []）
 
 main = print $ zipp [1..3] [10,20 ..] 
  -  [（1,10），（2,20），（3,30）] 
  

从类型相等到类型定义的翻译纯粹是机械的，所以也许编译器也可以为我们做到这一点！

(for the context to this see this recent SO entry).

I tried to come up with the definition of zip using foldr only:

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

It "works" on paper, but gives two "infinite type" errors:

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

Evidently, each type tr, tq, depends on the other, in a circular manner.

Is there any way to make it work, by some type sorcery or something?

I use Haskell Platform 2014.2.0.0 with GHCi 7.8.3 on Win7.

解决方案

Applying the insight from my other answer, I was able to solve it, by defining two mutually-recursive types:

-- tr ~ tq -> [(a,b)]
-- tq ~ a -> tr -> [(a,b)]

newtype Tr a b = PackR { unpackR ::  Tq a b -> [(a,b)] }
newtype Tq a b = PackQ { unpackQ ::  a -> Tr a b -> [(a,b)] }

zipp :: [a] -> [b] -> [(a,b)]
zipp xs ys = unpackR (zip1 xs) (zip2 ys)
  where
     zip1 = foldr (\ x r -> PackR $ \q -> unpackQ q x r ) n 
     n = PackR (\_ -> [])

     zip2 = foldr (\ y q -> PackQ $ \x r -> (x,y) : unpackR r q ) m 
     m = PackQ (\_ _ -> [])

main = print $ zipp [1..3] [10,20..]
-- [(1,10),(2,20),(3,30)]

The translation from type equivalency to type definition was purely mechanical, so maybe compiler could do this for us, too!

这篇关于仅在使用foldr定义zip时出现无限类型错误;它可以修复吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！