Deriving pleasure from GHC 6.12.1

GHC 6.12.1 has been out for a few months now, and things are starting to come together in terms of library compatibility. I look forward to the next release of the Haskell Platform which will include 6.12.

Here’s a totally sweet new feature in GHC 6.12.1 which you might not be aware of (I wasn’t aware of it for quite a while after the release). Let’s suppose I’ve defined the following data type of n-way trees with data at the leaves:

> data Tree a = Leaf a | Node [Tree a]
>   deriving Show

For example, here’s an example value of this type:

> t :: Tree Integer
> t = Node [Leaf 3, Leaf 7, Node [Leaf 4, Leaf 8], Leaf 1]

Now, suppose we wanted to do something to every leaf in a tree, (say) increment all the values by one. Of course, the best way to do this is to make Tree an instance of Functor, like so:

> instance Functor Tree where
>   fmap f (Leaf x)  = Leaf (f x)
>   fmap f (Node ts) = Node (fmap (fmap f) ts)

Now we can increment every leaf in t:

ghci> fmap (+1) t
Node [Leaf 4,Leaf 8,Node [Leaf 5,Leaf 9],Leaf 2]

OK, that wasn’t so hard. But… that Functor instance was awfully boring to write (even if it wasn’t really that long). In a sense it is "obvious" what the Functor instance should do just from looking at the definition of Tree. Couldn’t the Functor instance be automatically generated somehow?

It certainly can, and in the past the answer would have been "use a tool like DrIFT or Derive". However… GHC can now do it for you! All we need is to enable the DeriveFunctor extension, and add Functor to the deriving clause after the definition of our data type. Like this:

> {-# LANGUAGE DeriveFunctor #-}
> 
> data Tree a = Leaf a | Node [Tree a]
>   deriving (Show, Functor)
> 
> t :: Tree Integer
> t = Node [Leaf 3, Leaf 7, Node [Leaf 4, Leaf 8], Leaf 1]

And voila! No silly boilerplate. It Just Works:

ghci> fmap (+1) t
Node [Leaf 4,Leaf 8,Node [Leaf 5,Leaf 9],Leaf 2]

And that’s not all! GHC can automatically derive Foldable instances for us as well. We just need to add one more extension, and import Data.Foldable. Let’s import Data.Monoid too, just for fun.

> {-# LANGUAGE DeriveFunctor, DeriveFoldable #-}
> 
> import Data.Foldable
> import Data.Monoid
> 
> data Tree a = Leaf a | Node [Tree a]
>   deriving (Show, Functor, Foldable)
> 
> t :: Tree Integer
> t = Node [Leaf 3, Leaf 7, Node [Leaf 4, Leaf 8], Leaf 1]

Behold:

ghci> foldMap Sum t
Sum {getSum = 23}
ghci> foldMap (:[]) t
[3,7,4,8,1]

Sweet! We can add up all the leaves in a tree, or flatten a tree into a list, and a ton of other useful operations besides, with pretty much zero work on our part.

But wait! There’s even more! GHC can derive Traversable too.

> {-# LANGUAGE DeriveFunctor, DeriveFoldable, DeriveTraversable #-}
> 
> import Data.Foldable
> import Data.Monoid
> import Data.Traversable
> 
> data Tree a = Leaf a | Node [Tree a]
>   deriving (Show, Functor, Foldable, Traversable)
> 
> t :: Tree Integer
> t = Node [Leaf 3, Leaf 7, Node [Leaf 4, Leaf 8], Leaf 1]
ghci> traverse (\x -> if x > 6 then [x-1, x] else [x]) t
[ Node [Leaf 3,Leaf 6,Node [Leaf 4,Leaf 7],Leaf 1]
, Node [Leaf 3,Leaf 6,Node [Leaf 4,Leaf 8],Leaf 1]
, Node [Leaf 3,Leaf 7,Node [Leaf 4,Leaf 7],Leaf 1]
, Node [Leaf 3,Leaf 7,Node [Leaf 4,Leaf 8],Leaf 1]
]

A wesome! This example is a bit silly, perhaps, but I’ll leave you to come up with more interesting uses of traverse.

I should point out that this certainly doesn’t replace tools like DrIFT and Derive, which can do tons of other things as well. But having baked-in support for these very common cases is sure convenient!

Advertisements

About Brent

Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in haskell. Bookmark the permalink.

2 Responses to Deriving pleasure from GHC 6.12.1

  1. Thanks for writing the type class o pedia.

    Do these free theorems go away now that you all have implemented dependent types? From what I’m learning and understanding of Bask so far it seems like the surprising parts of Haskell to someone more familiar with the mathematical terminology stem from the fact that there is only one base type?

    • Brent says:

      No, free theorems don’t go away in general. It’s just that free theorems may not exist (or we may not know the right way to explain/derive them) for types involving more advanced extensions.

      I am not sure what you mean about surprising parts of Haskell stemming from the fact that there is only one base type. Can you give an example? I am not even sure what you mean by Haskell having “only one base type”, that does not really make sense to me. Do you mean one base *kind*?

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 )

Google+ photo

You are commenting using your Google+ 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 )

w

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.