Add immutable `Deque`

[magnus-madsen]

Add an immutable deque:

enum Deque[a] {
  // A deque has two lists: the "in" elements and the "out" elements.
  // When "out" runs dry, we move "in" to "out" (but in reverse order). 
  case Deque(List[a], List[a])
}

with operations:

def isEmpty(d: Deque[a]): Bool
def pushFront(x: a, d: Deque[a]): Deque[a]
def pushBack(x: a, d: Deque[a]): Deque[a]
def popFront(x: a, d: Deque[a]): Option[(a, Deque[a])]
def popBack(x: a, d: Deque[a]): Option[(a, Deque[a])]

See https://www.scala-lang.org/api/2.13.5/scala/collection/immutable/Queue.html See https://javadoc.io/static/org.scalaz/scalaz_2.9.3/7.1.17/scalaz/Dequeue.html See https://www.cs.cmu.edu/~rwh/students/okasaki.pdf

[ZiyaoWei]

@magnus-madsen - is this still worth adding? If so I’d be interested :-)

[magnus-madsen]

Yes, I would suggest to write the first 100 lines and then make a PR so we can discuss the architecture.

You might also want to find some papers etc on how to best implement it.

Note that for all public functions we expect 3-5 test cases.

[ZiyaoWei]

Finally an excuse for dusting off my old and underused copy of Okasaki!

It seems the dequeue implementation of scalaz you linked to above follows the "Banker’s Deques" section rather closely (manually transpiled :-) ) - I assume implementing the same algorithm would be fine? I'll read through the relevant sections of the book to make sure I'm not missing anything but want to sanity check.

[magnus-madsen]

Sure. I'm no expert either.

[magnus-madsen]

Following okasaki is also good

[ZiyaoWei]

Turns out deques in Okasaki use lazy evaluation to achieve the O(1) amortized bound in the face of persistence.

...which in turn is done in scalaz.Dequeue by using streams.

EDIT: It seems scalaz's Dequeue isn't amortized O(1) - it's basically a regular purely functional queue masquerading as a dequeue, and there could be a lot of whiplashes when there are interleavinguncons and unsnoc calls. This seems to prove it.

There is a design of deques that doesn't need streams mentioned in Okasaki, but it doesn't work with persistence.

Given the above, it seems the lazy Streams portion of #4533 should be done before Deque? I'd be happy to look into that if it is up for grabs.

[magnus-madsen]

We do have Lazy[t], but are you saying Deque cannot be done without?

In any case, https://github.com/flix/flix/issues/4533 is an experiment, and probably not something we should build on top of...

We do have DelayList though.

[ZiyaoWei]

Ah, DelayList seems to be exactly what is needed here, thanks! Somehow missed it and Lazy[t], I'll see if I can implement it over the coming weekend - sorry for the turnaround, still have a day job 😅

[ZiyaoWei]

It turns out (finger trees)[http://www.staff.city.ac.uk/~ross/papers/FingerTree.html] might be better according to Hugs.

The implementation in GHC seems to be the canonical one - I'll take a look but this looks significantly more complicated, and I think we'll want to measure which one is actually faster.

There is also something to be said about the Okasaki version being more simple, so maybe I could implement that first and it wouldn't hurt to have both available. Thoughts? Sorry this has been taking longer than I thought, but it has been super interesting and definitely is getting me to write some non trivial Flix code!

[magnus-madsen]

I think that experimentation is important, so I encourage you to go forward :)

As for getting something merged into Flix, I think the first task would simply be to agree on the API (i.e. list of public functions). Once that is in place, we can experiment with different implementations, right? :)

[magnus-madsen]

So-- it might actually be worth it to write a silly, stupid implementation with test cases, and then later replace it by a fancy and fast implementation.

[magnus-madsen]

Makes sense?

[ZiyaoWei]

Of course - thanks! I'll hack something out in the next few days then, probably start with Okasaki since it doesn't seem too difficult.

[ZiyaoWei]

So I have decided to first work out the signatures first by modeling things after List, but there are simply way too many functions there 😅

Would it be reasonable to

• have a Deque typeclass with a few functions to serve as the interface and then have potentially multiple implementations conforming to it? This would be similar to what Data.Dequeue is doing, or

• start with a minimal signature and evolve it piecemeal, e.g., along the lines Data.Seq?

I guess the real question is - should the canonical Deque be a typeclass or a concrete type?

[magnus-madsen]

I don't think we should start with a type class; rather I would identify the central operations, implement those, and then we can expand.