Написание функции добавления списка в OCaml

Question

Я определил пользовательский тип списка как часть домашнего упражнения.

type 'a myType =
  | Item of ('a * 'a myType)
  | Empty;;

Я уже сделал 'length', и теперь мне нужна функция 'append'. Моя функция длины:

let length l =
  let rec _length n = function
    | Empty         -> n
    | Item(_, next) -> _length (n + 1) next
  in _length 0 l;;

Но я действительно не знаю, как сделать функцию добавления.

let append list1 list2 = (* TODO *)

Я не могу использовать модуль списка, поэтому я не могу использовать :: или @.

Answer 1

Полагаю, мои комментарии становятся слишком длинными, чтобы их можно было считать простыми комментариями. Я не очень хочу отвечать, я просто хочу дать подсказки. В противном случае это побеждает цель.

Чтобы повторить мои намеки:

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

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

с. Далее вам нужно знать, как разбить непустой регистр на более мелкое добавление. проблема.

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

let list1 k =
    Item (k, Empty)

Один из способов думать об этом - каждый раз, когда в вашем коде появляется Item, вы создаете новый элемент. Item называется конструктором , потому что он создает элемент.

Надеюсь, это поможет.

Answer 2

Ваша структура - это список, поэтому вы должны начать с определения значения nil, которое является пустым списком, и функции cons head tail, которая добавляет элемент head перед списком tail.

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