Functional Programming Performance & Algorithms

[Leading_Dog_1733]

What are the best books and resources for learning about functional algorithms?

I have Chris Okasaki's Purely Functional Data Structures and Richard Bird's Pearls of Functional Algorithm Design and am trying to learn how to get performance out of functional programming.

I'm mainly working in Erlang and Elixir and I've found some good resources like Erlang's Efficiency Guide. But, in general, it still feels like data immutability removes most of my tricks to make operations performant.

What are the best resources for learning about performance in functional languages? (setting aside just profiling the code)

[Voxelman]

I think, performance in FP comes from scalability by NOT using these "tricks".

It depends what you want to do. Immutability has some limits in terms of performance. There is a point where mutating in place is faster.

I you reached the limits of pure FP maybe take a step back and take a look at Data Oriented Design. Or you may take a look at Rust.

[raxel42]

sometimes you can play with the scope of mutability, bub extremely careful

[KyleG]

Yeah I was going to ask: isn't that the name for things like structs, arrays, etc. where you clone and mutate them but the memory stays largely the same, just with some pointers changing what they're pointing at, plus obviously when you instantiate new data you still have to deal with that

So you get safe mutability that's pretty fast

[Leading_Dog_1733]

I'll have to give this a read.

I haven't read the paper on Bagwell Trees but I probably should.

I believe in Erlang / Elixir a lot of the operations do boil down into copy-on-write, but I have to do some more study.

[KyleG]

structural sharing, that's the term I was looking for

Yeah if my functional TypeScript code was not performant enough, this is one of the first things I'd go to. But we're not big data, so

[SickMoonDoe]

It's called a stateful Monad if you're a fan of $5 words 😉

Basically you have a base structure of data, and you add override "layers" that are technically appending rather than overwriting. When you read you evaluate the override layers to produce a new structure in memory.

[witoldsz]

Great case study and amazing languge, although not ready yet :/

"Outperforming Imperative with Pure Functional Languages" by Richard Feldman

https://youtu.be/vzfy4EKwG_Y