Ответы 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
Это не проблема округлости. Вы не можете написать выражение, которое может вызвать рекурсивное вычисление в rhs let rec: см. Http://stackoverflow.com/questions/19859953/limitations-of-let-rec-in-ocaml – camlspotter
Все предложения по этой ссылке, которые вы опубликовали включают использование изменяемой ссылки (либо напрямую, либо через «ленивый», чтобы связать узел). Неужели невозможно переписать «цикл», поэтому он использует только letrec? – hugomg
Ваш код вызывает ошибку 'неограниченного значения ys', а не' let rec error'. Я думаю, что последний 'ys' должен быть' result', чтобы произвести ошибку, которую вы указали. –