Как сделать так, чтобы функция возвращала список с плавающей точкой? - PullRequest
Новая
       102

Как сделать так, чтобы функция возвращала список с плавающей точкой?

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

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

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

let medianInTree (lst: float Tree) :float list=
    let rec medianInTree' (a : float Tree) acc = 
        match lst with
        | Leaf(n) -> n :: acc
        | Branch(Leaf(xx), Leaf(xs)) -> xx :: [xs] 
        | Branch(Leaf(x), Branch(Leaf(xx), Leaf(xs))) -> 
               let acc = medianInTree'(Leaf(x)) acc
               medianInTree' (Branch(Leaf(xx), Leaf(xs))) acc 
        | Branch(_, _) -> []
    medianInTree' lst []

Вопрос: medianInTree (Branch(Leaf(2.0), Branch(Leaf(3.0), Leaf(5.0))))

Я хочу этот результат: [2,0; 3,0; 5,0]

Ответы [ 2 ]

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

используя аккумулятор, вы можете сделать что-то вроде этого: 

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

Но при этом рекурсивный вызов для обработки левой ветви не является хвостовой рекурсивной. Чтобы обеспечить рекурсию хвоста при обработке древовидных структур, вы должны использовать продолжения . 

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

Что можно упростить как: 

let flatten 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
0 голосов
/ 11 ноября 2018

Ваша основная ошибка использует match с lst вместо a.Я сделал это немного проще. 

let medianInTree (lst: float Tree) :float list=
    let rec medianInTree' (a : float Tree)= 
        match a with
        | Leaf(n) -> [n]
        | Branch(l, r) -> (medianInTree' l) @ (medianInTree' r)
    medianInTree' lst
...