[Haskell-beginners] search a tree

[Stephen Tetley]

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)))