OCaml lazy lists
List comprehension is a syntax construct for easy creating lists which allows to write more readable code than using map and filter functions. It is analogous to set comprehension in mathematics.
In Haskell using list comprehension jointly with lazy nature of lists allows to easily handle infinite lists, but OCaml doesn't provide such functionality.
Consider the following Haskell code:
[ 2 * x | x <- [0 .. 100], x ^ 2 > 3]
The corresponding OCaml code could look like this:
let rec interval a b =
if a > b then [] else a :: interval (a + 1) b
List.map
(fun x -> 2 * x)
(List.filter (fun x -> x ** x > 3) (interval 0 100))
But even in this case because of the strict nature of OCaml we couldn't easy handle infinite lists:
[ 2 * x | x <- [0 .. ], x ^ 2 > 3]
Surely, it is possible to handle infinite lists by implementing an appropriate type on your own, e.g.:
type 'a node_t =
Nil
| Cons of 'a * 'a t
and 'a t = 'a node_t lazy_t
and providing corresponding functions to work with it.
But the lack of syntactic sugar for lazy lists makes working with them somewhat tedious.
The code will be bulky even for the simple example above, not to mention something like this:
primes = sieve [2..]
where
sieve (p:xs) = p : sieve [x|x <- xs, x `mod` p > 0]
To simplify the usage of lazy lists in OCaml I've implemented a lazy list library and a syntax extension that allows for the following notation in the above examples:
[% 2 * x | x <- [% 0 .. ]; x * x > 3 ]
let primes =
let rec sieve = function
p %: xs -> p %: sieve [% x | x <- xs; x mod p > 0 ]
in sieve [% 2 ..]
With this syntax extension lazy lists may be written as follows:
[% ] (* an empty lazy list *)
[% 42 ] (* a lazy list containing single element 42 *)
[% 1; 2; 3; 4; 5] (* a lazy list containing number from 1 to 5 *)
[% 1 .. 5 ] (* the same lazy list *)
[% 2; 4 .. 10 ] (* a lazy list containing even numbers from 1 to 10 *)
[% 1; 3 .. 9; 10; 12 .. 20 ]
(* a lazy list containing odd numbers from 1 to 9 and even number from 10 to 20 *)
[% 1 .. ] (* a lazy list containing positive integers *)
[% 2; 4 .. ] (* a lazy list containing all even positive integers *)
Cons in original syntax is performed in the following way:
1 %: [% 2; 3 ] (* a lazy list containing 1, 2, 3 *)
1 %: 2 %: 3 %: [] (* the same lazy list *)
In revised syntax:
[% 1 :: [% 2; 3 ] ] (* a lazy list containing 1, 2, 3 again *)
[% 1 :: [% 2 :: [% 3 :: [% ] ] ] ] (* and again *)
[% 1; 2 :: [% 3 ] ] (* the same lazy list *)
[% 1; 2; 3 :: [% ] ] (* the same lazy list *)
List comprehension consists from expression, generators, guards and let-bindings.
[% x + 1 | x <- [% 1 .. 10 ] ] (* a lazy list containing integers from 2 to 11 *)
Multiple generators are separated by semicolons:
[% x, y | x <- [% 1 .. 4 ]; y <- [% 7; 8 ] ]
Boolean guards allow filtering:
[% x, y, z | x <- [% 1 .. 20 ]; y <- [% x .. 20 ];
z <- [% y .. 20 ]; x * x + y * y = z * z]
[% i, j | i <- [% 1 .. ]; j <- [% 1 .. i - 1 ]; gcd i j = 1 ]
Example of let declaration:
[% i, j | i <- [% 1 .. ]; let k = i * i; j <- [% 1 .. k ] ]
Pattern matching allows arbitrary decomposition of lazy list:
match [% (1, [2; 3]); (4, [5; 6]) ] with
(x, [y; 3]) %: tl -> x + y
| _ -> 0
In revised syntax:
match [% (1, [2; 3]); (4, [5; 6]) ] with
[ [% (x, [y; e]) :: tl ] -> x + y
| _ -> 0 ] ;
This library can be downloaded here .
Any comments are very welcome.
