How many HOFs in Phobos?

[Andrei Alexandrescu]

On 2/1/11 7:17 PM, bearophile wrote:
> 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))))

I'd be glad to include such a function if there were good use cases for 
it. Fixed-point iteration is interesting in math, but in practice you 
don't just run it naively, e.g. you run it once and check for a 
termination condition (which may be quite involved when e.g. doing 
linear algebra; my dissertation uses a lot of fixed-point iteration).

To wit, the sin example sucks. At what time have you been at a point in 
life when you wanted to do not only a few iterations of sin against its 
own result, but actually you want to be able to express that very notion 
as a sole function? It at least you chose cos, I would have been more 
sympathetic because fixed point iteration it's a way to solving cos(x) = x.

SICP has if I remember correctly a couple of nice examples of iterations 
for computing pi and sqrt, but those are recurrences, not fixed point 
iterations. For that we already have std.range.recurrence which is more 
general. To do fixed point with sequence is trivial:

auto s = recurrence!"sin(a[n-1])"(1.0);

The main point is that there are very strong examples for recurrences.

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

I think better examples could be found for that one, but... still 
tenuous. What's wrong with array, take, and recurrence?

You _already_ have in D better abstractions that those you think you 
want to bring over from functional languages. You have edit distance 
that laughs Haskell's out the door, you have recurrence that makes 
iterate look like a useless oddity, you have range refinements that 
bring you the best of foldr without the cost...

> ------------------
>
> 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.

More like it spurs the language to allow better local instantiation.


Andrei