获得ast的子树

Question

我有一个布尔抽象语法树

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

我想在它上面应用一个函数并获得所有为此函数返回true的子树.

我的尝试:

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 []

我收到一个错误:

错误:变体类型列表没有构造函数Not

也试过这个:

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 []

编译好但永远不会终止!

Answer 1

首先,它不应该编译,因为Bast应该是小写的.

那是因为你list在前两种情况下返回一个类型的值,在后三种情况下返回一个原子.而且,(编译器还没有提到它,但很快就会提到)Not构造函数接受了bast,但是你试图用它来创建它bast list