Monday, June 05, 2006

The Play class

One useful trick I've found when manipulating data structures is the Play class, which I created to "play" with various data structures. Often a data structure will contain the same type within it - for example:

data Expr = Sum [Expr]
| Literal Int
| Div Expr Expr

Now I define a Play class as:

class PlayExpr a where
mapExpr :: (Expr -> Expr) -> a -> a
allExpr :: a -> [Expr]

mapExpr just maps over every element in the data structure, and allExpr gives every element back, this makes lots of things quite easy.

For example, with these properties you can test if there are any negative literals in the list:

[n | Literal n <- allExpr x, n < 0]

And operations like replacing Sum [x] with x can be coded easily as follows:

mapExpr f x
f (Sum [x]) = x
f x = x

This could be done as just two functions, not in a class, but by putting it in a class you can add instances for [x] (a,b) etc. And also, if this expression is embeded in a larger data structure, you can then traverse that larger data structure in exactly the same way.

I have used this quite extensively in some of my code.


Anonymous said...

If you want to write that shorter, why not try this:

import Data.Generics

literals :: (Int -> Bool) -> Expr -> [Int]
literals = listify

allExpr :: Expr -> [Expr]
allExpr = listify (const True)

mapExpr :: Typeable a => (a -> a) -> Expr -> Expr
mapExpr f = everywhere (mkT f)

data Expr
= Sum [Expr]
| Literal Int
| Div Expr Expr
deriving (Show,Typeable,Data)

This way, you can write your example like this:
literals (<0) x
and the second can stay as it is.
It's not Haskell98, but it sure rocks.

Neil Mitchell said...

That is pretty impressive, I'll have to take a look at Data.Generics!