Cyclical data structures in Elixir?

Questions / Help
, , ,
1

Certain kinds of algorithms can be sped up (or even: are only possible) by using cyclic data structures.
Functional languages make it hard to specify cyclic data structures (such as for instance doubly-linked lists) because of their immutability.

Nevertheless, in e.g. Haskell it is possible to create cyclic data structures using a process that is known as ‘tying the knot’. This seems to only be possible because Haskell is by definition/default lazy, however.

I am wondering if it is possible (maybe with some clever (non-hygienic) macro metaprogramming?) to create a cyclic data structure in Elixir, such as a list x where one of the elements contains this list.

Are there ways to do this?

6 Likes
2

i believe tying the knot is possible in haskell because lazy evaluation gives you a form of memoization for free. without that you have to memoize your cyclic data structures ‘by hand’. you can look at the erlang module digraph for an example that uses ets tables to model a graph with possible cycles via immutable data structures

however, using memoization to convert self referential data structures doesn’t let you use the algorithms that rely on self referential data structures on them. at best you can write code that looks like the imperative/cyclical algorithm but the performance is going to be - at best - the same as the pure functional algorithm. all you are really doing is rewriting one algorithm to look more like another. even haskell has to pay this performance penalty when working with self referential data structures

2 Likes
3

Zippers can be used to implement a two-way navigational list. The example in the article doesn’t support cycle, but it should be very easy to extend it by adding a clause which matches on the empty list in the second element.

The idea is to keep a tuple in the shape of {visited::[any], remaining::[any]}. So for example, in a tuple {[3, 2, 1], [4, 5, 6]} you’re currently at the element 4, while previously visited 1, 2, 3 (in that order). The next operation will move 4 to the top of the first list, so you’ll get {[4, 3, 2, 1], [5, 6]}. If after the move the second list is empty, then you just reverse the first list, and return {[], reversed_first_list}. So next({[5, 4, 3, 2, 1}, [6]) will return {[], [1, 2, 3, 4, 5, 6]}, and you’re back at the start.

You can take the similar approach to move in the opposite direction. The prev operation pops the head off the first list and pushes it at the top of the second list, unless the first list is empty, in which case you need to keep the last element of the second list, reversing all others into the first list.

Supporting insert and delete is as easy as pushing/popping to/from the top of the second list.

14 Likes
4

Also worth noting that this is very similar to the implementation of a queue in functional programming. For more information on the underpinnings of such structures I highly recommend: https://www.cs.cmu.edu/~rwh/theses/okasaki.pdf

4 Likes
5

Another very interesting structure are the Finger Trees, that allow for efficient implementations of deques (double ended queues), priority queues or lists with O(1) size information - http://www.staff.city.ac.uk/~ross/papers/FingerTree.html There are couple implementations in erlang in the wild.

It could be interesting to see some Elixir based implementations with all the protocols.

6 Likes
6

There is no way to create real cyclic data structures when you only have immutable data as cyclic structures require mutability. You can only simulate them in some way.

7 Likes