Home

cacophrene edited this page Aug 1, 2011 · 57 revisions
Clone this wiki locally

The Fcdll library implements circular doubly linked lists in OCaml. Unlike many other modules available on the web, this implementation use functional (immutable) lists with some kind of deferred computation (using functions rather than the dedicated Lazy module). This has three main consequences you should consider when using these lists in your applications :

  • Values are not computed once and for all.
  • As a consequence, side effects should be avoided.
  • Huge lists (up to max_int elements) are really cheap.

This library is licensed under the terms of the GNU Lesser General Public License version 3.

The latest stable release of the Fcdll library is 1.0. You need OCaml 3.12 to compile the library from sources.

However, some minor (syntactic) changes could be done in order to get full backward compatibility with older OCaml releases.

API documentation

You can build Fcdll documentation from sources using ocamldoc.

For convenience, here is the API documentation.

You will also find a more detailed presentation of Fcdll implementation (coming soon).

Bug reports and feature requests

Please send your bug reports and feature requests here. Small examples of unexpected behavior or requested features are appreciated.

We are doing our best to solve bugs quickly but patches are welcome.

Shedding light on Fcdll features : some examples

Please find below some code examples to illustrate the main features of Fcdll.

Circular doubly linked lists

Fcdll implements circular doubly linked lists. It means that you can read them in any sense. For convenience, iterators have an optional argument called rev which let you decide the sense of the iteration.

Reference : well, it just follows the definition of circular doubly linked lists

How to run this example : ocaml -I +fcdll fcdll.cma

# let a = Fcdll.init 10 (fun i -> i);;
val a : int Fcdll.fcdll = <abstr>
# let print = Printf.printf "%d ";;
val print : int -> unit = <fun>
# Fcdll.iter print a;;
0 1 2 3 4 5 6 7 8 9 - : unit = ()
# Fcdll.iter ~rev:true print a;;
9 8 7 6 5 4 3 2 1 0 - : unit = ()
# Fcdll.to_list (Fcdll.map ~rev:true (fun i -> 2 * i) a);;
- : int list = [18; 16; 14; 12; 10; 8; 6; 4; 2; 0]

Deferred computation : huge lists

Functional circular doubly linked lists use function-based deferred computation. It means that values are only computed when needed for another computation. As a consequence, it is possible to create huge lists of hundreds of billions of elements. This is obviously not possible with standard lists or arrays because they both use direct computation.

Reference : This feature was directly inspired from this Haskell article.

How to run this example : ocaml -I +fcdll fcdll.cma unix.cma

# let benchmark f n =
    let x = Unix.gettimeofday () in
    let r = f n in
    let y = Unix.gettimeofday () in
    Printf.printf "Elapsed time: %.3f ms\n%!" (1000. *. (y -. x));
    r;;
val benchmark : ('a -> 'b) -> 'a -> 'b = <fun>
# let x = benchmark (Fcdll.init 100_000_000_000) (fun i -> i);;
Elapsed time: 0.002 ms
val x : int Fcdll.fcdll = <abstr>
# let y = benchmark (Array.init 100_000_000_000) (fun i -> i);;
Out of memory during evaluation.

Recycling values : odd and even numbers

This example illustrates the behavior of functions which works on two lists such as Fcdll.combine. When the given lists are of different lengths, the shorter list is extended by recycling its values until it matches the size of the greater one. Since standard OCaml lists are not circular, the corresponding functions raise an exception when the given lists have different lengths.

Reference : This feature was directly inspired from the R language.

How to run this example : ocaml -I +fcdll fcdll.cma

# let ints = Fcdll.init 10_000_000 (fun i -> i);;
val ints : int Fcdll.fcdll = <abstr>
# type parity = Odd | Even;;
type parity = Odd | Even
# let flags = Fcdll.of_list [Even; Odd];;
val flags : parity Fcdll.fcdll = <abstr>
# let flagged_ints = Fcdll.combine ints flags;;
val flagged_ints : (int * parity) Fcdll.fcdll = <abstr>
# Fcdll.to_list (Fcdll.sub flagged_ints ~pos:0 ~len:5);;
- : (int * parity) list = [(0, Even); (1, Odd); (2, Even); (3, Odd); (4, Even)]
# Fcdll.to_list (Fcdll.sub flagged_ints ~pos:(-2) ~len:4);;
- : (int * parity) list = [(9999998, Even); (9999999, Odd); (0, Even); (1, Odd)]

Combining List and Array features : the blit function

The Fcdll library provides functions from both List and Array modules. For example, you can use Fcdll.blit to edit the contents of a given list. Please note that Fcdll.blit also recycle values when needed.

How to run this example : ocaml -I +fcdll fcdll.cma

# open Fcdll;;
# let dst = init 100_000 (fun i -> i);;
val dst : int Fcdll.fcdll = <abstr>
# let src = init 5 (fun i -> - i - 12);;
val src : int Fcdll.fcdll = <abstr>
# let res = blit ~src ~src_pos:0 ~dst ~dst_pos:(-2) ~len:7;;
val res : int Fcdll.fcdll = <abstr>
# to_list (sub res ~pos:(-4) ~len:11);;
- : int list = [99996; 99997; -12; -13; -14; -15; -16; -12; -13; 5; 6]