Дерево значений опций OCaml

Question

У меня есть задача написать функцию с типом ‘a btree -> ‘a option list, которая хранит данное дерево в списке элементов типа ‘a option в постфиксном заказе (по расписанию).

Внутренние узлы будут представлены None, внешние узлы (листья) со значением x будут представлены Some x.

До сих пор это было легко сделать для листьев, но как положить его в 'a option list?

type 'a btree = L of 'a | N of 'a btree * 'a btree ;; 

let rec store t = 
    match t with 
     | L x -> Some x 
     | N (a,b) -> None ??? 
;; 

Второй случай соответствия, который я знаю, неверен, но как его решить?

Answer 1

Если вы посмотрите на свой первый случай, вы увидите, что он тоже не совсем там; он возвращает 'a option, но вы хотите, чтобы функция возвращала 'a option list.

Очевидно, вы будете возвращать список, так что исправить, что первый:

let rec store = function 
    | L x -> [Some x] 
    | N (a,b) -> [None] (* ??? *) 

Теперь давайте исправим второй случай; мы хотим, чтобы добавить None к нашей продукции, но до этого, мы хотим, чтобы узлы наших поддеревьев:

let rec store = function 
    | L x -> [Some x] 
    | N (a,b) -> (store a) @ (store b) @ [None] 

@ имеет тип

'a list -> 'a list -> 'a list 

т.е. он соединяет списки вместе. Мы хотим присоединиться к списку результатов из левого поддерева, затем правого, а затем, наконец, результата для этого внутреннего узла.

Answer 2

В случае, если кто-то заинтересован в этом уточнении, можно сделать немного лучше, по сравнению с решением Len, путем нарезания дополнительного параметра аккумулятора.

Идея заключается в том, чтобы перейти от функции store : 'a btree -> 'a option list, которая принимает дерево и составить список к функции store' : 'a btree -> 'a option list -> 'a option list, который добавляет элемент дерева к списку существующих, переданный в качестве параметра.

let rec store' t acc = match t with 
    | L x -> Some x :: acc 
    | N (a, b) -> 
    store' a (store' b (None :: acc)) 

С этим определением, элементы добавляются лишь один раз в окончательном списке результатов, вместо того, чтобы сначала используется для создания временного store a списка, а затем добавляется во второй раз к конечному результату через оператор (@).

порядок параметр важен, т.к. запись t перед тем acc дает интуицию конечного порядка элементов в списке: элементы t будут перед тем элементы уже присутствуют в acc. Это позволяет считать случай N вполне естественно: легко видеть, что результат сначала будет содержать элементы a, затем b, затем None, затем acc.

Наконец, вы можете, конечно, определить store в терминах store':

let store t = store' t [] 

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

let store t = 
    let rec store t acc = match t with 
    | L x -> Some x :: acc 
    | N (a, b) -> 
     store a (store b (None :: acc)) 
    in store t [] 

конечно, будьте это определение «лучше», чем у Лена дает то, что ваш критерий оценки. Решение Len более короткое, более легкое для чтения и более точно сопоставляет исходную проблему.

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