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