haskell - 为无限 Stream 派生 Functor

Question

我正在关注这个 blog关于 F 代数 它解释说

A terminal coalgebra is usually interpreted in programming as a recipe for generating (possibly infinite) data structures or transition systems.

然后说

A canonical example of a coalgebra is based on a functor whose fixed point is an infinite stream of elements of type e. This is the functor:

data StreamF e a = StreamF e a
  deriving Functor

这是它的不动点:

data Stream e = Stream e (Stream e)

我试过代码 here

相关部分是

newtype Fix f = Fix (f (Fix f))
unFix :: Fix f -> f (Fix f)
unFix (Fix x) = x

cata :: Functor f => (f a -> a) -> Fix f -> a
cata alg = alg . fmap (cata alg) . unFix

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

data StreamF e a = StreamF e a
    deriving Functor
data Stream e = Stream e (Stream e)

era :: [Int] -> StreamF Int [Int]
era (p : ns) = StreamF p (filter (notdiv p) ns)
    where notdiv p n = n `mod` p /= 0

primes = ana era [2..]

我遇到了这个错误

main.hs:42:14: error:
• Can’t make a derived instance of ‘Functor (StreamF e)’:
You need DeriveFunctor to derive an instance for this class
• In the data declaration for ‘StreamF’

我哪里错了？

Answer 1

在不使用语言扩展的情况下，

deriving 在 Haskell 中非常有限。由于编译器不能总是计算出 Functor 实例应该是什么，deriving Functor 不是标准的 Haskell。

但是，有一种语言扩展允许这样做，即 -XDeriveFunctor。要启用此扩展，请执行以下操作之一:

• 使用标志 -XDeriveFunctor 进行编译。 (如:编译时运行ghc -XDeriveFunctor Main.hs)

• 在文件顶部写入编译指示 {-# LANGUAGE DeriveFunctor #-}。

添加此编译指示后，您的文件将如下所示:

{-# LANGUAGE DeriveFunctor #-}

newtype Fix f = Fix (f (Fix f))
unFix :: Fix f -> f (Fix f)
unFix (Fix x) = x

cata :: Functor f => (f a -> a) -> Fix f -> a
cata alg = alg . fmap (cata alg) . unFix

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

data StreamF e a = StreamF e a
    deriving Functor
data Stream e = Stream e (Stream e)

era :: [Int] -> StreamF Int [Int]
era (p : ns) = StreamF p (filter (notdiv p) ns)
    where notdiv p n = n `mod` p /= 0

primes = ana era [2..]

如果您计划使用 GHCi，请在加载文件之前使用 :set -XDeriveFunctor。