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.

Posted by Vadim Shender on 2008-08-04 16:39:50
Tags: ocaml, camlp4, syntax extension, lazy lists

OCaml partial application syntax enhancement

In many situations in functional programming it's handy to be able to produce "specialized" functions by fixing the values of part of the arguments of a more generic one. This is usually referred to as partial application. Here's a simple example in OCaml:

  # (+) 1 ;;
  - : int -> int = <fun>

  # let f = (+) 1 ;;
  val f : int -> int = <fun>
  # f 2 ;;
  - : int = 3

Partial application allows writing more elegant code in some cases:

  # List.map ((+) 1) [0; 1; 2; 3; 4] ;;
  - : int list = [1; 2; 3; 4; 5]

  # let f c a b = c * (a + b) ;;
  val f : int -> int -> int -> int = <fun>

  # List.map2 (f 2) [0; 1; 2] [1; 2; 3] ;;
  - : int list = [2; 6; 10]

instead of

  List.map (fun x -> 1 + x) [0; 1; 2; 3; 4] ;;

  List.map2 (fun x y -> f 2 x y) [0; 1; 2] [1; 2; 3]

But the support for partial application is somewhat limited - there's no syntax in OCaml for fixing an arbitrary subset of arguments, only a number of leftmost arguments (upd: I mean positional arguments here, no keyword arguments). This limitation disallows writing such elegant code for example in following case: we want to substract 5 from all elements of a list (i.e. we want to fix the second argument). The code has to look like this:

  # List.map (fun x -> (-) x 5) [1; 2; 3; 4; 5] ;;
  - : int list = [-4; -3; -2; -1; 0]

To overturn this limitation the pa_papply syntax extension have been created:

  open Camlp4

  module Id : Sig.Id = struct
    let name    = "Partial apply syntax extension"
    let version = "0.0.1"
  end

  module Make (Syn : Sig.Camlp4Syntax) = struct
    open Sig
    include Syntax

    EXTEND Gram
      expr: LEVEL "apply"  (* LEFTA *)
        [ [ e = expr; stubs = LIST1 "_" ->
              let il =
                let rec enum i = function [] -> [] | _ :: t -> i :: enum (i + 1) t
                in enum 0 stubs
              in

              let xl = List.map (fun i -> "__papply_x_" ^ string_of_int i) il in

              let eapplyx =
                List.fold_left (fun accu xi -> <:expr< $accu$ $lid:xi$ >>) e xl in

              let funx    =
                List.fold_right
                  (fun xi rest -> <:expr< fun $lid:xi$ -> $rest$>>)
                  xl <:expr< $eapplyx$ __papply_z>>
              in <:expr< fun __papply_z -> $funx$ >> ] ] ;

    END
  end

  module M = Register.OCamlSyntaxExtension (Id) (Make)

This extension is compiled by running following command:

 
  # ocamlc -I +camlp4 -pp camlp4orf -c pa_papply.ml

And the command:

 
  # ocamlc -pp "camlp4o -I . pa_papply.cmo" -c test.ml

compiles for instance file test.ml written in our extended syntax. pa_papply enables to rewrite the previous example in the following way:

  # List.map ((-) _ 5) [1; 2; 3; 4; 5] ;;
  - : int list = [-4; -3; -2; -1; 0]

It's possible to skip any number of leftmost arguments before partial application:

  # let f x y z = (x + y) * z ;;
  val f : int -> int -> int -> int = <fun>

  # f 1 2 3 ;;
  - : int = 9
  # f _ 2 1 3 ;;
  - : int = 9
  # f 1 _ 3 2 ;;
  - : int = 9
  # f _ _ 3 1 2 ;;
  - : int = 9

Comments, suggestions and bug reports are welcome.

Posted by Vadim Shender on 2008-07-09 14:09:55
Tags: ocaml, functional programming, camlp4

Archive

RSS feeds

Instant Message

Posts with tag ocaml

OCaml lazy lists

OCaml partial application syntax enhancement