вложенные списки в OCaml

Question

Я новичок в OCaml и определили вложенные списки следующим образом:

type 'a node = Empty | One of 'a | Many of 'a node list 

Теперь я хочу, чтобы определить функцию обертывания, которая надстроена квадратные скобки первых членов порядка вложенного списка. Напр. wrap (Многие [one a; Many [c; d]; один b; один e;]) возвращает Many [Many a; Empty]; Многие [Многие [с, d]; Empty]; Многие [б; Empty]; Многие [е; Empty]]. Вот мой код такой же:

let rec wrap list = function 
     Empty -> [] 
     | Many[x; y] -> Many [ Many[x; Empty]; wrap y;];; 

Но я получаю сообщение об ошибке в последнем выражении: Это выражение имеет тип «узел, но выражение было ожидать от типа» список б. Пожалуйста помоги.

Answer 1

Два ваших совпадения не возвращают значения одного и того же типа. Первый оператор возвращает список b; второй оператор возвращает «узел». Чтобы пройти мимо проверки типа, вам нужно будет изменить первый оператор следующим образом: Empty -> Empty.

Вторая проблема (с которой вы столкнетесь в следующем) заключается в том, что ваш рекурсивный вызов не получает значение правильного типа. wrap : 'a node -> 'a node, но y : 'a node list. Один из способов решения этой проблемы - заменить выражение на wrap (Many y).

Также будет проблема в том, что ваша текущая функция предполагает, что список Many содержит только два элемента. Я думаю, что вы хотите сделать это Many (x::y). Это соответствует x как глава списка, а y - как хвост. Тем не менее, вам понадобится случай для обработки Many ([]), чтобы избежать бесконечной рекурсии.

Наконец, общая форма вашей функции поражает меня как нечто необычное. Я бы заменил function Empty -> ... на match list with | Empty -> ....