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

Difference lists are

  • highly efficient
  • simple
  • immutable
  • concatenate, prepend, and append inconstant time
  • iterate intime 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.