Recursively defined values.

This library provides safe APIs that allow you to define and calculate values recursively, and still get a result out:

let s1 = RS.insert 23 s2
    s2 = RS.insert 42 s1
in RS.get s1

will not loop, but rather produces the set fromList [23,42]

See Data.Recursive.Examples for more examples, or just browse the modules

• Data.Recursive.Bool

• Data.Recursive.Set

• Data.Recursive.Map

• Data.Recursive.DualBool

More APIs (e.g. for maps or Natural) can be added over time, as need and good use-cases arise.

For the (unsafe) building blocks to build such APIs, see

• Data.Propagator.Purify for the wrapper that turns an IO-implemented propagator into a pure data structure

• Data.Propagator.Naive for a naive propagator implementation

• Data.Propagator.P2 for a smarter propagator implementation for the two-point lattice, i.e. Bool

The library is not (yet) focussed on performance, and uses a rather naive propagator implementation. Expect this to be slow if you have large graphs. This may be improved in the future (e.g. by propagating only deltas, and accumulating deltas before applying a function), but for now the focus is on foremost providing this capability in the first place and getting the user-facing API right.

rec-def - Pure recursive definition

This library provides safe APIs that allow you to define and calculate values recursively, and still get a result out:

>>> :{
  let s1 = RS.insert 23 s2
      s2 = RS.insert 42 s1
  in RS.get s1
 :}
fromList [23,42]

See the examples.hs file for more examples.

It also provides (unsafe) building blocks to build such APIs, see Data.Propagator.Purify.

Related work

• Edward Kmett's Data.Propagator.Prop module achieves something similar, and allows to construct more the graphs more flexibly, but requires a stricter phase control akin to runST.

• Jeannin, Kozen and Silva’s work on “CoCaml: Functional Programming with Regular Coinductive Types” in Ocaml even goes a step further and not only allow the recursive definitions to be written down as here, but even allows functions consume regular recursive values, and still produces something that can be solved.