[Haskell-beginners] search a tree
Stephen Tetley
stephen.tetley at gmail.com
Thu Feb 25 16:27:27 EST 2010
Hi John
The simplest way to extract variable names is probably with direct
recursion and an accumulator - program below.
Often though when working with syntax trees, you want do various
things on them that share the same traversal behaviour. At this point
a 'Generics' library is useful - however they are fairly complicated
to use. Strafunski/StrategyLib was the original and best documented
(probably not so easy to use these days as it there isn't a ready-made
distribution), but there is also: Uniplate (relatively simple and well
documented), Data.Generics aka SYB ('Scrap Your Boilerplate' - rather
complicated but well documented, somewhat 'standard') and others
generally with less documentation (e.g. Multirec, KURE).
There's a paper 'Design Patterns for Functional Strategic Programming'
by Joost Visser and Ralf Lammel (the a with umlauts) that is as good
start as any.
Best wishes
Stephen
module ExtractVars where
data Expression = Val Double
| Add Expression Expression
| Subtract Expression Expression
| Multiply Expression Expression
| Divide Expression Expression
| Var String
| Let String Expression Expression
extractVars :: Expression -> [String]
extractVars expr = step expr [] where
step (Let s e1 e2) acc = step e2 (step e1 (s:acc))
step (Add e1 e2) acc = step e2 (step e1 acc)
step (Subtract e1 e2) acc = step e2 (step e1 acc)
step (Multiply e1 e2) acc = step e2 (step e1 acc)
step (Divide e1 e2) acc = step e2 (step e1 acc)
step (Var _) acc = acc
step (Val _) acc = acc
demo1 = extractVars (Let "x" (Val 4) (Multiply (Var "x") (Val 4.0)))
More information about the Beginners
mailing list