CODEWITHSUNDEEP
functional-programmingocamlabstract-syntax-tree
eternalStudent
eternalStudent

Reputation: 484

Get the subtrees of an ast

I have a boolean abstract syntax tree

type bast =
    True
  | False
  | Not of bast 
  | Or of bast * bast 
  | And of bast * bast

and I want to apply on it a function and get all the subtrees that return true for this function.

My try:

let findtrees f (ast: bast ) =
    let rec findtree (tree: bast ) (mylist: bast list) = match tree with
        | True ->
            if (f tree)=true then mylist@[tree] else []
        | False ->
            if (f tree)=true then mylist@[tree] else []
        | Not e     ->  Not (findtree e subtrees)
        | And (e1,e2) ->  And (findtree e1 mylist, findtree e2 mylist)
        | Or  (e1,e2) ->  Or  (findtree e1 mylist, findtree e2 mylist)
    in findtree ast []

I get an error:

Error: The variant type list has no constructor Not

Tried also with this:

let findtrees f (ast: bast) =
    let rec findtree (tree: bast) (mylist: bast list) = match tree with
          (True|False) -> mylist
        | subtree ->
            if (f subtree)=true then
                mylist@[subtree]
            else
                select_tree subtree mylist
    in findtree ast []

Compiles fine but never terminates!

Upvotes: 1

Views: 357

Answers (2)

didierc
didierc

Reputation: 14730

Here's what I would probably write as a first working attempt:

let findtrees f (ast: bast ) =
  let rec findtree tree mylist = 
    let mylist = if f tree then tree::mylist else mylist in
    match tree with
      | True| False -> mylist
      | Not e -> findtree e mylist
      | Or (e1,e2)
      | And (e1,e2) ->  findtree e2 @@ findtree e1 mylist
  in findtree ast []

Some remarks:

  • You don't need to write exp = true for any expression exp (in your case it was f tree), since it implies that that exp is of type boolean and the resulting value would be exactly the same (please write the truth table to verify that)
  • I replaced mylist@[tree] with tree::mylist which is faster, but will produce a list in reverse order. If you care about that order, and wish to have the latest tested tree at the end of the list, simply apply List.rev to the result (you may of course include that in the body of findtrees)
  • Because your tree represents boolean expressions, there's perhaps a better way of handling the problem you are trying to solve.

Upvotes: 1

ivg
ivg

Reputation: 35210

first of all, it shouldn't compile, since Bast should be lowercased.

That is because you return a value of type list on first two cases, and an atom on a latter three. Moreover, (compiler didn't mentioned it yet, but will soon) Not constructor accepts a bast, but you're trying to create it with a bast list

Upvotes: 5

Related Questions