OCaml中无穷无尽的名单会占用所有的记忆吗？

Question

我们可以构建一个无穷无尽的列表:

let rec endless = 1::endless

我认为它会占用所有的记忆,但是当我试着进入时utop,似乎并非如此.

utop 显示列表已构建:

val endless:int list =
[1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; ...]

当我尝试申请时List.length,当然,它永远不会停止,因为它有无限数量的1s.

---

问:

1. OCaml如何处理无尽的列表？

2. 为什么它不会出现内存不足错误？

Answer 1

在OCaml中,列表是单个链接列表.你endless在记忆中表现为自我递归的利弊细胞

.--------.
|        | 
|  +---+-|-+
`->| 1 | * |
   +---+---+

Answer 2

我不知道OCaml,所以我不能告诉你OCaml如何处理实现,但我可以给你一个大致的想法.

从理论上看,你可以拥有一个只有一个元素的无穷无尽的列表,将自己指向下一个和前一个节点.这只是数据结构设计的问题.因此,存储无限列表所需的内存将归结为一个元素和两个指针,两者都指向同一元素.

因此它几乎不使用任何内存,但是不可能通过遵循下一个/前一个指针来计算导航列表节点的算法.