5 ms·

Purely Functional Data Structures in Scala

86 points by vkostyukov 13y ago

chollida1 13y ago
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-Okasaki/dp/0521663504 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.
- rustc 13y ago
  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)?
  - jcurbo 13y ago
    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-Richard/dp/0521513383/ 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-Cormen/dp/0262033844/ http://www.amazon.com/Introduction-Algorithms-Thomas-H-Corme...) and the Algorithm Design Manual (http://www.amazon.com/Algorithm-Design-Manual-Steven-Skiena/dp/1849967202/ 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.
  - andrewcooke 13y ago
    i always liked http://www.amazon.com/The-Functional-Approach-Programming-Cousineau/dp/0521576814 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.
- zeckalpha 13y ago
  This calls for a Scala port.
- mtrimpe 13y ago
  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!
- gtani 13y ago
  or his PhD thesis from CMU which is the basis of the book http://programmers.stackexchange.com/questions/185411/whats-the-difference-in-content-between-chris-okasakis-1996-thesis-and-1999-bo http://programmers.stackexchange.com/questions/185411/whats-...
fooyc 13y ago
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?
- herge 13y ago
  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.
  - fooyc 13y ago
    That was my point :)
- lysium 13y ago
  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.

86 points by vkostyukov 13y ago

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-Okasaki/dp/0521663504 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.

rustc 13y ago
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)?
- jcurbo 13y ago
  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-Richard/dp/0521513383/ 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-Cormen/dp/0262033844/ http://www.amazon.com/Introduction-Algorithms-Thomas-H-Corme...) and the Algorithm Design Manual (http://www.amazon.com/Algorithm-Design-Manual-Steven-Skiena/dp/1849967202/ 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.
- andrewcooke 13y ago
  i always liked http://www.amazon.com/The-Functional-Approach-Programming-Cousineau/dp/0521576814 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.
zeckalpha 13y ago
This calls for a Scala port.
mtrimpe 13y ago
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!
gtani 13y ago
or his PhD thesis from CMU which is the basis of the book http://programmers.stackexchange.com/questions/185411/whats-the-difference-in-content-between-chris-okasakis-1996-thesis-and-1999-bo http://programmers.stackexchange.com/questions/185411/whats-...

fooyc 13y ago

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?

herge 13y ago
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.
- fooyc 13y ago
  That was my point :)
lysium 13y ago
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.