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
where
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.
2 comments:
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.
That is pretty impressive, I'll have to take a look at Data.Generics!
Post a Comment