A difference list implementation for Julia. These are a highly efficient and simple way to build up lists from parts: appending, prepending, and concatenation are all very fast (constant time). They're also immutable, so you can reuse the parts.


Difference Lists for Julia, (C) 2018 Bill Burdick (William R. Burdick Jr.)

Difference lists are

  • highly efficient
  • simple
  • immutable
  • concatenate, prepend, and append in constant time
  • iterate in time N (like arrays)

This small library provides them for Julia, so you can use them when you need to accumulate a list incrementally. Since difference lists are immutable, you can easily reuse common parts.

To create a difference list, use the dl(items...) function like this:

julia> dl()

julia> dl(1)

julia> dl(1, 2, 3)
dl(1, 2, 3)

julia> dl(1, dl(2, 3), 4)
dl(1, dl(2, 3), 4)

Difference lists can iterate so you can easily convert them to collections.

julia> [x for x = dl(1, 2, 3)]
3-element Array{Int64,1}:

julia> collect(dl(1,2,3))
3-element Array{Any,1}:

You can concatenate difference lists in constant time using concatenate(lists::DL...), like this:

julia> concat(dl(1, 2), dl(3, 4))
dl(1, 2, 3, 4)

You can use a difference list itself as shorthand for concat, like this:

julia> dl(1, 2)(dl(3, 4), dl(5, 6, 7))
dl(1, 2, 3, 4, 5, 6, 7)


  • dl(): create an empty difference list
  • dl(items...): create a difference list from several elements
  • todl(iter): create a difference list from something you can iterate on
  • concat(lists...): concatenate several difference lists
  • dlconcat(iter...): concatenate several iterables into a difference list
  • push(list::DL, items...): make a difference list from list and items added to the end of it
  • pushfirst(list::DL, items...): make a difference list from list and items added to the start of it
  • (aList)(iter...): concatenate a difference list with one or more other difference lists or iterables

Difference lists can iterate, so you can use them in for loops, with collect(), etc.

First Commit


Last Touched

over 2 years ago


8 commits


Used By: