F # дерево уходит в список с продолжением хвостовой рекурсии - PullRequest
Новая
       20

F # дерево уходит в список с продолжением хвостовой рекурсии

0 голосов
/ 10 ноября 2018

У меня есть дерево типов, у которого есть ветви и листья. Я хотел бы получить список значений листьев. Пока я могу только сосчитать ветви.

Мое дерево: 

type 'a tr =
  | Leaf   of 'a
  | Branch of 'a tr * 'a tr

И мой код: 

let getList (tr:float tr)=
    let rec toList tree acc =
        match tree with
        | Leaf _ -> acc 0
        | Branch (tl,tr) -> toList tl (fun vl -> toList tr (fun vr -> acc(vl+vr+1)))
    toList tr id

Введите: 

 let test=Branch (Leaf 1.2, Branch(Leaf 1.2, Branch(Branch(Leaf 4.5, Leaf 6.6), Leaf 5.4)))
 getList test

В результате я хотел бы получить список: 

[1.2; 1.2; 4.5; 6.6; 5.4]

Я пробовал некоторые варианты, похожие на это, но безуспешно. 

  | Branch (tl,tr) -> toList tl (fun vl -> toList tr (fun vr -> (vl::vr)::acc))
    toList tr []

Любая помощь будет оценена.

Ответы [ 2 ]

0 голосов
/ 10 ноября 2018

Обратите внимание, что ваш тип дерева не может представлять узел только с одним дочерним узлом. Тип должен быть: 

type Tree<'T> =
    | Leaf of 'T
    | OnlyOne of Tree<'T>
    | Both of Tree<'T> * Tree<'T>

Чтобы использовать хвостовую рекурсию с продолжением, используйте функцию продолжения , а не acc umulator: 

let leaves tree =
    let rec collect tree cont =
        match tree with
        | Leaf x -> cont [x]
        | OnlyOne tree -> collect tree cont
        | Both (leftTree, rightTree) ->
            collect leftTree (fun leftAcc ->
                collect rightTree (fun rightAcc ->
                    leftAcc @ rightAcc |> cont))
    collect tree id

P / S: ваше наименование не очень хорошее: tr имеет слишком много значений.

0 голосов
/ 10 ноября 2018

Это связано с вашей функцией продолжения (acc), чья подпись (int -> 'a) Если вы хотите получить плоский список, подпись функции продолжения должна быть ('a список ->' b) 

let getList tree =
    let rec toList tree cont =
        match tree with
        | Leaf a -> cont [a]
        | Branch (left, right) -> 
            toList left (fun l -> 
                toList right (fun r -> 
                    cont (l @ r)))
    toList tree id

Редактировать; это должно быть более эффективным 

let getList tree = 
    let rec toList tree cont acc =
        match tree with 
        | Leaf a               -> cont (a :: acc)
        | Branch (left, right) -> toList left (toList right cont) acc
    toList tree id [] |> List.rev
...