Anamorphism Example

There don’t seem to be many examples of anamorphisms around. Here’s one to make up the lack.

Let’s start off with our target language.

> {-# LANGUAGE
>     DeriveFunctor,
>     DeriveFoldable,
>     DeriveTraversable #-}
>
> import Data.Foldable
> import Data.Traversable
>
> data TermF a = PlusF a a
>              | MultF a a
>              | IntConstF Int
>              deriving (Show, Ord, Eq, Functor, Foldable, Traversable)
>
> newtype Mu f = In {out :: f (Mu f)}
>
> type Term = Mu TermF
>
> type Algebra f a   = f a -> a
> type CoAlgebra f a = a -> f a
>
> cata :: Functor f => Algebra f a -> (Mu f -> a)
> cata f = f . fmap (cata f) . out
>
> ana :: Functor f => CoAlgebra f a -> (a -> Mu f)
> ana f = In. fmap (ana f) . f
>
> showF :: Term -> String
> showF = cata alg
>   where
>     alg (IntConstF x) = show x
>     alg (PlusF x y) = "(" ++ x ++ "+" ++ y ++ ")"
>     alg (MultF x y) = "(" ++ x ++ "*" ++ y ++ ")"

Now we can convert ints into a representation in our language just using 2’s and 1’s.

> toBin :: Int -> Term
> toBin = ana coAlg
>   where
>     coAlg :: Int -> TermF Int
>     coAlg 0 = IntConstF 0
>     coAlg 1 = IntConstF 1
>     coAlg 2 = IntConstF 2
>     coAlg n | n `mod` 2 == 0 = MultF 2 (n `div` 2)
>     coAlg n | otherwise      = PlusF 1 (n-1)

Here’s an example:

*Main> showF \$ toBin 31
"(1+(2*(1+(2*(1+(2*(1+2)))))))"