Hacker News Reader

Comment by kristianp | Hacker News Reader

> * Like all FP languages it has a weird obsession with singly linked lists, which are actually a pretty awful data structure

This made me chuckle. I've had that thought before, shouldn't the default be a vector on modern devices? Of course other collection types are available.

View on HN

The reason why functional languages like linked lists so much is because they are very easy to make immutable without a lot of pain all around. If you implement an immutable vector in a straightforward way, though, you basically need to do a lot of copying for any operation that needs to construct one (the rigmarole with immutable strings, and existence of hacks such as StringBuilder, is a good illustration of the problem).

But you can have a data structure that is more like vector under the hood while still supporting efficient copy-with-modifications. Clojure vectors, for example.

That makes sense. But LinkedIn lists are horrible for cache efficient things no? I think there was an article on HN from a Golang perspective padding structs or something such that they are efficient wrt to cache hits.

> But LinkedIn lists are horrible for cache efficient things no?

LinkedIn Lists you say? (Sorry. (But not that sorry.))

Edit meta sidenote: in this modern meme world, it's virtually impossible to know if a typo is a typo or just a meme you haven't heard of yet.

LinkedIn lists will tell you they contain one new element, but you have to click on a link and scroll through their suggested new elements to see what it is

Do they also always end with an element that tells you what the LinkedIn list taught it about B2B sales?

lol my phone autocorrected ugh.

But you know what I mean. Some grace would be nice.

I know. It was just too hard to pass up. :)

Well you got me. I audibly groaned and slapped my forehead.

They are, but you don't tend to keep them around in memory long enough. Start consuming the front before you produce the back.

Which is a pity, you can fit entire small arrays in a cache line to end up with no pointer chasing at all.

I'd say that functional programming is probably one of the only domains where linked lists actually make sense. Vectors certainty have their use in more places though.

A good compiler will make the lists disappear in many cases. No runtime overhead. I actually love single linked lists as a way to break down sequences of problem steps.

In Haskell, yes, because laziness permits deforestation. ML, including OCaml, is eager and consequently cannot do this.

I believe it's possible in theory - Koka has a whole "functional but in-place" set of compiler optimisations that essentially translate functional algorithms into imperative ones. But I think that's also possible in Koka in part because of its ownership rules that track where objects are created and freed, so might also not be feasible for OCaml.

I mean, the set of valid deforestation transformations you could do to an OCaml program is not literally the empty set, but OCaml functions can do I/O, update refs, and throw exceptions, as well as failing to terminate, so you would have to be sure that none of the code you were running in the wrong order did any of those things. I don't think the garbage collection issues you mention are a problem, though maybe I don't understand them?

Part of what Koka's functional-but-in-place system relies on is the Perceus program analysis, which, as I understand it, is kind of like a limited Rust-like lifetime analysis which can determine statically the lifetime of different objects and whether they can be reused or discarded or whatever. That way, if you're, say, mapping over a linked list, rather than construct a whole new list for the new entries, the Koka compiler simply mutates the old list with the new values. You write a pure, functional algorithm, and Koka converts it to the imperative equivalent.

That said, I think this is somewhat unrelated to the idea of making linked lists disappear - Koka is still using linked lists, but optimising their allocation and deallocation, whereas Haskell can convert a linked list to an array and do a different set of optimisations there.

See: https://koka-lang.github.io/koka/doc/book.html#sec-fbip

Why would a specific way of structuring data in memory be relevant to breaking down sequences of problem steps?

If what you mean is the ability to think in terms of "first" and "rest", that's just an interface that doesn't have to be backed by a linked list implementation.

I’m curious what you mean. Surely there’s the overhead of unpredictable memory access?

Not GP but bump allocation (OCaml's GC uses a bump allocator into the young heap) mitigates this somewhat, list nodes tend to be allocated near each other. It is worse than the guaranteed contiguous access patterns of a vector, but it's not completely scattered either.

Ah yes, our old friend - the sufficiently smart compiler.

Reply on news.ycombinator.com