[MrJohz]

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.

[kragen]

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?

[MrJohz]

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