Упорядочить обход дерева и применить данную функцию ко всем узлам - PullRequest
Новая
       16

Упорядочить обход дерева и применить данную функцию ко всем узлам

2 голосов
/ 05 марта 2019

Я написал функцию обхода дерева в порядке: 

let rec inOrder (tree: BinTree<'a>) : 'a list =
    match tree with
    | Leaf -> []
    | Node(x,l,r) -> (inOrder l) @ [x] @ (inOrder r)

Теперь я хочу использовать эту функцию, чтобы «отобразить» все заметки и применить функцию, заданную в качестве параметра.Он должен взять функцию и дерево, а затем вернуть дерево.Это то, что у меня есть: 

let mapInOrder f t = 
    inOrder t
    |> Map.ofList

Например, если я дам функции этот ввод: 

mapInOrder float (Node(1,Node(2,Leaf,Leaf),Node(3,Leaf,Leaf)));;

Я хочу вывод: 

(Node(1.0,Node(2.0,Leaf,Leaf),Node(3.0,Leaf,Leaf)))

Ответы [ 3 ]

4 голосов
/ 05 марта 2019

Чтобы отобразить функцию через List, используйте функцию List.map: 

let mapInOrder f t = 
    inOrder t
    |> List.map f

Но эта функция выдаст список в качестве вывода. Ваш пример выдаст: 

[ 1.0 ; 2.0 ; 3.0 ]

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

1 голос
/ 05 марта 2019

Вот с чем я пришел: 

type BinTree<'a> =
    | Leaf 
    | Node of x :'a  * l:BinTree<'a> * r:BinTree<'a>

let rec inOrder (tree: BinTree<'a>) : 'a list =
    match tree with
    | Leaf -> []
    | Node(x,l,r) -> (inOrder l) @ [x] @ (inOrder r)

let exampleTree = (Node(1,Node(2,Leaf,Leaf),Node(3,Leaf,Leaf)));;

let mapInOrder tree mapFunc = 
    tree
        |> inOrder 
        |> List.map mapFunc

let res = mapInOrder exampleTree double
//val res : double list = [2.0; 1.0; 3.0] <-------------- result of your current try

let rec copyAndMapInOrder<'b> (tree: BinTree<'a>) mapFunc : BinTree<'b> =
    match tree with
    | Leaf -> Leaf
    | Node(x,l,r) -> Node((mapFunc x), (copyAndMapInOrder l mapFunc), (copyAndMapInOrder r mapFunc))

let res2 = copyAndMapInOrder exampleTree double
//val res2 : BinTree<double> = Node (1.0,Node (2.0,Leaf,Leaf),Node (3.0,Leaf,Leaf)) <-- expected result

Этот код - только моя реализация того, что @AMieres предлагает выше.

0 голосов
/ 06 марта 2019

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

let rec fold  (e: 'b) (f : 'a -> 'b -> 'b -> 'b) (tree: BinTree<'a>) : 'b =
    match tree with
    | Leaf -> e
    | Node(x,l,r) -> f x (fold e f l) (fold e f r)

let inorderTree  f t = fold Leaf (fun x l r -> Node (f x, l, r)) t
let inorderList  f t  = fold [] (fun x l r -> l @ [f x] @ r) t
let inorderList' t  = inorderList id t
let inorderTree' t  = inorderTree id t
...