Hacker News Reader

Comment by olivia-banks | Hacker News Reader

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.

View on HN

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.

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.

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

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

Reply on news.ycombinator.com