Difference lists in Elixir
Elixir
Switch branches/tags
Nothing to show
Clone or download
sotojuan dlist -> difflist
Old version of this project was called "dlist", but this name is alredy
in use in Hex. I renamed the actual Elixir project but forgot to rename
the files.
Latest commit cefd24f May 10, 2017
Permalink
Failed to load latest commit information.
bench Rename project Mar 12, 2017
config Start project Mar 7, 2017
lib dlist -> difflist May 22, 2017
test dlist -> difflist May 22, 2017
.editorconfig Start project Mar 7, 2017
.gitignore Add left-associated `append` benchmark Mar 9, 2017
mix.exs Rename project Mar 12, 2017
mix.lock Add `ex_doc` Mar 12, 2017
readme.md Add background information to readme Mar 12, 2017

readme.md

difflist

Difference lists in Elixir

Install

In your mix.exs:

defp deps do
  [
    {:difflist, "~> 1.0.0"}
  ]
end

Then run mix deps.get.

Background

Difference lists are a way of encoding a list as the action of preappending them. Instead of a list being [1, 2, 3], it is the anonymous function fn(ys) -> [1, 2, 3] ++ ys end.

Difference lists are fast for left-associated appends (list ++ [x]) as they are represented as function composition.

Refer to this excellent blog post for more information.

Usage

The best place to read the documentation is in HexDocs or in iex (e.g. h DiffList.from_list).

This package exposes a DiffList module with the following functions:

Creating difference lists

DiffList.from_list/1

Creates a difference list from a regular list.

DiffList.empty/0

Creates an empty difference list.

DiffList.singleton/1

Creates a difference list of one element.

Using difference lists

DiffList.append/2

Appends a difference list to another difference list.

DiffList.cons/2

Prepends an item to a difference list.

DiffList.snoc/2

Appends an item to a difference list.

DiffList.head/1

Gets the first item of a difference list.

DiffList.tail/1

Gets the tail (a difference list of everything but the first item) of a difference list.

DiffList.concat/1

Concatenates a list of difference lists into one difference list.

Benchmark

A simple left-associated append benchmark is included. Run mix bench to run it.

License

MIT © Juan Soto