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
