Как мне написать функцию для создания круговой версии списка в OCaml?

Можно создавать бесконечные циклические списки, используя let rec, не прибегая к изменяемым ссылкам:

let rec xs = 1 :: 0 :: xs ;;

Но могу ли я использовать эту же технику для написания функции, которая получает конечный список и возвращает его бесконечную циклическую версию? Я пытался писать

let rec cycle xs = 
    let rec result = go xs and
            go = function
              | [] -> result
              | (y::ys) -> y :: go ys in
    result
;;

Но получил следующую ошибку

Ошибка: этот вид выражения не разрешен как правая часть `let rec'

Источник

4 ответа

Решение

У вашего кода есть две проблемы:

  • result = go xs в незаконной форме для let rec
  • Функция пытается создать цикл путем некоторого вычисления, которое попадает в бесконечный цикл, вызывая переполнение стека.

Приведенный выше код отклонен компилятором, поскольку вы не можете написать выражение, которое может вызвать рекурсивные вычисления в правой части let rec (см. Ограничения let rec в OCaml).

Даже если вы решите проблему, у вас все еще есть проблема: cycle не заканчивает работу

let rec cycle xs =
  let rec go = function
    | [] -> go xs
    | y::ys -> y :: g ys
  in
  go xs;;

cycle [1;2];;

cycle [1;2] не удается из-за переполнения стека.

В OCaml, let rec может определить зацикленную структуру только тогда, когда ее определение является "статическим" и не выполняет никаких вычислений. let rec xs = 1 :: 0 :: xs это такой пример: (::) это не функция, а конструктор, который просто создает структуру данных. С другой стороны, cycle выполняет некоторое выполнение кода для динамического создания структуры, и оно бесконечно. Я боюсь, что вы не можете написать такую ​​функцию, как cycle в OCaml.

Если вы хотите ввести некоторые петли в данных, как cycle в OCaml вы можете использовать ленивую структуру, чтобы предотвратить немедленные бесконечные циклы, такие как ленивый список Хаскелла, или использовать мутацию, чтобы сделать цикл заменой. Список OCaml не ленив и не изменчив, поэтому вы не можете написать функцию, которая динамически создает зацикленные списки.

Источник

Если вы не возражаете против использования черной магии, вы можете попробовать этот код:

let cycle l =
  if l = [] then invalid_arg "cycle" else
  let l' = List.map (fun x -> x) l in   (* copy the list *)
  let rec aux = function
    | [] -> assert false
    | [_] as lst ->   (* find the last cons cell *)
        (* and set the last pointer to the beginning of the list *)
        Obj.set_field (Obj.repr lst) 1 (Obj.repr l')
    | _::t -> aux t
  in aux l'; l'

Помните, что использование модуля Obj крайне нежелательно. С другой стороны, существуют промышленные программы и библиотеки (Coq, ядро ​​Джейн Стрит, в том числе батареи), которые используют этот вид запрещенного искусства.

Источник

Ответ camlspotter уже достаточно хорош. Я просто хочу добавить еще несколько пунктов здесь.

Прежде всего, для проблемы write a function that receives a finite list and returns an infinite, circular version of it, это может быть сделано на уровне кода / реализации, просто если вы действительно используете функцию, она будет иметь проблему с переполнением стека и никогда не вернется.

Простая версия того, что вы пытались сделать, выглядит следующим образом:

let rec circle1 xs = List.rev_append (List.rev xs) (circle1 xs)
val circle: 'a list -> 'a list = <fun>

Это может быть скомпилировано и теоретически это правильно. На [1;2;3]предполагается генерировать [1;2;3;1;2;3;1;2;3;1;2;3;...],

Однако, конечно, он потерпит неудачу, потому что его выполнение будет бесконечным и, в конечном счете, будет переполнением стека.

Так почему let rec circle2 = 1::2::3::circle2 буду работать?

Посмотрим, что будет, если ты это сделаешь.

Первый, circle2 это значение, и это список. После того, как OCaml получит эту информацию, он может создать статический адрес для circle2 с представлением списка в памяти.

Реальная ценность памяти 1::2::3::circle2что на самом деле Node (1, Node (2, Node (3, circle2))), то есть узел с int 1 и адрес узла с int 2 и адрес узла с int 3 и адрес круга 2. Но мы уже знаем адрес circle2, верно? Так что OCaml просто поместил туда адрес circle2.

Все будет работать

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

Давайте тогда вернемся к примеру circle1, Circle1 - это функция, да, у нее есть адрес, но она нам не нужна или не нужна. То, что мы хотим, это адрес приложения функции circle1 xs, Это не похоже на circle2, это функциональное приложение, которое означает, что нам нужно что-то вычислить, чтобы получить адрес. Так,

OCaml сделает List.rev xs, а затем попытаться получить адрес circle1 xsзатем повторите, повторите.

Хорошо, тогда почему мы иногда получаем Error: This kind of expression is not allowed as right-hand side of 'let rec'?

От http://caml.inria.fr/pub/docs/manual-ocaml/extn.html

конструкция привязки let rec, в дополнение к определению рекурсивных функций, также поддерживает определенный класс рекурсивных определений нефункциональных значений, таких как

пусть rec name1 = 1:: name2 и name2 = 2:: name1 в выражении, которое связывает name1 с циклическим списком 1::2::1::2::… и name2 с циклическим списком 2::1::2::1::… Неформально класс принятых определений состоит из тех определений, в которых определенные имена встречаются только внутри тел функций или в качестве аргумента для конструктора данных.

Если вы используете let rec определить привязку, скажем let rec name, это name может быть только в теле функции или в конструкторе данных.

В предыдущих двух примерах circle1 находится в теле функции (let rec circle1 = fun xs -> ...) а также circle2 находится в конструкторе данных.

Если вы делаете let rec circle = circle, это даст ошибку, поскольку кружок не в двух допустимых случаях. let rec x = let y = x in y не будет делать либо, потому что опять же, х не в конструкторе или функции.

Вот также четкое объяснение:

https://realworldocaml.org/v1/en/html/imperative-programming-1.html

Раздел Limitations of let rec

Источник

Что насчет (в OCaml 4.13.1)

      # let rec x = 1 :: x;;
val x : int list = [1; <cycle>]
# List.tl (List.tl (List.tl x));;
- : int list = [1; <cycle>]
Источник
Другие вопросы по тегам