unique-id

Pure generation of unique identifiers in Elm.

Sometimes we need unique identifiers attached to some parts of a data structure so we can identify them for analysis and processing. Therefore it's convenient to have a source from which we can acquire unique IDs. In an impure language, we'd just designate a mutable integer variable nextId and then use nextId++ wherever a unique Id is needed. That doesn't work in a pure language, but this library makes it relatively convenient.

We specify computations within the Unique type, and then run that computation to allocate all the identifiers therein. Within one invocation of run, all the generated Id values are guaranteed to be unique. However, multiple invocations of run will generate conflicting Ids. Therefore, as much as possible you want to specify computations wrapped within Unique.

Unique computations can be specified with the typical andThen and map operations. The function unique generates the next Id and return produces a constant value.

There is an extended example in tests/Example.elm. It defines a binary tree data structure where the leaves will hold a value of any type and also be marked with a Unique.Id:

type Tree a
  = Branch (Tree a) (Tree a)
  | Leaf a Unique.Id

We define the alias TreeGen to describe a computation that produces a Tree:

type alias TreeGen a = Unique.Unique (Tree a)

Then by providing these alternative constructors:

leaf : a -> TreeGen a
leaf a = Unique.map (Leaf a) Unique.unique

branch : TreeGen a -> TreeGen a -> TreeGen a
branch left right = Unique.map2 Branch left right

we can produce trees within Unique like this:

example : TreeGen a
example = branch (leaf "xen") (branch (leaf "yow") (leaf "zip"))

The leaves will be labeled with Ids 0, 1, and 2:

> toString (Unique.run example)
Branch (Leaf "xen" (Id 0)) (Branch (Leaf "yow" (Id 1)) (Leaf "zip" (Id 2)))

Suppose now we want to splice a new tree into an existing tree at a certain leaf. We can specify the Id of the leaf to be replaced, and do the entire computation within Unique (via the TreeGen alias):

splice : Unique.Id -> TreeGen a -> Tree a -> TreeGen a
splice id subst tree =
  case tree of
    Leaf x k ->
      if k == id then subst
      else leaf x
    Branch left right ->
      branch (splice id subst left) (splice id subst right)

The resulting tree will regenerate identifiers for all the leaves in its tree parameter.

The Example module continues with a UI that renders binary trees as nested boxes: brown-bordered boxes for branches and green boxes for leaves. When you hover over one of the leaves, it will splice the other tree onto that point and show the result.

This library fulfills a similar role to the Data.Unique module in Haskell.