Re:Cache-Efficient Functional Algorithms (2014) [pdf]
by sctb on Saturday April 23, 2016 @11:33AM
(#11555959)
I would be very hesitant to accuse Robert Harper of misusing the term 'functional'. I'm not an expert in their field, but I interpret 'functional algorithm' to mean an algorithm whose inputs are transformed by successive applications of functions (in the mathematical sense.)
[ Parent
| on HN ]
Re:Cache-Efficient Functional Algorithms (2014) [pdf]
by fpoling on Saturday April 23, 2016 @12:46PM
(#11556264)
I guess I formulated not precisely enough. I have not tried to accuse anybody of misusing. From books that I read I got a strong impression that the term "functional programming" as a term is about treating functions as the first-class entities (or even the only entities). The persistent data structures is orthogonal to this. But I guess I just have to accept that in the field it is a common speak to use "functional algorithms" to mean "algorithms for persistent data structures".
Personally I see this as unfortunate as the persistence as a term IMO is much more precise. It also remains that one also needs GC and properly accounts its cost which this paper discuss a lot.
Re:Cache-Efficient Functional Algorithms (2014) [pdf]
by RcouF1uZ4gsC on Saturday April 23, 2016 @05:19PM
(#11557462)
The confusion is that you are thinking of function in the programming language sense (i.e. A subroutine ) rather than in the mathematical sense (i.e. A function called with the same arguments always returns the same value). The mathematic definition of function necessitates persistent data structures (i.e. You do not modify the dataset but return a new dataset with the modifications).
Re:Cache-Efficient Functional Algorithms (2014) [pdf]
by fpoling on Saturday April 23, 2016 @06:07PM
(#11557635)
Yet persistent data do not imply functional programming. For example, one can work with persistent data structures in Java using global variables to pass references to data structures. One can also implement algorithms from the article using explicit stack to avoid recursion. Yet such atrocities will not change the conclusion of the article that the code will be cache-efficient as long as the runtime is sufficiently smart.
So my assumption (which could be wrong) is that by using the word "functional" that article unnecessary restricts its auditory. For example, a Java programmer would not even bother to open it assuming this is something relevant at best to Haskell or F#. I definitely had such expectation.