Hacker News Reader

Comment by ReleaseCandidat | Hacker News Reader

>... linked lists are slow and inefficient with modern CPU caches, and you should almost never use them

You should not use them most of the time in functional languages (like OCaml and Haskell and...) for this reasons either, it's just that (almost) all examples for beginners use them because they are "easier" than for example trees.

Oh, by the way, OCaml does not have significant whitespace (but e.g.F# and Haskell do).

View on HN

You use them all the time in Haskell and OCaml. Cache locality isn't such an issue. You're not mallocing linked list nodes. You allocate by a pointer bump of the minor heap, and if the GC copies your list into the major heap, it's going to copy the list elements together.

You also use recursion all the time, and no, recursion is not generally straightforwardly optimised into iteration unless you're doing trivial tail recursion.

Yes I know and at least GHC optimizes lists better than most other data structures (I guess even isomorphic ones). But I guess your definition of "all the time" is not the samé as mine (yes, I use them in every project too). What I wanted to express is that lists are way less used than beginner tutorials may make it seem and there are other data structures available (like in other languages ;).

In Haskell you typically don’t allocate any memory when using the default list type, because of laziness. The it’s totally fine and efficient. Just don’t use it to store data for later retrieval.

Notice the ! in "!significant whitespace"

I thought I was being slick

Oh, sorry. I've read that as "non-lazy whitespace" ;)

Reply on news.ycombinator.com