Stack Overflow when calling a function that generates a lazy list?

user_18201731 0
Viewed 66

I can define an infinite data structure - aka lazy list - like this.

let 'a lazylist = Succ of 'a * (unit -> 'a lazylist);;

(Why can't I replace unit -> 'a lazylist with () -> 'a lazylist?)

The way I understand lazy data structures the above definition says that a lazy list consists of a tupel of a generic element 'a and a function unit->'a lazylist that will compute the next element in the list when called with () which is of type unit.

So e.g. I could generate a list that has every even number:

let rec even_list l = 
  match l with 
    Succ (a, l') -> 
      if (a mod 2 = 0) then 
        Succ (a, fun() -> even_list (l' ())
      else  
        even_list (l' ());;

The way I understand it: When fun() -> even_list (l'())) is called with the unit argument () it will call even_list with the successor of l' by giving it unit as an argument: l'()

But is it possible for the else even_list (l'());; part to lead to a Stack Overflow if we give even_list a lazylist as an argument that only consists of uneven elements e.g.? Whereas in the then part of the if-statement we only generate the next element of the list when called with () - in the else part we would search indefinitely.

lazy-evaluation ocaml functional-programming
1 Answers

First, you can use the built-in Seq.t type rather than define your own lazy list type.

Second, your function even_list is tail-recursive and cannot result in a stack overflow.

Third, if you are using the take function proposed in Call lazy-list function in OCaml, it is this function which is not tail-recursive and consumes stack.

You can write a tail-recursive version of this function

let rec take l n (Succ(x,f)) =
  if n = 0 then List.rev l
  else take (x::l) (n-1) (f ())
let take n l = take [] n l

or define a fold function

let rec fold_until n f acc (Succ(x,l)) =
  if n = 0 then acc
  else fold_until (n-1) f (f acc x) (l())

and use that function to define a printer that does not build an intermediary list.

(This is why it is generally advised to write-down a fully self-contained example, otherwise the issue is too often hidden in the implicit context of the question.)

user_73693660
Related