Получить поддеревьев из аст

Question

У меня есть логическое абстрактное синтаксическое дерево

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

и я хочу, чтобы применить на него функции и получить все поддеревья, которые возвращают верно для этой функции.

Моя попытка:

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

Я получаю сообщение об ошибке:

Error: The variant type list has no constructor 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

Answer 2

Вот что я бы, наверное, написать в качестве первой рабочей попытки:

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

Некоторые замечания:

• Вам не нужно писать exp = true для любого выражения exp (в вашем случае это было f tree), так как это подразумевает, чтоимеет тип boolean и полученное значение будет точно такой же (просьба написать таблицу истинности, чтобы проверить, что)
• я заменил mylist@[tree] с tree::mylist, который быстрее, но будет производить список в обратном порядке. Если вы заботитесь об этом заказе и хотите иметь последнее тестируемое дерево в конце списка, просто примените List.rev к результату (конечно, вы можете включить его в тело findtrees)
• Поскольку ваше дерево представляет собой булево выражение , возможно, лучший способ решить проблему, которую вы пытаетесь решить.