How many HOFs in Phobos?

[bearophile]

Jonathan M Davis:

>The issue is that if you want something in Phobos, it _does_ need to be designed with performance in mind. Anything which isn't efficient needs to have a very good reason for its existence which balances out its lack of efficiency. If the Haskell implementation isn't performant enough, then it doesn't cut it for Phobos, even if it's a good fit for Haskell.<

I think you have misunderstood the discussion, or maybe I just don't understand you.

My discussion was about HOFs, not about Levenshtein distance (I've shown a fast one, but it's probably not usable for Phobos because of license issues: http://codepad.org/s0ezEojU ).

---------------------

Andrei:

>The fact that foldl and foldr are only one letter apart is a design mistake.<

I agree, mostly :-)


>But something like foldr that uses head recursion would be indeed rather dangerous to include.<

>std.algorithm.reduce implements foldl, as it should. Simulating foldr on bidirectional ranges is as easy as reduce(retro(range)). Defining Haskell-style foldr on forward ranges would be difficult because it needs lazy evaluation through and through, and is at danger because people may use it naively.

Python2 has only the foldr, probably to keep language simpler & safer to use. Python3 has moved reduce from the language to the std library.

So far I have needed both kinds of folds in D only to translate some small programs from Haskell to D (and in this case I have even once confused the two folds, as you have noted), so probably I will be able to survive without a (better renamed) foldr in Phobos, if you don't want it for "safety" for naive programmers.

------------------

But there are other HOFs that may be useful (they are in dlibs1 too):

- "nest" (or iterate), to apply one function many times:
nest(sin, 0.2, 4) === sin(sin(sin(sin(0.2))))

- Something similar, that keeps all the intermediate results. It's sometimes named nestList, but in D it may be lazy.

------------------

There is another problem, shown by std.functional.compose. See the part about D here:
http://rosettacode.org/wiki/First-class_functions#D

This task asks things like (more details on the rosettacode page):
- Create new functions from preexisting functions at run-time
- Store functions in collections
- Use functions as arguments to other functions
- Use functions as return values of other functions 


To do it "well enough" the D implementation doesn't want to use std.functional.compose and defines a more dynamic one, able to use run time delegates:


private import std.math ;
import std.stdio ;
 
T delegate(S) compose(T, U, S)(T delegate(U) f, U delegate(S) g) {
    return (S s) { return f(g(s)); };
}
 
void main() {
	// warper need as not all built-in real functions 
	// have same signature , eg pure/nothrow
	auto sin  = delegate (real x) { return std.math.sin(x) ; } ;
	auto asin = delegate (real x) { return std.math.asin(x) ; } ;
	auto cos  = delegate (real x) { return std.math.cos(x) ; } ;
	auto acos = delegate (real x) { return std.math.acos(x) ; } ;
	auto cube = delegate (real x) { return x*x*x ; } ;
	auto cbrt = delegate (real x) { return std.math.cbrt(x) ; } ;
 
	// built-in : sin/cos/asin/acos/cbrt user:cube
	auto fun = [sin,  cos,  cube] ;
	auto inv = [asin, acos, cbrt] ;
 
	foreach(i, f ; fun)
		writefln("%6.3f", compose(f, inv[i])(0.5)) ;
}


You are able to write a similar program with std.functional.compose too, but using tuples instead of arrays, this is less flexible:

import std.stdio, std.typetuple, std.functional;
private import std.math;
 
void main() {
    // wrappers needed as not all built-in functions
    // have same signature, eg pure/nothrow
    auto sin  = (real x) { return std.math.sin(x); };
    auto asin = (real x) { return std.math.asin(x); };
    auto cos  = (real x) { return std.math.cos(x); };
    auto acos = (real x) { return std.math.acos(x); };
    auto cube = (real x) { return x ^^ 3; };
    auto cbrt = (real x) { return std.math.cbrt(x); };
 
    alias TypeTuple!(sin,  cos,  cube) dir;
    alias TypeTuple!(asin, acos, cbrt) inv;
 
    foreach (i, f; dir)
        writefln("%6.3f", compose!(f, inv[i])(0.5));
}


This questions the design of std.functional.compose.

Bye,
bearophile