
Hi All, I have an expression which contains several different let statements let x = 4*5 and let Y = 6+4 for example. What I want to do is traverse the tree and just return the variables. In other words I just want it to return a list of all the variables in a tree. I have a function for Var String. So would it be something like given a String -> [String] or is this expression ->String (gives back a string) Whats the best way to check or compare? Jon

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)))
participants (2)
-
John Moore
-
Stephen Tetley