All Comments
TopTalkedBooks posted at August 19, 2017
Yup. Purely Functional Data Structures (thesis as linked, book: https://www.amazon.com/Purely-Functional-Structures-Chris-Ok...) is awesome. I especially found some of the tree-based recursive algorithms eye-opening (once you spend the time to wrap your head around them).

IMHO required reading if you're doing any heavy FP work.

TopTalkedBooks posted at August 19, 2017
Going back to the basics to solidify my foundation, one each quarter. Good Practice makes one a better engineer!

Digital Electronics using [1] Operating Systems using [2] Functional Data Structures using [3] Graphics Algorithms [4]

Any recommendations for these subjects sincerely appreciated. Thanks.

[1] https://www.amazon.com/Digital-Design-Computer-Architecture-... [2] https://www.amazon.com/Modern-Operating-Systems-Andrew-Tanen... [3] https://www.amazon.com/Purely-Functional-Structures-Chris-Ok... [4] https://www.amazon.com/Graphics-Visualization-Principles-Alg...

The more you practice, the more you can, the more you want to, the more you enjoy it, the less it tires you.” ― Robert A. Heinlein, The Cat Who Walks Through Walls

TopTalkedBooks posted at August 19, 2017
For those of you who aren't familiar with the author's other works, it's worth taking a peek at his other books.

I can whole heatedly recommend Pearls of Functional Algorithm Design http://www.amazon.com/Pearls-Functional-Algorithm-Design-Ric...

It's a good cross between two other excellent books:

- Jon Bentley's Programming Pearls http://www.amazon.com/Programming-Pearls-2nd-Jon-Bentley/dp/...

and

- Chris Okasaki's Purely Function Data Structures http://www.amazon.com/Purely-Functional-Structures-Chris-Oka....

If you haven't read all three, its well worth your while to do so!

And of course if you are going down the rabbit hole of reading Perls of Functional Algorithm Design then you need to read the "how to read Pearls of Functional Algorithm design" as well.

http://www.atamo.com/blog/how-to-read-pearls-by-richard-bird...

TopTalkedBooks posted at August 20, 2017

I just keep the visited set as a set and pass it as a parameter. There are efficient log-time implementations of sets of any ordered type and extra-efficient sets of integers.

To represent a graph I use adjacency lists, or I'll use a finite map that maps each node to a list of its successors. It depends what I want to do.

Rather than Abelson and Sussman, I recommend Chris Okasaki's Purely Functional Data Structures. I've linked to Chris's dissertation, but if you have the money, he expanded it into an excellent book.


Just for grins, here's a slightly scary reverse postorder depth-first search done in continuation-passing style in Haskell. This is straight out of the Hoopl optimizer library:

postorder_dfs_from_except :: forall block e . (NonLocal block, LabelsPtr e)
                          => LabelMap (block C C) -> e -> LabelSet -> [block C C]
postorder_dfs_from_except blocks b visited =
 vchildren (get_children b) (\acc _visited -> acc) [] visited
 where
   vnode :: block C C -> ([block C C] -> LabelSet -> a) 
                      -> ([block C C] -> LabelSet -> a)
   vnode block cont acc visited =
        if setMember id visited then
            cont acc visited
        else
            let cont' acc visited = cont (block:acc) visited in
            vchildren (get_children block) cont' acc (setInsert id     visited)
      where id = entryLabel block
   vchildren bs cont acc visited = next bs acc visited
      where next children acc visited =
                case children of []     -> cont acc visited
                                 (b:bs) -> vnode b (next bs) acc     visited
   get_children block = foldr add_id [] $ targetLabels bloc
   add_id id rst = case lookupFact id blocks of
                      Just b -> b : rst
                      Nothing -> rst
TopTalkedBooks posted at August 20, 2017

It's because of immutable state. A list is an object + a pointer, so if we imagined a list as a Tuple it might look like this:

let tupleList = ("a", ("b", ("c", [])))

Now let's get the first item in this "list" with a "head" function. This head function takes O(1) time because we can use fst:

> fst tupleList

If we want to swap out the first item in the list with a different one we could do this:

let tupleList2 = ("x",snd tupleList)

Which can also be done in O(1). Why? Because absolutely no other element in the list stores a reference to the first entry. Because of immutable state, we now have two lists, tupleList and tupleList2. When we made tupleList2 we didn't copy the whole list. Because the original pointers are immutable we can continue to reference them but use something else at the start of our list.

Now let's try to get the last element of our 3 item list:

> snd . snd $ fst tupleList

That happened in O(3), which is equal to the length of our list i.e. O(n).

But couldn't we store a pointer to the last element in the list and access that in O(1)? To do that we would need an array, not a list. An array allows O(1) lookup time of any element as it is a primitive data structure implemented on a register level.

(ASIDE: If you're unsure of why we would use a Linked List instead of an Array then you should do some more reading about data structures, algorithms on data structures and Big-O time complexity of various operations like get, poll, insert, delete, sort, etc).

Now that we've established that, let's look at concatenation. Let's concat tupleList with a new list, ("e", ("f", [])). To do this we have to traverse the whole list just like getting the last element:

tupleList3 = (fst tupleList, (snd $ fst tupleList, (snd . snd $ fst tupleList, ("e", ("f", [])))

The above operation is actually worse than O(n) time, because for each element in the list we have to re-read the list up to that index. But if we ignore that for a moment and focus on the key aspect: in order to get to the last element in the list, we must traverse the entire structure.

You may be asking, why don't we just store in memory what the last list item is? That way appending to the end of the list would be done in O(1). But not so fast, we can't change the last list item without changing the entire list. Why?

Let's take a stab at how that might look:

data Queue a = Queue { last :: Queue a, head :: a, next :: Queue a} | Empty
appendEnd :: a -> Queue a -> Queue a
appendEnd a2 (Queue l, h, n) = ????

IF I modify "last", which is an immutable variable, I won't actually be modifying the pointer for the last item in the queue. I will be creating a copy of the last item. Everything else that referenced that original item, will continue referencing the original item.

So in order to update the last item in the queue, I have to update everything that has a reference to it. Which can only be done in optimally O(n) time.

So in our traditional list, we have our final item:

List a []

But if we want to change it, we make a copy of it. Now the second last item has a reference to an old version. So we need to update that item.

List a (List a [])

But if we update the second last item we make a copy of it. Now the third last item has an old reference. So we need to update that. Repeat until we get to the head of the list. And we come full circle. Nothing keeps a reference to the head of the list so editing that takes O(1).

This is the reason that Haskell doesn't have Doubly Linked Lists. It's also why a "Queue" (or at least a FIFO queue) can't be implemented in a traditional way. Making a Queue in Haskell involves some serious re-thinking of traditional data structures.

If you become even more curious about how all of this works, consider getting the book Purely Funtional Data Structures.

EDIT: If you've ever seen this: http://visualgo.net/list.html you might notice that in the visualization "Insert Tail" happens in O(1). But in order to do that we need to modify the final entry in the list to give it a new pointer. Updating a pointer mutates state which is not allowed in a purely functional language. Hopefully that was made clear with the rest of my post.

TopTalkedBooks posted at August 20, 2017

This would be a long answer, so please let me apologize in advance for pointing you towards a book and not directly answering. I highly recommend looking at Purely Functional Data Structures which is (legally) available as a PDF from the author. Though it's a good book to have in print/ebook anyway.

and the super short answer is use Clojure's built in sorted-map if you want this in practice (though writing your own will of course get nerd-street-cred) because sorted maps use a binary red-black-tree under the hood

TopTalkedBooks posted at August 20, 2017

You could try references to his book by Haskell or Clojure folk rather than just the CMU pdf : e.g.,

http://www.amazon.com/Purely-Functional-Structures-Chris-Okasaki/dp/0521663504

There was a question here on SO at :

What is the benefit of purely functional data structure?

There is also Clojure area this :

https://github.com/viksit/clojure-datastructures

And there was this on SE :

https://cstheory.stackexchange.com/questions/1539/whats-new-in-purely-functional-data-structures-since-okasaki

Hope something there provides a basis for a search that bears results :-)

You may have to use an academic or biz ref search engine and you may want to look at poster sessions at a conf because search is not obvious here, e.g., Mercury can generate Erlang code ... so searching caching and locality with respect to performance in functional programming in some hardware area dealing with latency.

Canada'a National Research Council (NRC) had some work going on ... you could try a search of their pub's/notices/reports

But note: a search with

bigdata latency locality NRC 2012

gives rather different result from

bigdata functional latency locality NSF 2012

( and I would next drop the 2012 and try using the google search tool date range option for recent results)

TopTalkedBooks posted at August 20, 2017

A related question was asked before: "Does functional programming replace GoF design patterns", with great responses.

The equivalent of "design patterns" is very vague in FP. In general, every time you see a "pattern" in your code you should create something to cover all of its uses in a uniform way. Often it will be a higher-order function.

For example, the following C code

for (int i = 0; i < n; i++)
  if (a[i] == 42)
    return true;
return false;

can be thought of some basic "design pattern" - checking if there's some special element on the list. This snippet could appear many times in code with different conditions. In FP, you simply use a higher order function several times. It's not a "pattern" anymore.

Functional programming has its own practices, but they are much different from "design patterns" in OOP. They include use of polymorphism, lists, higher-order functions, immutability/purity, laziness [not all are essential or specific to FP]... See also "what are core concepts of FP". Also, type classes (Haskell), modules and functors (OCaml), continuations, monads, zippers, finger trees, monoids, arrows, applicative functors, monad transformers, many purely functional data structures (book) etc. Functional pearls, already mentioned by Randall Schulz, form a very rich resource of FP at its best.

To learn how to write idiomatic code, any book/resource on a functional programming language will suffice IMHO (for example, RWH and LYAH); differences between thinking imperatively and functionally are always explained there.

In dynamic languages, Jeff Foster's link is a good collection; here is a very clever use of memoization in JavaScript that could be considered a "design pattern".

TopTalkedBooks posted at August 20, 2017

I don't think there's a shortcut here.

Just as you imply, Clojure's persistent data structures are quite a different thing from the immutable collections classes that Cocoa provides.

If you want to use Clojure's persistent data structures from Obj-C, the only way to do so is to re-implement them in Objective-C. My understand is that many of these are described in Okasaki's book, Purely Functional Data Structures, and in the papers of Phil Bagwell.

This other answer has some links: What is the data structure behind Clojure's sets?.

TopTalkedBooks posted at August 20, 2017
TopTalkedBooks posted at August 20, 2017

First of all, don't do premature optimisations. Have you measured your code? Maybe there is some concrete bottlenecks?

Since most of the objects consist of smaller objects joined via data stuctures, I think you can get rid of this problem by using persistent data structures .

persistent data structure is a data structure which always preserves the previous version of itself when it is modified; such data structures are effectively immutable, as their operations do not (visibly) update the structure in-place, but instead always yield a new updated structure

Here is wonderful talk about some of them by Daniel Spiewak. If you want more, take a look on Purely Functional Data Structures by Chris Okasaki.

TopTalkedBooks posted at August 20, 2017

This article, Haskell: Queues without pointers, describes a purely functional queue with O(1) amortized cost (edit: for adding and removing elements). I think the data structure comes from Chris Okasaki and more details are in his book.

The basic idea is to decompose the queue into two lists, one for the front and one for the back. New elements are added to "front". "Back" is stored in reverse order, to facilitate popping elements. When all elements of "back" are gone, "front" is reversed and re-identified as "back". This data structure has O(1) amortized cost for these operations, but apparently with some work it can be reduced to O(1), proper.

Edit: Okasaki's paper describes an elegant, purely functional implementation of queues and double-ended queues (deques). Deques allow adding or removing elements from either end. All such operations are O(1), worst case.

TopTalkedBooks posted at August 20, 2017
The canonical text discussing how this is achieved refers to data structures optimized for immutability as "purely functional data structures". [1] These type of data structures are the default for Clojure as well, and there are a number of blog posts and presentations discussing their implementation. [2] [3]

It's a reasonably complicated topic, but the basic idea is that since the data structures are immutable, much of their structure can be shared between versions with few changes. Most of these data structures end up using a Tree of some sort. Performance characteristics can be influenced to an extent by using bucketing to control the width/height of the tree.

[1] : Purely Functional Data Structures (Amazon: https://www.amazon.com/Purely-Functional-Structures-Chris-Ok...) [2] http://hypirion.com/musings/understanding-persistent-vector-... [3] https://www.youtube.com/watch?v=7BFF50BHPPo

TopTalkedBooks posted at December 12, 2017
> A data structure cannot be functional.

I think the author is using the term "purely functional data structure" to mean a data structure that lends itself to an implementation in a purely functional language [1,2].

[1] https://www.amazon.com/Purely-Functional-Structures-Chris-Ok...

Top Books
We collected top books from hacker news, stack overflow, Reddit, which are recommended by amazing people.