Skip to content
Difference list library for OCaml
OCaml Shell
Branch: master
Clone or download
Pull request Compare This branch is 3 commits ahead of BYVoid:master.
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
bench
src
test
.gitignore
.travis-ci.sh
.travis.yml
INSTALL.txt
README.md
dlist.ocp
dlist.opam
dune-project

README.md

OCaml Difference List

Dlist (Difference List) is a purely functional list-like data structure supporting O(1) concatenation. This is particularly useful for efficient list construction from many lists. Dlist is a lazy immutable data type with no side effect.

This data structure is very handy when your algorithm requires lots of concatenations from many lists.

The idea is inspired by Haskell Data.Dlist and the APIs are influenced by Core.List.

Installation

Using OPAM:

opam install dlist

From source:

opam install ocp-build ounit core_bench
ocp-build build
ocp-build install

Documentation

http://byvoid.github.io/Dlist/Dlist.html

Example

let dlst1 = Dlist.of_list [1;2;3;4;5] in
let dlst2 = Dlist.of_list [6;7;8;9;10] in
let dlst = Dlist.append dlst1 dlst2 in (* O(1) *)
let lst = Dlist.to_list dlst

Time complexity

O(1) operations:

  • Dlist.empty
  • Dlist.append
  • Dlist.concat
  • Dlist.rev
  • Dlist.map
  • Dlist.mapi
  • Dlist.map2

O(N) operations:

  • Dlist.to_list
  • Dlist.of_list
  • Dlist.of_dlist
  • Dlist.length
  • Dlist.hd
  • Dlist.tl
  • Dlist.nth
  • Dlist.fold
  • Dlist.iter

Benchmark

Generate 100 lists where every list contains 100 random integers, and concatenate them with @ for list and Dlist.append for Dlist.

  Name       Time/Run   Speedup  
 ------- ------------- --------- 
  list    112_341_988      1.00  
  dlist    12_571_208      8.94 

License

BSD3

You can’t perform that action at this time.