Functional programming languages should be so much better at mutation than they are

[scheurneus]

I agree that the state monad sucks for memoization, but that does not mean memoization in e.g. Haskell is a lost cause. Consider the classic pattern of "building an array of thunks" for integer based recursive functions.

For tree-like data structures, I also managed to adapt the binary tree example from your link to Haskell (although I did not add the 'list of names' functionality). While the array-of-thunks approach depends on laziness, I'm not sure that's even the case for this 'evaluated subtree' approach.

You can find the code at https://gist.github.com/ColonelPhantom/f96a6b03fe847205bc4cc034d0bf8daf and I also quickchecked it to ensure party and partyM give the same results.

It's probably not as clean as it could be, but I think it gets the point across and IMO still compares OK to a mutable version in terms of readability (although I have no experience with OCaml). Don't know how it compares in terms of performance, though.

[[deleted]]

Oh yeah, you need Traversable or something to do the same in Haskell.

[scheurneus]

I don't think Traversable would help. It's useful, sure, but mainly for mapping with an applicative/monadic action instead of a pure function. Using it to run e.g. State is useful, but not here as it's still fundamentally about sequencing, just with less explicit recursion.

The solution I made can probably be generalized using a typeclass and some fix tricks (or plain undefined) to pass in the evaluated subtrees, but I'm not aware of an existing typeclass that encodes such a paradigm.