4 ms·
>... 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
by ReleaseCandidat 3y ago
>... 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).
- dvektor 3y agoNotice the ! in "!significant whitespace" I thought I was being slick
- ReleaseCandidat 3y agoOh, sorry. I've read that as "non-lazy whitespace" ;)
- Jaxan 3y agoIn 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.
- momentoftop 3y agoYou 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.
- ReleaseCandidat 3y agoYes 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 ;).