Дерево в упорядоченный список с хвостовой рекурсией - PullRequest
Новая
       52

Дерево в упорядоченный список с хвостовой рекурсией

0 голосов
/ 15 декабря 2018

Я больше часа сижу над проблемой и не могу найти решения.У меня есть этот тип данных: type 'a tree = Empty | Node of 'a * 'a tree * 'a tree

И я должен найти функцию, которая преобразует данное дерево в упорядоченном списке.Также нет такого инварианта, как если бы левый ребенок был меньше правого.Я уже нашел «нормальное» рекурсивное решение, но не хвостовое рекурсивное решение.Я уже думал о создании неупорядоченного списка и сортировке его с помощью List.sort, но при этом используется сортировка слиянием, которая не является хвостовой рекурсивной.Может быть, у кого-то есть хороший совет.

Спасибо!

1 Ответ

0 голосов
/ 16 декабря 2018

Если вы хотите пройти по дереву в порядке и вернуть список , это означает, что наша функция inorder должна иметь тип 'a tree -> 'a list. 

let rec inorder t =
    match t with
      | Empty -> []
      | Node (v, l, r) -> List.append (inorder l) (v :: (inorder r)) (* ! *)

Однако List.append находится в положении хвоста, а не inorder.Другая проблема - у нас два звонка на inorder.Если мы поместим inorder l в хвостовое положение, inorder r не сможет оказаться в хвостовом положении - и наоборот.

Оптимальный способ обойти эту проблему - это стиль продолжения продолжения.Мы берем нашу функцию выше и преобразуем ее в вспомогательную функцию с дополнительным параметром для нашего продолжения, return

(* convert to helper function, add an extra parameter *)
let rec loop t return =
    match t with
        | Empty -> ...
        | Node (v, l, r) -> ...

Продолжение представляет «что делать дальше» , поэтому вместо этогоотправляя значения непосредственно из нашей функции, мы должны вместо этого передать их в продолжение.Это означает, что для случая Empty мы будем return [] - вместо простого []

let rec loop t return =
    match t with
        | Empty -> return []
        | Node (v, l, r) -> ...

Для случая Node (v, l, r), теперь, когда у нас есть дополнительный параметр, мы можем написать наш собственныйпродолжение, информирующее loop, что делать дальше.Итак, чтобы построить наш отсортированный список, нам понадобится loop l, затем loop r (или наоборот), , затем , мы можем append их.Мы напишем нашу программу следующим образом. 

let rec loop t return =
    match t with
        | Empty -> return []
        | Node (v, l, r) ->
            loop l ... (* build the left_result *)
            loop r ... (* build the right_result *)
            return (List.append left_result (v :: right_result))

На следующем шаге мы заполним фактический лямбда-синтаксис для продолжений. 

let rec loop t return =
    match t with
        | Empty -> return []
        | Node (v, l, r) ->
            loop l (fun left ->
            loop r (fun right ->
            return (List.append left (v :: right))))

Наконец, мы определимinorder, который является вызовом loop с продолжением по умолчанию, identity. 

let identity x =
    x

let inorder t =
    let rec loop t return =
        match t with
            | Empty -> return []
            | Node (v, l, r) ->
                loop r (fun right ->
                loop l (fun left ->
                return (List.append left (v :: right))))
    in
    loop t identity

Как видите, loop r (fun right -> ...) находится в хвостовой позиции для ветви Node.loop l (fun left -> ...) находится в хвостовой позиции первого продолжения.И List.append ... находится в хвостовой позиции второго продолжения.Если List.append является хвостовой рекурсивной процедурой, inorder не будет наращивать стек.

Обратите внимание, использование List.append может быть дорогостоящим выбором для больших деревьев.Наша функция вызывает его один раз за Node.Можете ли вы придумать способ избежать этого?Это упражнение оставлено для читателя.

...