deriving a Functor for an infinite Stream

Question

I'm following this blog about F-algebras It explains that

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

and says that

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

and this is its fixed point:

data Stream e = Stream e (Stream e)

I’ve tried the code here

the relevant part being

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..]

I’m getting this error

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’

Where am I going wrong?

Answer 1

deriving is very limited in Haskell without using language extensions. Since the compiler can't always work out what a Functor instance should be, deriving Functor is not standard Haskell.

However, there is a language extension that allows this, namely -XDeriveFunctor. To enable this extension do one of:

• Compile with the flag -XDeriveFunctor. (Eg: run ghc -XDeriveFunctor Main.hs when compiling)

• Write the pragma {-# LANGUAGE DeriveFunctor #-} at the top of your file.

Here's how your file would look with this pragma added:

{-# 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..]

If you plan on using GHCi, use :set -XDeriveFunctor before loading the file.