Cyclical data structures in Elixir?

Qqwy

TypeCheck Core Team

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?

5 comments

#macros #data-structures #lazyness #immutability

6 5140 5

2016-12-31 09:51:08 UTC

Marked As Solved

Show Best Posts
Show All (oldest first)
Show All (newest first)

rvirding

Creator of Erlang

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.

Post #5

Also Liked

sasajuric

Author of Elixir In Action

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.

Post #2

michalmuskala

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 - Finger trees: a simple general-purpose data structure There are couple implementations in erlang in the wild.

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

Post #4

benwilson512

Author of Craft GraphQL APIs in Elixir with Absinthe

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

Post #3