Два разных типа рекурсивных функций OCaml - PullRequest
Новая
       47

Два разных типа рекурсивных функций OCaml

0 голосов
/ 06 октября 2018

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

Для простоты предположим, что T - это двоичное дерево.Поэтому я буду использовать следующий тип: 

type 'a tree = Empty | 'a * 'a tree * 'a tree

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

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

Итак, у нас просто есть: 

let rec nodes = function
    |Empty -> 0 (*it's ok we are done here*)
    |Node(_,l,r) -> 1 + nodes l + nodes r

Что очень хорошо, так это то, что когда информация может быть вычислена слева направо, тогда сопоставление с образцом в OCaml является очень сильныминструмент и информацию I можно рассчитать простым способом.Итак, в общем, у нас есть: 

let rec get_information = function
    | Empty     -> (*here we are done so we return a constant value*)
    |Node(_,l,r)-> (*here we apply recusrively the function to the left and right tree*)

Теперь вот моя проблема.Допустим, I - это информация, которая не может быть рассчитана слева направо, но справа налево.Таким образом, это означает, что для получения информации I нам нужно начинать с листьев дерева и рекурсивно расширяться до вершины, и мы закончим, только когда доберемся до корня бинарного дерева (поэтому конечный случай - это когда мыдобраться до корня двоичного дерева, а не листьев).

Например, скажем, информация I такова: «двоичное дерево имеет свойство, которое для каждого узла равно количеству узлов в его левой части».поддерево строго превосходит количество узлов в его правом поддереве ".Если мы хотим решить это за линейное время, то нам нужно начинать с листьев и рекурсивно тратить деньги наверх (обратите внимание, что я не обязательно хочу решить проблему).

Так что для меня этосложно написать функцию, которая получает информацию I, когда I - это информация справа налево (она должна начинаться с листьев и расширяться до вершины).Напротив, сопоставление с образцом идеально, когда информация представляет собой информацию слева направо.

Итак, мой вопрос, как это сделать, когда нам нужно написать функцию, которая получает информацию I (когда I справа налево)?Существуют ли методы для решения подобных проблем?Можно ли все еще хитро использовать сопоставление с образцом, чтобы получить желаемый результат?

1 Ответ

0 голосов
/ 07 октября 2018

Сопоставление с образцом полезно для написания обоих видов функций.Также могут использоваться функции более высокого порядка, называемые складками.

Во-первых, конкретная версия.Мы хотим знать, является ли дерево наклонным, и если да, то сколько у него узлов.int option будет представлять это хорошо, с None, указывающим на любое не левое наклонное дерево. 

type 'a tree = Empty | Branch of 'a * 'a tree * 'a tree

let rec tree_info = function
  | Empty -> Some 0
  | Branch (_, l, r) ->
    match tree_info l, tree_info r with
    | Some x, Some y when x >= y -> Some (x + y + 1)
    | _ -> None

let is_left_leaning tree =
  match tree_info tree with
  | Some _ -> true
  | None -> false

(Обратите внимание, что условие x >= y не «строго больше, чем», но это преднамеренно; x > y - плохой выбор. Я оставлю выяснение, почему, как упражнение.)

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

let rec foldr empty branch = function
  | Empty -> empty
  | Branch (x, l, r) ->
    branch x (foldr empty branch l) (foldr empty branch r)

Обратите внимание, чтозначение empty и конструктор Empty имеют одинаковую арность, а значение branch и конструктор Branch имеют одинаковую арность с соответствующими типами аргументов.Это характерно для правильного сгиба.

Учитывая foldr, мы можем легко определить map: 

let map f tree =
  foldr Empty (fun x l r -> Branch (f x, l, r)) tree

Или, конечно, 'tree_info': 

let tree_info tree =
  foldr
    (Some 0)
    (fun _ l r ->
       match l, r with
       | Some x, Some y when x >= y -> Some (x + y + 1)
       | _ -> None)
    tree

Это альтернатива сопоставлению с образцом в конструкторах tree.

...