Hacker News Reader

Comment by gizmo686 | Hacker News Reader

>In fact, I would tell people - try not to use linked lists, because the notion of head and tail is an imperative concept that leaked into the functional world.

Citation needed. Haskell's most basic data structure is a singly-linked list. The concept of a linked list seems to fit quite well with functional programming, as adding an additional element is simply a matter of making an element that points back to the unchanged previous element. And, linked lists work very well with recursion, as you can process the head, then move on to the rest of the list.

Are you aware of a functional datatype that can store an arbitrary amount of information and is simpler than a linked-list?

View on HN

I got this idea from Guy Steele's keynote at Scala Days, named "What Fortress and Scala can learn from each other". For reference, Guy Steele worked on multiple programming languages, including Scheme and he can explain it better than me:

http://skillsmatter.com/podcast/scala/scala-days-keynote-301...

The gist of the matter is this - lists preserve insertion order (instead of the elements themselves having a natural order) and can only be accessed sequentially. You cannot easily split lists in two, or multiple chunks, which means we'll have a hard time doing automatic parallelizing of computations performed on linked lists.

Think of this simple expression:

    someList.filter(_ % 2 == 0).map(_ + 10)

If the underlying data-structure would be a balanced binary tree, you could easily split the work required in multiple threads. Because you're specifying the "what" instead of "how" and you can let the platform choose the best solution, like splitting it in threads or offloading that to a GPU, right? Well, linked list have the "how" encoded in them.

Maybe it helps to think of data-structures for what they really are: frozen algorithms.

Guy Steele is working on some pretty cool stuff in Fortress. Check that video out.

That makes sense. Still, I don't think its fair to say that linked lists are an imperative concept. While they lack one of the most mentioned advantages of functional programming, they still feel 'natural' in functional programming, not like they are borrowed from imperative.

Furthermore, I am not aware of another functional data structure which has O(1) append time, which allows us to construct lists element by element easily.

You can have amortized O(1) with trees for example. Appending elements to the end of Vectors in Scala or Clojure is done in amortized O(1), being a tree with a high branching factor. And I'm not sure how the immutable Queue is implemented in Scala, but it's also O(1) for queue() and dequeue() and it can't be a list.

It's true though, Lists are easy to implement, easy to reason about and speaking of frozen algorithms, you can view a linked list as being a frozen tail-recursion :-)

Linked lists are a good fit for functional languages, and arrays aren't a great fit: this can be a major obstacle to writing Haskell code that is both idiomatic and efficient.

Reply on news.ycombinator.com