Enumerating all pairs constructible from two lazy lists in OCaml

Question

Hi everyone,

I am attempting to enumerate the set of all pairs made of elements from two lazy lists (first element from the first list, second element from the second list) in OCaml using the usual diagonalization idea. The idea is, in strict evaluation terms, something like

enum [0;1;2;...] [0;1;2;...] = [(0,0);(0,1);(1;0);(0;2);(1;1);(2;2);...]

My question is: how do you define this lazily?

I'll explain what I've thought so far, maybe it will be helpful for anyone trying to answer this. But if you know the answer already, you don't need to read any further. I may be going the wrong route.

I have defined lazy lists as

type 'a node_t =
   | Nil
   | Cons of 'a *'a t
and 'a t = ('a node_t) Lazy.t

Then I defined the function 'seq'

let seq m =
   let rec seq_ n m max acc =
           if n=max+1
               then acc
               else (seq_ (n+1) (m-1) max (lazy (Cons((n,m),acc))))
in seq_ 0 m m (lazy Nil)

which gives me a lazy list of pairs (x,y) such that x+y=m. This is what the diagonal idea is about. We start by enumerating all the pairs which sum 0, then all those which sum 1, then those which sum 2, etc.

Then I defined the function 'enum_pair'

let enum_pair () = 
  let rec enum_pair_ n = lazy (Cons(seq n,enum_pair_ (n+1)))
in enum_pair_ 0

which generates the infinite lazy list made up of: the lazy list of pairs which sum 0, concatenated with the lazy lists of pairs which sum 1, etc.

By now, it seems to me that I'm almost there. The problem now is: how do I get the actual pairs one by one?

It seems to me that I'd have to use some form of list concatenation (the lazy equivalent of @). But that is not efficient because, in my representation of lazy lists, concatenating two lists has complexity O(n^2) where n is the size of the first list. Should I go for a different representations of lazy lists? Or is there another way (not using 'seq' and 'enum_pair' above) which doesn't require list concatenation?

Any help would be really appreciated.

Thanks a lot, Surikator.

Answer 1

Hi again,

In the mean time I've managed to get somewhere but, although it solves the problem, the solution is not very elegant. After defining the functions defined in my initial question, I can define the additional function 'enum_pair_cat' as

let rec enum_pair_cat ls =
lazy(
    match Lazy.force ls with
        | Nil             -> Nil
        | Cons(h,t) -> match Lazy.force h with
                                        | Nil -> Lazy.force (enum_pair_cat t)
                                        | Cons (h2,t2) -> Cons (h2,enum_pair_cat (lazy (Cons (t2,t))))
)

This new function achieves the desired behavior. By doing

enum_pair_cat (enum_pair ())

we get a lazy list which has the pairs enumerated as described. So, this solves the problem.

However, I am not entirely satisfied with this because this solution doesn't scale up to higher enumerations (say, of three lazy lists). If you have any ideas on how to solve the general problem of enumerating all n-tuples taken from n lazy lists, let me know!

Thanks, Surikator.

Answer 2

In Haskell you can write:

concatMap (\l -> zip l (reverse l)) $ inits [0..]

First we generate all initial segments of [0..]:

> take 5 $ inits [0..]
[[],[0],[0,1],[0,1,2],[0,1,2,3]]

Taking one of the segments an zipping it with its reverse gives us one diagonal:

> (\l -> zip l (reverse l)) [0..4]
[(0,4),(1,3),(2,2),(3,1),(4,0)]

So mapping the zip will give all diagonals:

> take 10 $ concatMap (\l -> zip l (reverse l)) $ zipWith take [1..] (repeat [0..])
[(0,0),(0,1),(1,0),(0,2),(1,1),(2,0),(0,3),(1,2),(2,1),(3,0)]