Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Will endless list in OCaml eat up all the memory?

Tags:

ocaml

We can construct an endless list like this:

let rec endless = 1::endless

I think it would eat up all the memory, but when I tried in utop, it doesn't seem so.

utop shows the list has been constructed:

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

When I try to apply List.length, of course, it never stops due to the fact it has infinite number of 1s.


Q:

  1. How does OCaml handle endless list?

  2. Why it won't give a out-of-memory error?

like image 218
Jackson Tale Avatar asked Apr 24 '14 10:04

Jackson Tale


2 Answers

In OCaml, lists are single linked lists. Your endless is represented in memory as a self-recursive cons cell

.--------.
|        | 
|  +---+-|-+
`->| 1 | * |
   +---+---+
like image 81
Stas Avatar answered Sep 30 '22 12:09

Stas


I have no knowledge of OCaml, so I can't tell you how OCaml handles the implementation, but I can give you a general idea.

Theoretically seen you can have an endless list with just one element, pointing to itself as the next and previous node. This is just a matter of the data structure design. So, the needed memory to store an endless list would come down to one element and two pointers, both pointing at the same element.

Therefore it uses almost no memory, but it is impossible to count for algorithms that navigate the list nodes by following the next/previous pointers.

like image 34
kasoban Avatar answered Sep 30 '22 11:09

kasoban