Ничего не делать при сопоставлении с образцом в OCaml
Когда я программирую функции для деревьев в OCaml, я всегда сталкиваюсь с этой повторяющейся проблемой: когда я добираюсь до листьев дерева, я хотел бы ничего не возвращать, но все же хочу, чтобы моя программа продолжалась.
Чтобы быть более ясным, иногда у меня есть упражнения, которые просят найти конкретный узел
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
Итак, как я могу сказать «ничего не делать» в случае шаблона?
Спасибо !
Ответы 2
Вы должны спросить себя: в третьем случае, как вы узнаете, что первая рекурсия нашла результат? Как отличить это от неудачной рекурсии и что делать в любом случае? Кроме того, что если во всем дереве нет ни одного узла, соответствующего вашему критерию?
Так что "ничего не делать" - это не то, что вы хотите, нужно как-то указать, что ничего не найдено.
Один очевидный способ решить все это — вернуть опцию, которая даст следующий код:
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, когда узел не найден.
Спасибо большое. Я не знал о типе опции в OCaml. Сначала я думал, что ваш код не линейный по количеству узлов, а квадратичный, но на самом деле это не так! Это умно, спасибо за помощь.
Есть два способа взглянуть на это:
1) Когда вы нажимаете Nil в find_node, это означает, что узел не найден. Вы должны вернуть какую-то форму ничего.
1а) Вы возвращаете 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
Таким образом, у вас не будет дела Nil. С другой стороны, тогда нет представления пустого дерева.
Вам нужно закодировать случай «не найден» в типе возвращаемого значения. Я предлагаю вам посмотреть на тип
option. Вам также необходимо проверить значение, возвращаемоеfind_node n lв рекурсивном случае|Node(l, _, r) -> find_node n l; find_node n r.