Рекурсивные функции и сопоставление с образцом в ocaml - PullRequest
Новая
       8

Рекурсивные функции и сопоставление с образцом в ocaml

0 голосов
/ 22 сентября 2018

Следующий фрагмент кода взят с официального сайта OCaml : 

# let rec compress = function
| a :: (b :: _ as t) -> if a = b then compress t else a :: compress t
| smaller -> smaller;;
val compress : 'a list -> 'a list = <fun>

Вышеприведенная функция «сжимает» список с последовательными дублирующимися элементами, например: 

# compress ["a";"a";"a";"a";"b";"c";"c";"a";"a";"d";"e";"e";"e";"e"];;

- : string list = ["a"; "b"; "c"; "a"; "d"; "e"]

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

Например, где находится базовый вариант?Это smaller -> smaller?Я знаю, smaller - это переменная или идентификатор, но что он возвращает (возвращает даже правильный термин в OCaml для того, что здесь происходит)?

Я знаю, что списки в OCaml являются односвязными, поэтомуМне также интересно, генерируется ли новый список, или элементы существующего списка вырезаются?Поскольку OCaml функционален, я склонен думать, что списки не являются изменяемыми - это правильно?Если вы хотите изменить список, вам, по сути, нужно создать новый список с элементами, которые вы хотите добавить (или с элементами, которые вы хотите обрезать, отсутствуют).Это правильное понимание?

1 Ответ

0 голосов
/ 22 сентября 2018

Да, базовый случай таков: 

| smaller -> smaller

Первый шаблон выражения match соответствует любому списку длиной 2 или более.(Было бы хорошо убедиться, что вы понимаете, почему это так.)

Поскольку OCaml сопоставляет шаблоны по порядку, базовый случай сопоставляет списки длин 0 и 1. Именно поэтому программист выбрал имя smaller.Они думали: «Это какой-то меньший список».

Части выражения соответствия выглядят в общем так: 

| pattern -> result

Любые имена в шаблоне связаны с частями значениясоответствует шаблону (как вы говорите).Так что smaller привязан ко всему списку.Таким образом, в итоге вторая часть match говорит, что если список имеет длину 0 или 1, результатом должен быть просто сам список.

Списки в OCaml являются неизменяемыми, поэтому это невозможноРезультатом функции будет измененная версия списка.В результате получается новый список, если только этот список не является коротким списком (длиной 0 или 1).

Итак, то, что вы говорите об неизменности списков OCaml, совершенно верно.

...