Data structures – Haskell – Aelve Guide

treap

2019-05-07T08:32:56Z

treap (Hackage)

The treap package implements a tree-like data structure called implicit treap. This data structure implements interface similar to random-access arrays, but with fast (logarithmic time complexity) insert/delete/split/merge/take/drop/rotate operations. In addition, treap allows you to specify and measure values of any monoids on a segment, like a sum of elements or minimal element on some contiguous part of the array.

When to use?

Use this package when you want the following operations to be fast:

Access elements by index.
Insert elements by index.
Delete elements by index.
Calculate monoidal operation (like sum, product, min, etc.) of all elements between two indices.
Call slicing operations like take or drop or split.

slist

2019-05-07T08:28:10Z

slist (Hackage)

This package introduces sized list data type — Slist. The data type has the following shape:

data Slist a = Slist
    { sList :: [a]
    , sSize :: Size
    }

As you can see along with the familiar list, it contains Size field that represents the size of the structure. Slists can be finite or infinite, and this is expressed with Size.

data Size
    = Size Int
    | Infinity

This representation of the list gives some additional advantages. Getting the length of the list is the "free" operation (runs in O(1)). This property helps to improve the performance for a bunch of functions like take, drop, at, etc. But also it doesn't actually add any overhead on the existing functions.

algebraic-graphs

2018-10-14T17:27:18Z

algebraic-graphs (Hackage)

Alga (this package) is a library for algebraic construction and manipulation of graphs in Haskell. See the README for more information.

dlist

2017-09-28T17:30:13Z

dlist (Hackage)

A list-like type supporting O(1) append, useful for efficient logging and pretty printing.

Example

Using DList as the state type when printing a tree with the Writer monad from dlist docs:

import Control.Monad.Writer
import Data.DList

data Tree a = Leaf a | Branch (Tree a) (Tree a)

flatten_writer :: Tree x -> DList x
flatten_writer = snd . runWriter . flatten
    where
      flatten (Leaf x)     = tell (singleton x)
      flatten (Branch x y) = flatten x >> flatten y

fgl

2017-09-28T17:30:09Z

fgl (Hackage)

An inductive representation of manipulating graph data structures.

TODO: better description.

Notes

Links

Links to tutorials, blog posts, etc.

Imports

Most commonly used imports from the library

Usage

Some examples

Gotchas

Common mistakes and non-obvious things

bytestring-trie

2017-09-28T17:30:06Z

bytestring-trie (Hackage)

An efficient finite map from (byte)strings to values.

If all you need to do is associate strings to values you should use either Map from containers or HashMap from unordered-containers. You should only use this if you need the extra capabilities that a trie can provide (structure sharing for highly redundant keys, submap of all keys with a given prefix, extracting minimum and maximum keys, etc).

HList

2017-09-28T17:29:59Z

HList (Hackage)

Creation and manipulation of heterogenous lists (HLists) whose length and element types are known at compile-time.

unordered-containers

2017-09-27T20:11:48Z

unordered-containers (Hackage)

Efficient hashing-based container types including HashSet and HashMap.

Strict or Lazy hashmap? If:

you will eventually need all the values stored, or
the stored values don't represent large virtual data structures to be lazily computed

then you should use the Data.HashMap.Strict.

containers

2017-09-27T20:11:43Z

containers (Hackage)

Efficient general-purpose implementations of various immutable ordered container types. This package includes: Maps, Sets, Trees, Graphs, and Seqs.

Strict or Lazy map? If:

you will eventually need all the values stored, or
the stored values don't represent large virtual data structures to be lazily computed

then you should use the strict version of each of the container type (Data.IntMap.Strict, Data.Map.Strict).

Tutorial: https://haskell-containers.readthedocs.io.