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

Question

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

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 
;; 

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

Error: This kind of expression is not allowed as right-hand side of `let rec'

Answer 1

Ваш код имеет две проблемы:

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

Приведенный выше код отвергается компилятором, потому что вы не можете написать выражение, которое может привести к рекурсивной вычисления в правой части let rec (см Limitations of let rec in 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, то вы можете использовать ленивую структуру, чтобы предотвратить немедленные бесконечные циклы, такие как ленивый список Haskell, или использовать мутацию для создания цикла подстановкой. Список OCaml не ленив и не изменен, поэтому вы не можете писать функцию, динамически создавая зацикленные списки.

Answer 2

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

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

Простой вариант того, что вы пытаетесь сделать, это так:

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;...].

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

---

Так почему же 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 просто указал адрес Circ2.

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

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

---

Давайте вернемся к примеру 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#s%3aletrecvalues

the let rec binding construct, in addition to the definition of recursive functions, also supports a certain class of recursive definitions of non-functional values, such as

let rec name1 = 1 :: name2 and name2 = 2 :: name1 in expr which binds name1 to the cyclic list 1::2::1::2::…, and name2 to the cyclic list 2::1::2::1::…Informally, the class of accepted definitions consists of those definitions where the defined names occur only inside function bodies or as argument to a data constructor.

Если вы используете 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 тоже не будет, потому что снова x не в конструкторе или функции.

---

Здесь также четкое объяснение:

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

Раздел Limitations of let rec

Answer 3

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

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 сильно d iscouraged.С другой стороны, существуют промышленные программы и библиотеки (Coq, Jane Street's Core, Batteries included), которые, как известно, используют такое запретное искусство.