Ничего не делать для сопоставления с образцом в OCaml

Question

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

Чтобы быть более ясным, иногда у меня есть упражнения, которые просят найти конкретный узел n , поэтому я могу сделать следующее: (для простоты я делаю это здесь на двоичных деревьях):

let rec find_node n tree = match tree with 
|Nil   ->  (* I don't want my program to stop here but then what can I return ?*) 
|Node(l, k, r) as t when k =n -> t
|Node(l, _, r) -> find_node n l; find_node n r

Я использую следующее представление бинарных деревьев:

type b_tree = Nil | Node of b_tree * int * b_tree 

В общем, я бы хотел, чтобы моя программа продолжала работать до тех пор, пока не найдет то, что хочет, но, поскольку у функции в OCaml есть только один тип возврата, я не могу сделать что-то вроде:

let rec find_node n tree = match tree with 
|Nil   ->  ()  (*returning unit type here*)
|Node(l, k, r) as t when k =n -> t
|Node(l, _, r) -> find_node n l; find_node n r

Так как я могу сказать "ничего не делать" в случае с образцом?

Спасибо!

Answer 1

Вы должны спросить себя: в третьем случае, как вы узнаете, что первая рекурсия дала результат?Как вы отличаете это от неудачной рекурсии и что вы делаете в любом случае?Кроме того, что, если во всем дереве нет узла, отвечающего вашему критерию?

То есть «ничего не делать» - это не то, что вам нужно, вам нужно как-то указать, что ничего не найдено.

OneОчевидный способ решить все это - вернуть опцию, которая выдаст следующий код:

let rec find_node n tree =
  match tree with 
  | Nil -> None
  | Node ((_, k, _) as t) when k = n -> Some t
  | Node (l, _, r) ->
    match find_node n l with
    | None -> find_node n r
    | some -> some

Это имеет тип возврата (b_tree * int * b_tree) option, описывающий атрибуты узла, или значение None, когда ни один узел не имеетбыл найден.

Answer 2

Есть два способа взглянуть на это:

1) Когда вы нажимаете Nil в find_node, это означает, что ни один узел не был найден. Вы должны вернуть какую-то форму ничего.

1a) Вы возвращаете None, что также означает, что вы должны вернуть Some x в других случаях. Это API-интерфейс с опциями.

1b) Вы поднимаете Not_found. Это API-интерфейс с исключениями.

Некоторые модули следуют 1a, другие 1b. У некоторых есть подмодули для ароматов или 2 функции, например find_node (исключение) и find_node_opt (опция). Какой вкус вы должны иметь? Это 50% личных предпочтений и 50% вариантов использования. Оба одинаково действительны, и оба имеют преимущества с другой в зависимости от варианта использования.

2) Ваш тип данных виноват

Я видел деревья, определенные как

type b_tree = Leaf of int | Node of b_tree * int * b_tree 

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