How would I call the following function in order to compute the numbers from 1 to 100 e.g.?
type 'a llist = Cons of 'a * (unit -> 'a llist)
let rec lnat n = Cons (n, fun () -> lnat (n+1))
Calling lnat 1 gives me the following:
lnat 1;;
- : int llist = Cons (1, <fun>)
But how do I compute the following numbers?
If the goal is to convert a (finite prefix of an) llist to an ordinary list, we can do that with a simple recursive helper function.
let rec take n (Cons (x, xs)) =
if n = 0 then [] else x :: take (n - 1) (xs ())
Use as
# take 100 (lnat 1);;
- : int list =
[1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15; 16; 17; 18; 19; 20; 21;
22; 23; 24; 25; 26; 27; 28; 29; 30; 31; 32; 33; 34; 35; 36; 37; 38; 39; 40;
41; 42; 43; 44; 45; 46; 47; 48; 49; 50; 51; 52; 53; 54; 55; 56; 57; 58; 59;
60; 61; 62; 63; 64; 65; 66; 67; 68; 69; 70; 71; 72; 73; 74; 75; 76; 77; 78;
79; 80; 81; 82; 83; 84; 85; 86; 87; 88; 89; 90; 91; 92; 93; 94; 95; 96; 97;
98; 99; 100]
The llist in your representation stores the first value strictly and then hides the rest of the computation behind a function that takes (). Since the function takes () (i.e. no real arguments), its only choice (aside from producing side effects, which I feel would be unexpected behavior in this context) is to produce a constant value.
So it really is just an infinite list, where the function part "protects" the rest of the list from flooding your computer's memory. To access the following element, apply the function to (), the only valid value of type unit.