linked-list: Suspicious alternative for functional languages

[NobbZ]

During reading the changes made by PR #188, I encountered some paragraph in the linked-list.md, which I do find is giving a suspicious alternative for implementing the exercise in functional languages:

In languages that do not have good support for mutability (such as Elixir or Erlang), you may choose to implement a functional list where shift and pop have amortized O(1) time. The simplest data structure for this will have a pair of linked lists for the front and back, where iteration order is front ++ reverse back.

In a commit of the afforementioned PR, I already did a quick comment:

https://github.com/cebial/x-common/commit/552006a4610f917233e604ace3e964158ad01d6b#diff-25093f3da30fc2fdff5ad6a3967a7dfbL29

So this paragraph is describing an Okasaki-Functional-Double-Ended-Queue. This is not comparable with Doubly-Linked-Lists in any way.

Perhaps we should split this exercise up into this one and describe it in a imperativ way only while creating another exercise which does require you to implement a dequeue.

Another way to interprete this paragraph is very similar to a zipper as in zipper.md. If it is meant like a zipper we should probably don't do this exercise in languages which are immutable only and stick to that zipper-exercise.

Are there any further opinions on this?

[kytrinyx]

I think the right move is to not implement the linked-list in functional languages. We should remove the suspicious alternative from the README.

If functional languages have implemented linked-list with the alternative, we should consider deprecating it.

If the zipper problem is sufficiently close to the dequeue, I would not want to implement a new exercise specifically for the dequeue.

[NobbZ]

The Zipper is actually far away from a dequeue, its just another way to read that paragraph.

The functional dequeue is something that holds two lists, one "front" and one "back" queue. One appends by "consing" to the back, and pops by taking the head from the front. If the front is empty when one tries to pop, the "back" is reversed and used as front.

A Zipper on the other hand is more similar to a Visitor in OOP. When created it takes the original datastructure and converts parts of it into an internal representation. When talking about a list-zipper this were exactly 2 lists. One containing all items before the current position with the most recent visited as its head (so it is reversed) and a list containing the items after the current position. This were a very simple Zipper. You can walk this Zipper back and forth elementwise in O(1) (if it is implemented correctly) and as such you get similar runtime behaviour as with a doubly-linked-list, as long as you use its zipper. Also you can reconstruct the original list from any position in O(n), where n is the current position in the list. The Zipper from the actual exercise is more complex since it walks a binary tree, but also there you can go one step down or up in O(1) (if you consider copying the data has no cost), and also you are able to reconstruct the original tree from any position in O(n), with n beeing the depth in the tree of the current position.

So implementing a functional dequeue (also called Okasaki-Queue because of his paper "Purely Functional Data Structures" from 1996) is completely different from implementing a Zipper (even for lists).

[petertseng]

The suspicious paragraph was removed in #194 a long time ago, so we are good on this front.

To replace it, if we will have the proposal of #623, it will be given its own exercise.