用变形写邮编(longzip)

Question

致力于一个项目，并试图用无变形的方式来编写longzip。我在为这个用例编写协代数时遇到了一些困难。我在下面用Fix定义了我的变形：

-- Fixed point of a Functor    
newtype Fix f = In (f (Fix f))     
    
deriving instance (Eq (f (Fix f))) => Eq (Fix f)    
    
out :: Fix f -> f (Fix f)    
out (In f) = f 

-- Anamorphism
type Coalgebra f a = a -> f a

ana :: (Functor f) => Coalgebra f a -> a -> Fix f
ana f = In . fmap (ana f) . f

这是从cata的“反转箭头”派生出来的ana的定义：

-- Catamorphism    
type Algebra f a = f a -> a    
    
cata :: (Functor f) => Algebra f a -> Fix f -> a

cata f = f . fmap (cata f) . out

我看到zip使用ana的一个版本编写，该版本的定义显然不同(以谓词作为参数)：

 zip2 = ana unsp fin
    where
    fin (as,bs) = (as==[]) || (bs ==[]) 
    unsp ((a:as), (b:bs)) = ((a,b),(as,bs))

(取自https://en.wikipedia.org/wiki/Anamorphism)

但是，我不知道如何使用上面定义的ana版本，特别是在编写Coalgebra类型的a -> fa方面。类似地，它是否必须将两个列表参数取为zip，并将它们组合成一个a

Answer 1

首先，给自己一个起点。写下你要做的事：

-- make this example actually complete
{-# Language StandaloneDeriving, UndecidableInstances, DeriveFunctor #-}
import Prelude hiding (zip)


-- Fixed point of a Functor
newtype Fix f = In (f (Fix f))

deriving instance (Eq (f (Fix f))) => Eq (Fix f)
deriving instance (Show (f (Fix f))) => Show (Fix f)

out :: Fix f -> f (Fix f)
out (In f) = f

-- Anamorphism
type Coalgebra f a = a -> f a

ana :: (Functor f) => Coalgebra f a -> a -> Fix f
ana f = In . fmap (ana f) . f


-- Base functor for a list
data ListF a f = Nil | Cons a f deriving (Eq, Show, Functor)
type List a = Fix (ListF a)

-- write down the type. It helps you think about things
zip :: List a -> List b -> List (a, b)
zip x y = ana undefined undefined

您知道，zip必须作为对ana的调用来实现，所以剩下的就是找出种子和协代数。应该相当清楚，种子需要包含x和y。似乎没有任何进一步的信息是必要的，所以让我们假设种子将是(x, y)，直到/除非它带来问题。这些信息足以确定第一次尝试的类型：

zip :: List a -> List b -> List (a, b)
zip x y = ana zipCoalgebra (x, y)

zipCoalgebra :: (List a, List b) -> ListF (a, b) (List a, List b)
zipCoalgebra = undefined

我觉得这是你错过的一步:写下你想要做的事情，然后跟随类型来确定你所需要的。如果您曾经看到过zip的任何实现，那么剩下的部分就有点微不足道了。这是一个写下最无聊的事情类型检查(密切注意List和ListF在类型之间的区别)的问题。我强烈建议你停止在这里阅读，自己试一试。除此之外，我可以说，这实际上对学习如何思考这个问题没有什么帮助。

如果你真的一点也不知道：

zipCoalgebra :: (List a, List b) -> ListF (a, b) (List a, List b)
zipCoalgebra (In (Cons a as), In (Cons b bs)) = Cons (a, b) (as, bs)
zipCoalgebra _ = Nil

如果您以前见过zip的实现，那么它确实是您所期望的，它带有必要的噪声，可以使它在Fix周围进行类型检查。让我们让它转一下：

ghci> zip (In (Cons 1 (In Nil))) (In Nil)
In Nil
ghci> zip (In (Cons 1 (In Nil))) (In (Cons 2 (In Nil)))
In (Cons (1,2) (In Nil))

是啊。按预期行事。看来这两份名单就像种子一样充足，一切都很好。