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)))))))"
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s