Purely Functional Data Structures in Scala | Hacker News Reader

Purely Functional Data Structures in Scala

slideshare.net

86 pointsvkostyukov16 comments

Open articleView on HN

For those of you who have an interest in functional languages, let me throw out this book:

http://www.amazon.ca/Purely-Functional-Structures-Chris-Okas...

I just can't say enough good things about it. The code is in ml but there is a Haskell port of the data structures.

It's a small book so its easy to read and digest in a couple of weeks.

I've heard lots of good things about this book, it's on high priority on my "next to read" list.

Can you or anyone else recommend more books related to FP algorithms, concepts in general (which are not necessarily language specific)?

Same here, I came in to post about that exact book.

There's also Pearls of Functional Algorithm Design which I have yet to read. http://www.amazon.com/Pearls-Functional-Algorithm-Design-Ric...

In general you've got stuff like Introduction to Algorithms (http://www.amazon.com/Introduction-Algorithms-Thomas-H-Corme...) and the Algorithm Design Manual (http://www.amazon.com/Algorithm-Design-Manual-Steven-Skiena/...) both of which I have seen mentioned as good books. I'm in a grad school-level algorithms class that just started using the former (which is language agnostic, but we are doing our implementations in Java) and it looks pretty good to me.

i always liked http://www.amazon.com/The-Functional-Approach-Programming-Co... although it's quite old and uses ml (caml - imagine it's similar to ocaml, or even f#). in fact, i preferred it to SICP.

This calls for a Scala port.

Keep in mind though that (according to Odersky) Scala's data structures are based on an improved version of Okasaki's research.

It's still very much a mind-twisting and expanding book though!

or his PhD thesis from CMU which is the basis of the book

http://programmers.stackexchange.com/questions/185411/whats-...

Great slides. Very interesting because implementing immutable data structures is not obvious.

I'm having a hard time figuring out a use case for some of these purely functional structures.

For instance, the queue: if you dequeue concurrently, you end up dequeuing the same element twice:

    q Queue
    // thread A
    q, elem = q.dequeue()
    // thread B
    q, elem = q.dequeue()
    // elem can be the same in both A and B

If you enqueue concurrently, only one element will end up being enqueued:

    q Queue
    // thread A
    q = q.enqueue(elemA)
    // thread B
    q = q.enqueue(elemB)
    // only one of elemA or elemB is queued

So if the structure is useless for concurrency (without external synchronization), what's his purpose?

If both queues are immutable, enqueuing/dequeuing is just creating a new queue with/without the element in it.

So thread A and thread B can share the same queue, but will create two different queues (one for each thread) when enqueuing to it.

Now if you want to share a queue between two threads, you have to simply synchronize between the threads and share each of their current versions of the queue.

That was my point :)

Actually, concurrency is some of the use cases (among others). The structure is not useless at all, actually, the opposite is true. Further, I think your analysis is underspecified if not wrong.

If thread A and B share the same q initially, both will receive the same object when dequeuing. If they enqueue, both will end up with a different q: thread A's q will have elemA, thread B's q will have elemB. It does not matter whether the operations happen concurrently or not.

If thread A and B shared a non-functional data structure q, you would have to synchronize your queues between threads, otherwise "anything can happen". With functional data structures you only have to synchronize them when you actually want them to be synchronized (eg. A&B taking work orders from a common queue vs. A&B executing the same work orders twice in parallel). In addition, the synchronization involves only sharing the "current" data structure, no synchronization happens within the data structure's implementation.

I think the question was more of how oddly this goes with the "multiple workers placing data on a queue" or the "multiple workers taking data off of a queue." In either of those cases, there will still have to be synchronization over the queue/dequeue logic such that a workers contribution is accounted for correctly.

The only use case for the persistent container I can think of is specifically when the container is being passed around by multiple threads. That is, if your concern is what is going into the container, then a mutable version likely has you covered rather well. If your concern is, instead, on passing around the collection, the persistent ones have an advantage in reasoning. (Though, again, the common case of a queue is to be manipulated...)

You can use these to build persistent data structures. Since you never change anything, you always have all the previous versions of the datastructure available. This has applications in file systems (fe zfs,btrfs,...) or databases (CouchDB,....) For an introduction, take a look here: http://blog.incubaid.com/2011/10/03/what-are-you-playing-wit...

Immutable data structures let you use compare-and-swap to guarantee all updates to a shared reference are atomic. This can be a win if the amount of contention is low enough such that optimistically generating and setting the modified version usually succeeds, particularly if that modified version can be created in log or amortized constant time.

Another benefit is that since the data structures are immutable you can easily operate over snapshots of them with no worries as to what other threads are doing. This can make them easier to code against and can sometimes be much easier to deal with than locks since you avoid most deadlock/livelock problems that you usually have to worry about with locking, though if you're using straight-up CAS you do have to be mindful of the A-B-A problem.

Enuque/deque create new queues, so you can for example send them as messages or swap some mutable reference.

The purpose of purely functional data structures is generally not to be used as a shared, mutable source of data among multiple threads/processes. Hell, even in a single process, this kind of serial access results in the same situation. The point of a purely functional data structure is to be able to pass it to another method/thread/whatever, without having to worry that the data will be modified without the caller context expecting it..

In terms of the type of pattern you're talking about (something like producer/consumer), an appropriate pattern in Scala might be to use an actor with an internal mutable data structure. Actors receive messages in a synchronized manner, and can then distribute work as needed. If the majority of your data is immutable, then beyond config for number of threads and actor mailbox size, there's very little you need to worry about - contention, lock granularity and race conditions are essentially non-issues.

As a thought exercise, it would be possible to use an immutable queue with an actor for the above purpose. Create an actor that, when receiving a message containing an item to enqueue, waits until it receives a queue. When sent a message with a queue, it should take a message from the mailbox, enqueue it, then send the queue to a second actor. That actor will dequeue and operate on an item from its message, then send a message with the new queue (with one less item) to the original actor. The only time the original actor will do nothing is when it receives a message with an empty queue (which is how it will start, and also the state it will be in every time it has finished working its queue), in which case it will wait for an item to enqueue. Assuming that the "process a queue item" step is fast (as it should be), and the "wait for a queue" is not a busy wait (I think there is a way to do this with Akka), then this might actually be efficient. This is probably a bad idea though, just having fun thinking about how it would be possible. =)

Reply on news.ycombinator.com