F #: нужна помощь в обратном порядке

Question

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

type ilist = E | L of int * ilist

Кажется, я не могу найти много помощи при работе со списками вне стандартного типа онлайн ([1; 2; 3])

Я должен написать функцию, которая принимает списки и меняет порядок

например: реверс (L (1, L (2, L (3, E)))) выдаст (L (3, L (2, L (1, E))))

Пока вот мой код:

 let rec reverse l = 
     match l with 
     | E -> failwith "Empty List"
     | L(h, E) -> h
     | L(h, t) -> // append tail and recursive call with rest of list?

 let list = reverse (L(1, L(2, L(3, E))))
 printfn "reversed list: %A" list

Спасибо за любую помощь!

Answer 1

Чего вам не хватает - это удобный способ добавить int к ilist:

let rec append x l =
  match l with
  | E       -> L (x,E)
  | L (h,t) -> L (h,append x t)

printfn "%A" (append 4 list)

Теперь используйте эту функцию в вашем последнем случае совпадения, чтобы добавить h к обратному t:

let rec reverse l = 
  match l with 
  | E       -> E
  | L (h,t) -> append h (reverse t)

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

Также обратите внимание, что ваш второй случай совпадения | L(h, E) -> h неверен, поскольку он возвращает int вместо ilist. Но это все равно не нужно, поэтому просто удалите его. Вместо этого список синглтона L (h,E) будет сопоставляться с | L (h,t) -> ..., что, в свою очередь, рекурсивно соответствует t с | E -> E.

Вот рабочий пример: https://repl.it/repls/PhonyAdventurousNet