Hacker News new | ask | show | jobs
by ghj 2109 days ago
Mathematical abstractions are often at the wrong level of abstraction. Mathematicians mostly care about value semantics but programmers need to care about how it's realized in hardware too.

For example, sure, you can think of a list as a "monoid" where the add operator is concatenation of two list. But adding two lists is not a fast operation even using specialized functional data structures. So making concatenation a primitive for equational reasoning just results in really slow code.
2 comments
codygman 2109 days ago
> Mathematicians mostly care about value semantics but programmers need to care about how it's realized in hardware too.

Exactly! The thing is this book gives a method where you care about value semantics, keep the ideal representation, and then care later about how it's realized in the hardware!

link
contravariant 2109 days ago
I'm confused, with the right data structure concatenating lists is an O(1) operation.
link
ghj 2109 days ago
You're probably thinking of storing it as some linked list but that doesn't work with mathematical abstractions (which is my point).

For example in mathematics if you write "C = A + B" and then you ask what A is, it's still always going to be the same.

To make this work in programming you basically have to make all your data structures persistent[1]. AFAIK you would need a store the list as a finger tree or something if you need fast concatenation and that will still only be O(log(n)) [2].

[1] https://en.wikipedia.org/wiki/Persistent_data_structure

[2] http://hackage.haskell.org/package/fingertree-0.1.4.2/docs/D...

[3] https://stackoverflow.com/questions/28406512/why-does-concat...

link
leafboi 2109 days ago
In math everything is persistent/immutable anyway, so persistent data structures are a given when working with purely mathematical abstractions.

There is a memory issue because of this, but this problem isn't exclusive to FP languages. Many languages solve this with something called garbage collection.

link
leafboi 2109 days ago
The very definition of pure FP (which is basically just programming founded on the principles of mathematics) rest foundationally on just a program that is immutable and has no side effects. Those are the only two requirements needed to do FP.

Immutability is therefore the axiomatic foundation of FP.

link
contravariant 2109 days ago
You don't need a linked list you can just store C as 'A + B'.
link