1 // Written in the D programming language.
4 Functions that manipulate other functions.
6 This module provides functions for compile time function composition. These
7 functions are helpful when constructing predicates for the algorithms in
8 $(MREF std, algorithm) or $(MREF std, range).
10 $(SCRIPT inhibitQuickIndex = 1;)
12 $(TR $(TH Function Name) $(TH Description)
14 $(TR $(TD $(LREF adjoin))
15 $(TD Joins a couple of functions into one that executes the original
16 functions independently and returns a tuple with all the results.
18 $(TR $(TD $(LREF compose), $(LREF pipe))
19 $(TD Join a couple of functions into one that executes the original
20 functions one after the other, using one function's result for the next
23 $(TR $(TD $(LREF forward))
24 $(TD Forwards function arguments while saving ref-ness.
26 $(TR $(TD $(LREF lessThan), $(LREF greaterThan), $(LREF equalTo))
27 $(TD Ready-made predicate functions to compare two values.
29 $(TR $(TD $(LREF memoize))
30 $(TD Creates a function that caches its result for fast re-evaluation.
32 $(TR $(TD $(LREF not))
33 $(TD Creates a function that negates another.
35 $(TR $(TD $(LREF partial))
36 $(TD Creates a function that binds the first argument of a given function
39 $(TR $(TD $(LREF reverseArgs), $(LREF binaryReverseArgs))
40 $(TD Predicate that reverses the order of its arguments.
42 $(TR $(TD $(LREF toDelegate))
43 $(TD Converts a callable to a delegate.
45 $(TR $(TD $(LREF unaryFun), $(LREF binaryFun))
46 $(TD Create a unary or binary function from a string. Most often
47 used when defining algorithms on ranges.
51 Copyright: Copyright Andrei Alexandrescu 2008 - 2009.
52 License: $(HTTP boost.org/LICENSE_1_0.txt, Boost License 1.0).
53 Authors: $(HTTP erdani.org, Andrei Alexandrescu)
54 Source: $(PHOBOSSRC std/_functional.d)
57 Copyright Andrei Alexandrescu 2008 - 2009.
58 Distributed under the Boost Software License, Version 1.0.
59 (See accompanying file LICENSE_1_0.txt or copy at
60 http://www.boost.org/LICENSE_1_0.txt)
62 module std.functional;
64 import std.meta; // AliasSeq, Reverse
65 import std.traits; // isCallable, Parameters
68 private template needOpCallAlias(alias fun)
70 /* Determine whether or not unaryFun and binaryFun need to alias to fun or
71 * fun.opCall. Basically, fun is a function object if fun(...) compiles. We
72 * want is(unaryFun!fun) (resp., is(binaryFun!fun)) to be true if fun is
73 * any function object. There are 4 possible cases:
75 * 1) fun is the type of a function object with static opCall;
76 * 2) fun is an instance of a function object with static opCall;
77 * 3) fun is the type of a function object with non-static opCall;
78 * 4) fun is an instance of a function object with non-static opCall.
80 * In case (1), is(unaryFun!fun) should compile, but does not if unaryFun
81 * aliases itself to fun, because typeof(fun) is an error when fun itself
82 * is a type. So it must be aliased to fun.opCall instead. All other cases
83 * should be aliased to fun directly.
85 static if (is(typeof(fun.opCall) == function))
87 enum needOpCallAlias = !is(typeof(fun)) && __traits(compiles, () {
88 return fun(Parameters!fun.init);
92 enum needOpCallAlias = false;
96 Transforms a string representing an expression into a unary
97 function. The string must either use symbol name $(D a) as
98 the parameter or provide the symbol via the $(D parmName) argument.
99 If $(D fun) is not a string, $(D unaryFun) aliases itself away to $(D fun).
102 template unaryFun(alias fun, string parmName = "a")
104 static if (is(typeof(fun) : string))
106 static if (!fun._ctfeMatchUnary(parmName))
108 import std.algorithm, std.conv, std.exception, std.math, std.range, std.string;
109 import std.meta, std.traits, std.typecons;
111 auto unaryFun(ElementType)(auto ref ElementType __a)
113 mixin("alias " ~ parmName ~ " = __a ;");
117 else static if (needOpCallAlias!fun)
120 alias unaryFun = fun.opCall;
124 alias unaryFun = fun;
131 // Strings are compiled into functions:
132 alias isEven = unaryFun!("(a & 1) == 0");
133 assert(isEven(2) && !isEven(1));
138 static int f1(int a) { return a + 1; }
139 static assert(is(typeof(unaryFun!(f1)(1)) == int));
140 assert(unaryFun!(f1)(41) == 42);
141 int f2(int a) { return a + 1; }
142 static assert(is(typeof(unaryFun!(f2)(1)) == int));
143 assert(unaryFun!(f2)(41) == 42);
144 assert(unaryFun!("a + 1")(41) == 42);
145 //assert(unaryFun!("return a + 1;")(41) == 42);
148 assert(unaryFun!"a + 1"(num) == 42);
153 static bool opCall(int n) { return true; }
155 static assert(needOpCallAlias!Seen);
156 static assert(is(typeof(unaryFun!Seen(1))));
157 assert(unaryFun!Seen(1));
160 static assert(!needOpCallAlias!s);
161 static assert(is(typeof(unaryFun!s(1))));
162 assert(unaryFun!s(1));
166 bool opCall(int n) { return true; }
169 static assert(!needOpCallAlias!fo);
170 static assert(is(typeof(unaryFun!fo)));
171 assert(unaryFun!fo(1));
173 // Function object with non-static opCall can only be called with an
174 // instance, not with merely the type.
175 static assert(!is(typeof(unaryFun!FuncObj)));
179 Transforms a string representing an expression into a binary function. The
180 string must either use symbol names $(D a) and $(D b) as the parameters or
181 provide the symbols via the $(D parm1Name) and $(D parm2Name) arguments.
182 If $(D fun) is not a string, $(D binaryFun) aliases itself away to
186 template binaryFun(alias fun, string parm1Name = "a",
187 string parm2Name = "b")
189 static if (is(typeof(fun) : string))
191 static if (!fun._ctfeMatchBinary(parm1Name, parm2Name))
193 import std.algorithm, std.conv, std.exception, std.math, std.range, std.string;
194 import std.meta, std.traits, std.typecons;
196 auto binaryFun(ElementType1, ElementType2)
197 (auto ref ElementType1 __a, auto ref ElementType2 __b)
199 mixin("alias "~parm1Name~" = __a ;");
200 mixin("alias "~parm2Name~" = __b ;");
204 else static if (needOpCallAlias!fun)
207 alias binaryFun = fun.opCall;
211 alias binaryFun = fun;
218 alias less = binaryFun!("a < b");
219 assert(less(1, 2) && !less(2, 1));
220 alias greater = binaryFun!("a > b");
221 assert(!greater("1", "2") && greater("2", "1"));
226 static int f1(int a, string b) { return a + 1; }
227 static assert(is(typeof(binaryFun!(f1)(1, "2")) == int));
228 assert(binaryFun!(f1)(41, "a") == 42);
229 string f2(int a, string b) { return b ~ "2"; }
230 static assert(is(typeof(binaryFun!(f2)(1, "1")) == string));
231 assert(binaryFun!(f2)(1, "4") == "42");
232 assert(binaryFun!("a + b")(41, 1) == 42);
234 //assert(binaryFun!("return a + b;")(41, 1) == 42);
239 static bool opCall(int x, int y) { return true; }
241 static assert(is(typeof(binaryFun!Seen)));
242 assert(binaryFun!Seen(1,1));
246 bool opCall(int x, int y) { return true; }
249 static assert(!needOpCallAlias!fo);
250 static assert(is(typeof(binaryFun!fo)));
251 assert(unaryFun!fo(1,1));
253 // Function object with non-static opCall can only be called with an
254 // instance, not with merely the type.
255 static assert(!is(typeof(binaryFun!FuncObj)));
258 // skip all ASCII chars except a .. z, A .. Z, 0 .. 9, '_' and '.'.
259 private uint _ctfeSkipOp(ref string op)
261 if (!__ctfe) assert(false);
262 import std.ascii : isASCII, isAlphaNum;
263 immutable oldLength = op.length;
266 immutable front = op[0];
267 if (front.isASCII() && !(front.isAlphaNum() || front == '_' || front == '.'))
272 return oldLength != op.length;
276 private uint _ctfeSkipInteger(ref string op)
278 if (!__ctfe) assert(false);
279 import std.ascii : isDigit;
280 immutable oldLength = op.length;
283 immutable front = op[0];
289 return oldLength != op.length;
293 private uint _ctfeSkipName(ref string op, string name)
295 if (!__ctfe) assert(false);
296 if (op.length >= name.length && op[0 .. name.length] == name)
298 op = op[name.length..$];
304 // returns 1 if $(D fun) is trivial unary function
305 private uint _ctfeMatchUnary(string fun, string name)
307 if (!__ctfe) assert(false);
311 immutable h = fun._ctfeSkipName(name) + fun._ctfeSkipInteger();
319 if (!fun._ctfeSkipOp())
325 return fun.length == 0;
330 static assert(!_ctfeMatchUnary("sqrt(Ñ‘)", "Ñ‘"));
331 static assert(!_ctfeMatchUnary("Ñ‘.sqrt", "Ñ‘"));
332 static assert(!_ctfeMatchUnary(".Ñ‘+Ñ‘", "Ñ‘"));
333 static assert(!_ctfeMatchUnary("_Ñ‘+Ñ‘", "Ñ‘"));
334 static assert(!_ctfeMatchUnary("Ñ‘Ñ‘", "Ñ‘"));
335 static assert(_ctfeMatchUnary("a+a", "a"));
336 static assert(_ctfeMatchUnary("a + 10", "a"));
337 static assert(_ctfeMatchUnary("4 == a", "a"));
338 static assert(_ctfeMatchUnary("2 == a", "a"));
339 static assert(_ctfeMatchUnary("1 != a", "a"));
340 static assert(_ctfeMatchUnary("a != 4", "a"));
341 static assert(_ctfeMatchUnary("a< 1", "a"));
342 static assert(_ctfeMatchUnary("434 < a", "a"));
343 static assert(_ctfeMatchUnary("132 > a", "a"));
344 static assert(_ctfeMatchUnary("123 >a", "a"));
345 static assert(_ctfeMatchUnary("a>82", "a"));
346 static assert(_ctfeMatchUnary("Ñ‘>82", "Ñ‘"));
347 static assert(_ctfeMatchUnary("Ñ‘[Ñ‘(Ñ‘)]", "Ñ‘"));
348 static assert(_ctfeMatchUnary("Ñ‘[21]", "Ñ‘"));
351 // returns 1 if $(D fun) is trivial binary function
352 private uint _ctfeMatchBinary(string fun, string name1, string name2)
354 if (!__ctfe) assert(false);
358 immutable h = fun._ctfeSkipName(name1) + fun._ctfeSkipName(name2) + fun._ctfeSkipInteger();
366 if (!fun._ctfeSkipOp())
372 return fun.length == 0;
378 static assert(!_ctfeMatchBinary("sqrt(Ñ‘)", "Ñ‘", "b"));
379 static assert(!_ctfeMatchBinary("Ñ‘.sqrt", "Ñ‘", "b"));
380 static assert(!_ctfeMatchBinary(".Ñ‘+Ñ‘", "Ñ‘", "b"));
381 static assert(!_ctfeMatchBinary("_Ñ‘+Ñ‘", "Ñ‘", "b"));
382 static assert(!_ctfeMatchBinary("Ñ‘Ñ‘", "Ñ‘", "b"));
383 static assert(_ctfeMatchBinary("a+a", "a", "b"));
384 static assert(_ctfeMatchBinary("a + 10", "a", "b"));
385 static assert(_ctfeMatchBinary("4 == a", "a", "b"));
386 static assert(_ctfeMatchBinary("2 == a", "a", "b"));
387 static assert(_ctfeMatchBinary("1 != a", "a", "b"));
388 static assert(_ctfeMatchBinary("a != 4", "a", "b"));
389 static assert(_ctfeMatchBinary("a< 1", "a", "b"));
390 static assert(_ctfeMatchBinary("434 < a", "a", "b"));
391 static assert(_ctfeMatchBinary("132 > a", "a", "b"));
392 static assert(_ctfeMatchBinary("123 >a", "a", "b"));
393 static assert(_ctfeMatchBinary("a>82", "a", "b"));
394 static assert(_ctfeMatchBinary("Ñ‘>82", "Ñ‘", "q"));
395 static assert(_ctfeMatchBinary("Ñ‘[Ñ‘(10)]", "Ñ‘", "q"));
396 static assert(_ctfeMatchBinary("Ñ‘[21]", "Ñ‘", "q"));
398 static assert(!_ctfeMatchBinary("sqrt(Ñ‘)+b", "b", "Ñ‘"));
399 static assert(!_ctfeMatchBinary("Ñ‘.sqrt-b", "b", "Ñ‘"));
400 static assert(!_ctfeMatchBinary(".Ñ‘+b", "b", "Ñ‘"));
401 static assert(!_ctfeMatchBinary("_b+Ñ‘", "b", "Ñ‘"));
402 static assert(!_ctfeMatchBinary("ba", "b", "a"));
403 static assert(_ctfeMatchBinary("a+b", "b", "a"));
404 static assert(_ctfeMatchBinary("a + b", "b", "a"));
405 static assert(_ctfeMatchBinary("b == a", "b", "a"));
406 static assert(_ctfeMatchBinary("b == a", "b", "a"));
407 static assert(_ctfeMatchBinary("b != a", "b", "a"));
408 static assert(_ctfeMatchBinary("a != b", "b", "a"));
409 static assert(_ctfeMatchBinary("a< b", "b", "a"));
410 static assert(_ctfeMatchBinary("b < a", "b", "a"));
411 static assert(_ctfeMatchBinary("b > a", "b", "a"));
412 static assert(_ctfeMatchBinary("b >a", "b", "a"));
413 static assert(_ctfeMatchBinary("a>b", "b", "a"));
414 static assert(_ctfeMatchBinary("Ñ‘>b", "b", "Ñ‘"));
415 static assert(_ctfeMatchBinary("b[Ñ‘(-1)]", "b", "Ñ‘"));
416 static assert(_ctfeMatchBinary("Ñ‘[-21]", "b", "Ñ‘"));
420 template safeOp(string S)
421 if (S=="<"||S==">"||S=="<="||S==">="||S=="=="||S=="!=")
423 import std.traits : isIntegral;
424 private bool unsafeOp(ElementType1, ElementType2)(ElementType1 a, ElementType2 b) pure
425 if (isIntegral!ElementType1 && isIntegral!ElementType2)
427 import std.traits : CommonType;
428 alias T = CommonType!(ElementType1, ElementType2);
429 return mixin("cast(T)a "~S~" cast(T) b");
432 bool safeOp(T0, T1)(auto ref T0 a, auto ref T1 b)
434 import std.traits : mostNegative;
435 static if (isIntegral!T0 && isIntegral!T1 &&
436 (mostNegative!T0 < 0) != (mostNegative!T1 < 0))
438 static if (S == "<=" || S == "<")
440 static if (mostNegative!T0 < 0)
441 immutable result = a < 0 || unsafeOp(a, b);
443 immutable result = b >= 0 && unsafeOp(a, b);
447 static if (mostNegative!T0 < 0)
448 immutable result = a >= 0 && unsafeOp(a, b);
450 immutable result = b < 0 || unsafeOp(a, b);
455 static assert(is(typeof(mixin("a "~S~" b"))),
456 "Invalid arguments: Cannot compare types " ~ T0.stringof ~ " and " ~ T1.stringof ~ ".");
458 immutable result = mixin("a "~S~" b");
464 @safe unittest //check user defined types
466 import std.algorithm.comparison : equal;
470 auto opEquals(Foo foo)
475 assert(safeOp!"!="(Foo(1), Foo(2)));
479 Predicate that returns $(D_PARAM a < b).
480 Correctly compares signed and unsigned integers, ie. -1 < 2U.
482 alias lessThan = safeOp!"<";
485 pure @safe @nogc nothrow unittest
487 assert(lessThan(2, 3));
488 assert(lessThan(2U, 3U));
489 assert(lessThan(2, 3.0));
490 assert(lessThan(-2, 3U));
491 assert(lessThan(2, 3U));
492 assert(!lessThan(3U, -2));
493 assert(!lessThan(3U, 2));
494 assert(!lessThan(0, 0));
495 assert(!lessThan(0U, 0));
496 assert(!lessThan(0, 0U));
500 Predicate that returns $(D_PARAM a > b).
501 Correctly compares signed and unsigned integers, ie. 2U > -1.
503 alias greaterThan = safeOp!">";
508 assert(!greaterThan(2, 3));
509 assert(!greaterThan(2U, 3U));
510 assert(!greaterThan(2, 3.0));
511 assert(!greaterThan(-2, 3U));
512 assert(!greaterThan(2, 3U));
513 assert(greaterThan(3U, -2));
514 assert(greaterThan(3U, 2));
515 assert(!greaterThan(0, 0));
516 assert(!greaterThan(0U, 0));
517 assert(!greaterThan(0, 0U));
521 Predicate that returns $(D_PARAM a == b).
522 Correctly compares signed and unsigned integers, ie. !(-1 == ~0U).
524 alias equalTo = safeOp!"==";
529 assert(equalTo(0U, 0));
530 assert(equalTo(0, 0U));
531 assert(!equalTo(-1, ~0U));
534 N-ary predicate that reverses the order of arguments, e.g., given
535 $(D pred(a, b, c)), returns $(D pred(c, b, a)).
537 template reverseArgs(alias pred)
539 auto reverseArgs(Args...)(auto ref Args args)
540 if (is(typeof(pred(Reverse!args))))
542 return pred(Reverse!args);
549 alias gt = reverseArgs!(binaryFun!("a < b"));
550 assert(gt(2, 1) && !gt(1, 1));
552 bool xyz(int a, int b) { return a * x < b / x; }
555 alias zyx = reverseArgs!(foo);
556 assert(zyx(5, 4) == foo(4, 5));
562 int abc(int a, int b, int c) { return a * b + c; }
563 alias cba = reverseArgs!abc;
564 assert(abc(91, 17, 32) == cba(32, 17, 91));
570 int a(int a) { return a * 2; }
571 alias _a = reverseArgs!a;
572 assert(a(2) == _a(2));
578 int b() { return 4; }
579 alias _b = reverseArgs!b;
584 Binary predicate that reverses the order of arguments, e.g., given
585 $(D pred(a, b)), returns $(D pred(b, a)).
587 template binaryReverseArgs(alias pred)
589 auto binaryReverseArgs(ElementType1, ElementType2)
590 (auto ref ElementType1 a, auto ref ElementType2 b)
599 alias gt = binaryReverseArgs!(binaryFun!("a < b"));
600 assert(gt(2, 1) && !gt(1, 1));
607 bool xyz(int a, int b) { return a * x < b / x; }
610 alias zyx = binaryReverseArgs!(foo);
611 assert(zyx(5, 4) == foo(4, 5));
615 Negates predicate $(D pred).
617 template not(alias pred)
619 auto not(T...)(auto ref T args)
621 static if (is(typeof(!pred(args))))
623 else static if (T.length == 1)
624 return !unaryFun!pred(args);
625 else static if (T.length == 2)
626 return !binaryFun!pred(args);
635 import std.algorithm.searching : find;
636 import std.functional;
637 import std.uni : isWhite;
638 string a = " Hello, world!";
639 assert(find!(not!isWhite)(a) == "Hello, world!");
644 assert(not!"a != 5"(5));
645 assert(not!"a != b"(5, 5));
647 assert(not!(() => false)());
648 assert(not!(a => a != 5)(5));
649 assert(not!((a, b) => a != b)(5, 5));
650 assert(not!((a, b, c) => a * b * c != 125 )(5, 5, 5));
654 $(LINK2 http://en.wikipedia.org/wiki/Partial_application, Partially
655 applies) $(D_PARAM fun) by tying its first argument to $(D_PARAM arg).
657 template partial(alias fun, alias arg)
659 static if (is(typeof(fun) == delegate) || is(typeof(fun) == function))
661 import std.traits : ReturnType;
662 ReturnType!fun partial(Parameters!fun[1..$] args2)
664 return fun(arg, args2);
669 auto partial(Ts...)(Ts args2)
671 static if (is(typeof(fun(arg, args2))))
673 return fun(arg, args2);
677 static string errormsg()
679 string msg = "Cannot call '" ~ fun.stringof ~ "' with arguments " ~
682 msg ~= ", " ~ T.stringof;
686 static assert(0, errormsg());
695 int fun(int a, int b) { return a + b; }
696 alias fun5 = partial!(fun, 5);
697 assert(fun5(6) == 11);
698 // Note that in most cases you'd use an alias instead of a value
699 // assignment. Using an alias allows you to partially evaluate template
700 // functions without committing to a particular type of the function.
703 // tests for partially evaluating callables
706 static int f1(int a, int b) { return a + b; }
707 assert(partial!(f1, 5)(6) == 11);
709 int f2(int a, int b) { return a + b; }
711 assert(partial!(f2, x)(6) == 11);
713 assert(partial!(f2, x)(6) == 13);
714 static assert(partial!(f2, 5)(6) == 11);
717 auto f3 = &partial!(dg, x);
720 static int funOneArg(int a) { return a; }
721 assert(partial!(funOneArg, 1)() == 1);
723 static int funThreeArgs(int a, int b, int c) { return a + b + c; }
724 alias funThreeArgs1 = partial!(funThreeArgs, 1);
725 assert(funThreeArgs1(2, 3) == 6);
726 static assert(!is(typeof(funThreeArgs1(2))));
729 alias fe = partial!(f2, xe);
730 static assert(fe(6) == 11);
733 // tests for partially evaluating templated/overloaded callables
736 static auto add(A, B)(A x, B y)
741 alias add5 = partial!(add, 5);
742 assert(add5(6) == 11);
743 static assert(!is(typeof(add5())));
744 static assert(!is(typeof(add5(6, 7))));
746 // taking address of templated partial evaluation needs explicit type
747 auto dg = &add5!(int);
751 alias addX = partial!(add, x);
752 assert(addX(6) == 11);
754 static struct Callable
756 static string opCall(string a, string b) { return a ~ b; }
757 int opCall(int a, int b) { return a * b; }
758 double opCall(double a, double b) { return a + b; }
761 assert(partial!(Callable, "5")("6") == "56");
762 assert(partial!(callable, 5)(6) == 30);
763 assert(partial!(callable, 7.0)(3.0) == 7.0 + 3.0);
765 static struct TCallable
767 auto opCall(A, B)(A a, B b)
773 assert(partial!(tcallable, 5)(6) == 11);
774 static assert(!is(typeof(partial!(tcallable, "5")(6))));
776 static A funOneArg(A)(A a) { return a; }
777 alias funOneArg1 = partial!(funOneArg, 1);
778 assert(funOneArg1() == 1);
780 static auto funThreeArgs(A, B, C)(A a, B b, C c) { return a + b + c; }
781 alias funThreeArgs1 = partial!(funThreeArgs, 1);
782 assert(funThreeArgs1(2, 3) == 6);
783 static assert(!is(typeof(funThreeArgs1(1))));
785 auto dg2 = &funOneArg1!();
790 Takes multiple functions and adjoins them together. The result is a
791 $(REF Tuple, std,typecons) with one element per passed-in function. Upon
792 invocation, the returned tuple is the adjoined results of all
795 Note: In the special case where only a single function is provided
796 ($(D F.length == 1)), adjoin simply aliases to the single passed function
799 template adjoin(F...)
805 template adjoin(F...)
808 auto adjoin(V...)(auto ref V a)
810 import std.typecons : tuple;
811 static if (F.length == 2)
813 return tuple(F[0](a), F[1](a));
815 else static if (F.length == 3)
817 return tuple(F[0](a), F[1](a), F[2](a));
821 import std.format : format;
822 import std.range : iota;
823 return mixin (q{tuple(%(F[%s](a)%|, %))}.format(iota(0, F.length)));
831 import std.functional, std.typecons : Tuple;
832 static bool f1(int a) { return a != 0; }
833 static int f2(int a) { return a / 2; }
834 auto x = adjoin!(f1, f2)(5);
835 assert(is(typeof(x) == Tuple!(bool, int)));
836 assert(x[0] == true && x[1] == 2);
841 import std.typecons : Tuple;
842 static bool F1(int a) { return a != 0; }
843 auto x1 = adjoin!(F1)(5);
844 static int F2(int a) { return a / 2; }
845 auto x2 = adjoin!(F1, F2)(5);
846 assert(is(typeof(x2) == Tuple!(bool, int)));
847 assert(x2[0] && x2[1] == 2);
848 auto x3 = adjoin!(F1, F2, F2)(5);
849 assert(is(typeof(x3) == Tuple!(bool, int, int)));
850 assert(x3[0] && x3[1] == 2 && x3[2] == 2);
852 bool F4(int a) { return a != x1; }
853 alias eff4 = adjoin!(F4);
856 bool delegate(int) @safe store;
857 int fun() { return 42 + store(5); }
860 s.store = (int a) { return eff4(a); };
867 import std.meta : staticMap;
868 import std.typecons : Tuple, tuple;
869 alias funs = staticMap!(unaryFun, "a", "a * 2", "a * 3", "a * a", "-a");
870 alias afun = adjoin!funs;
871 assert(afun(5) == tuple(5, 10, 15, 25, -5));
874 alias IC = immutable(C);
875 IC foo(){return typeof(return).init;}
876 Tuple!(IC, IC, IC, IC) ret1 = adjoin!(foo, foo, foo, foo)();
878 static struct S{int* p;}
879 alias IS = immutable(S);
880 IS bar(){return typeof(return).init;}
881 enum Tuple!(IS, IS, IS, IS) ret2 = adjoin!(bar, bar, bar, bar)();
885 Composes passed-in functions $(D fun[0], fun[1], ...) returning a
886 function $(D f(x)) that in turn returns $(D
887 fun[0](fun[1](...(x)))...). Each function can be a regular
888 functions, a delegate, or a string.
890 See_Also: $(LREF pipe)
892 template compose(fun...)
894 static if (fun.length == 1)
896 alias compose = unaryFun!(fun[0]);
898 else static if (fun.length == 2)
901 alias fun0 = unaryFun!(fun[0]);
902 alias fun1 = unaryFun!(fun[1]);
904 // protein: the core composition operation
905 typeof({ E a; return fun0(fun1(a)); }()) compose(E)(E a)
907 return fun0(fun1(a));
912 // protein: assembling operations
913 alias compose = compose!(fun[0], compose!(fun[1 .. $]));
920 import std.algorithm.comparison : equal;
921 import std.algorithm.iteration : map;
922 import std.array : split;
923 import std.conv : to;
925 // First split a string in whitespace-separated tokens and then
926 // convert each token into an integer
927 assert(compose!(map!(to!(int)), split)("1 2 3").equal([1, 2, 3]));
931 Pipes functions in sequence. Offers the same functionality as $(D
932 compose), but with functions specified in reverse order. This may
933 lead to more readable code in some situation because the order of
934 execution is the same as lexical order.
939 // Read an entire text file, split the resulting string in
940 // whitespace-separated tokens, and then convert each token into an
942 int[] a = pipe!(readText, split, map!(to!(int)))("file.txt");
945 See_Also: $(LREF compose)
947 alias pipe(fun...) = compose!(Reverse!(fun));
951 import std.conv : to;
952 string foo(int a) { return to!(string)(a); }
953 int bar(string a) { return to!(int)(a) + 1; }
954 double baz(int a) { return a + 0.5; }
955 assert(compose!(baz, bar, foo)(1) == 2.5);
956 assert(pipe!(foo, bar, baz)(1) == 2.5);
958 assert(compose!(baz, `to!(int)(a) + 1`, foo)(1) == 2.5);
959 assert(compose!(baz, bar)("1"[]) == 2.5);
961 assert(compose!(baz, bar)("1") == 2.5);
963 assert(compose!(`a + 0.5`, `to!(int)(a) + 1`, foo)(1) == 2.5);
967 * $(LINK2 https://en.wikipedia.org/wiki/Memoization, Memoizes) a function so as
968 * to avoid repeated computation. The memoization structure is a hash table keyed by a
969 * tuple of the function's arguments. There is a speed gain if the
970 * function is repeatedly called with the same arguments and is more
971 * expensive than a hash table lookup. For more information on memoization, refer to $(HTTP docs.google.com/viewer?url=http%3A%2F%2Fhop.perl.plover.com%2Fbook%2Fpdf%2F03CachingAndMemoization.pdf, this book chapter).
975 double transmogrify(int a, string b)
977 ... expensive computation ...
979 alias fastTransmogrify = memoize!transmogrify;
982 auto slow = transmogrify(2, "hello");
983 auto fast = fastTransmogrify(2, "hello");
984 assert(slow == fast);
988 Technically the memoized function should be pure because $(D memoize) assumes it will
989 always return the same result for a given tuple of arguments. However, $(D memoize) does not
990 enforce that because sometimes it
991 is useful to memoize an impure function, too.
993 template memoize(alias fun)
995 import std.traits : ReturnType;
996 // alias Args = Parameters!fun; // Bugzilla 13580
998 ReturnType!fun memoize(Parameters!fun args)
1000 alias Args = Parameters!fun;
1001 import std.typecons : Tuple;
1003 static ReturnType!fun[Tuple!Args] memo;
1004 auto t = Tuple!Args(args);
1005 if (auto p = t in memo)
1007 return memo[t] = fun(args);
1012 template memoize(alias fun, uint maxSize)
1014 import std.traits : ReturnType;
1015 // alias Args = Parameters!fun; // Bugzilla 13580
1016 ReturnType!fun memoize(Parameters!fun args)
1018 import std.traits : hasIndirections;
1019 import std.typecons : tuple;
1020 static struct Value { Parameters!fun args; ReturnType!fun res; }
1021 static Value[] memo;
1022 static size_t[] initialized;
1026 import core.memory : GC;
1028 // Ensure no allocation overflows
1029 static assert(maxSize < size_t.max / Value.sizeof);
1030 static assert(maxSize < size_t.max - (8 * size_t.sizeof - 1));
1032 enum attr = GC.BlkAttr.NO_INTERIOR | (hasIndirections!Value ? 0 : GC.BlkAttr.NO_SCAN);
1033 memo = (cast(Value*) GC.malloc(Value.sizeof * maxSize, attr))[0 .. maxSize];
1034 enum nwords = (maxSize + 8 * size_t.sizeof - 1) / (8 * size_t.sizeof);
1035 initialized = (cast(size_t*) GC.calloc(nwords * size_t.sizeof, attr | GC.BlkAttr.NO_SCAN))[0 .. nwords];
1038 import core.bitop : bt, bts;
1039 import std.conv : emplace;
1042 foreach (ref arg; args)
1043 hash = hashOf(arg, hash);
1045 immutable idx1 = hash % maxSize;
1046 if (!bt(initialized.ptr, idx1))
1048 emplace(&memo[idx1], args, fun(args));
1049 bts(initialized.ptr, idx1); // only set to initialized after setting args and value (bugzilla 14025)
1050 return memo[idx1].res;
1052 else if (memo[idx1].args == args)
1053 return memo[idx1].res;
1055 immutable idx2 = (hash * 16_777_619) % maxSize;
1056 if (!bt(initialized.ptr, idx2))
1058 emplace(&memo[idx2], memo[idx1]);
1059 bts(initialized.ptr, idx2); // only set to initialized after setting args and value (bugzilla 14025)
1061 else if (memo[idx2].args == args)
1062 return memo[idx2].res;
1063 else if (idx1 != idx2)
1064 memo[idx2] = memo[idx1];
1066 memo[idx1] = Value(args, fun(args));
1067 return memo[idx1].res;
1072 * To _memoize a recursive function, simply insert the memoized call in lieu of the plain recursive call.
1073 * For example, to transform the exponential-time Fibonacci implementation into a linear-time computation:
1077 ulong fib(ulong n) @safe
1079 return n < 2 ? n : memoize!fib(n - 2) + memoize!fib(n - 1);
1081 assert(fib(10) == 55);
1085 * To improve the speed of the factorial function,
1089 ulong fact(ulong n) @safe
1091 return n < 2 ? 1 : n * memoize!fact(n - 1);
1093 assert(fact(10) == 3628800);
1097 * This memoizes all values of $(D fact) up to the largest argument. To only cache the final
1098 * result, move $(D memoize) outside the function as shown below.
1102 ulong factImpl(ulong n) @safe
1104 return n < 2 ? 1 : n * factImpl(n - 1);
1106 alias fact = memoize!factImpl;
1107 assert(fact(10) == 3628800);
1111 * When the $(D maxSize) parameter is specified, memoize will used
1112 * a fixed size hash table to limit the number of cached entries.
1114 @system unittest // not @safe due to memoize
1118 // Memoize no more than 8 values
1119 return n < 2 ? 1 : n * memoize!(fact, 8)(n - 1);
1121 assert(fact(8) == 40320);
1122 // using more entries than maxSize will overwrite existing entries
1123 assert(fact(10) == 3628800);
1126 @system unittest // not @safe due to memoize
1128 import core.math : sqrt;
1129 alias msqrt = memoize!(function double(double x) { return sqrt(x); });
1130 auto y = msqrt(2.0);
1131 assert(y == msqrt(2.0));
1133 assert(y == sqrt(4.0));
1135 // alias mrgb2cmyk = memoize!rgb2cmyk;
1136 // auto z = mrgb2cmyk([43, 56, 76]);
1137 // assert(z == mrgb2cmyk([43, 56, 76]));
1139 //alias mfib = memoize!fib;
1141 static ulong fib(ulong n) @safe
1143 alias mfib = memoize!fib;
1144 return n < 2 ? 1 : mfib(n - 2) + mfib(n - 1);
1150 static ulong fact(ulong n) @safe
1152 alias mfact = memoize!fact;
1153 return n < 2 ? 1 : n * mfact(n - 1);
1155 assert(fact(10) == 3628800);
1158 static uint len2(const string s) { // Error
1159 alias mLen2 = memoize!len2;
1163 return 1 + mLen2(s[1 .. $]);
1166 int _func(int x) @safe { return 1; }
1167 alias func = memoize!(_func, 10);
1168 assert(func(int.init) == 1);
1169 assert(func(int.init) == 1);
1172 // 16079: memoize should work with arrays
1176 T median(T)(const T[] nums) {
1177 import std.algorithm.sorting : sort;
1179 auto arr = nums.dup;
1184 return (arr[$ / 2 - 1]
1188 alias fastMedian = memoize!(median!int);
1190 assert(fastMedian([7, 5, 3]) == 5);
1191 assert(fastMedian([7, 5, 3]) == 5);
1193 assert(executed == 1);
1196 // 16079: memoize should work with structs
1200 T pickFirst(T)(T first)
1206 struct Foo { int k; }
1209 alias first = memoize!(pickFirst!Foo);
1210 assert(first(Foo(3)) == A);
1211 assert(first(Foo(3)) == A);
1212 assert(executed == 1);
1215 // 16079: memoize should work with classes
1219 T pickFirst(T)(T first)
1232 override size_t toHash()
1236 override bool opEquals(Object o)
1238 auto b = cast(Bar) o;
1239 return b && k == b.k;
1243 alias firstClass = memoize!(pickFirst!Bar);
1244 assert(firstClass(new Bar(3)).k == 3);
1245 assert(firstClass(new Bar(3)).k == 3);
1246 assert(executed == 1);
1249 private struct DelegateFaker(F)
1251 import std.typecons : FuncInfo, MemberFunctionGenerator;
1254 static F castToF(THIS)(THIS x) @trusted
1260 * What all the stuff below does is this:
1261 *--------------------
1262 * struct DelegateFaker(F) {
1264 * [ref] ReturnType!F doIt(Parameters!F args) [@attributes]
1266 * auto fp = cast(F) &this;
1270 *--------------------
1273 // We will use MemberFunctionGenerator in std.typecons. This is a policy
1274 // configuration for generating the doIt().
1275 template GeneratingPolicy()
1277 // Inform the genereator that we only have type information.
1278 enum WITHOUT_SYMBOL = true;
1280 // Generate the function body of doIt().
1281 template generateFunctionBody(unused...)
1283 enum generateFunctionBody =
1284 // [ref] ReturnType doIt(Parameters args) @attributes
1286 // When this function gets called, the this pointer isn't
1287 // really a this pointer (no instance even really exists), but
1288 // a function pointer that points to the function to be called.
1289 // Cast it to the correct type and call it.
1291 auto fp = castToF(&this);
1296 // Type information used by the generated code.
1297 alias FuncInfo_doIt = FuncInfo!(F);
1299 // Generate the member function doIt().
1300 mixin( MemberFunctionGenerator!(GeneratingPolicy!())
1301 .generateFunction!("FuncInfo_doIt", "doIt", F) );
1305 * Convert a callable to a delegate with the same parameter list and
1306 * return type, avoiding heap allocations and use of auxiliary storage.
1311 * writeln("Hello, world.");
1314 * void runDelegate(void delegate() myDelegate) {
1318 * auto delegateToPass = toDelegate(&doStuff);
1319 * runDelegate(delegateToPass); // Calls doStuff, prints "Hello, world."
1324 * $(LI Does not work with $(D @safe) functions.)
1325 * $(LI Ignores C-style / D-style variadic arguments.)
1328 auto toDelegate(F)(auto ref F fp)
1331 static if (is(F == delegate))
1335 else static if (is(typeof(&F.opCall) == delegate)
1336 || (is(typeof(&F.opCall) V : V*) && is(V == function)))
1338 return toDelegate(&fp.opCall);
1342 alias DelType = typeof(&(new DelegateFaker!(F)).doIt);
1344 static struct DelegateFields {
1347 //pragma(msg, typeof(del));
1356 // fp is stored in the returned delegate's context pointer.
1357 // The returned delegate's function pointer points to
1358 // DelegateFaker.doIt.
1361 df.contextPtr = cast(void*) fp;
1363 DelegateFaker!(F) dummy;
1364 auto dummyDel = &dummy.doIt;
1365 df.funcPtr = dummyDel.funcptr;
1374 static int inc(ref uint num) {
1380 auto incMyNumDel = toDelegate(&inc);
1381 auto returnVal = incMyNumDel(myNum);
1385 @system unittest // not @safe due to toDelegate
1387 static int inc(ref uint num) {
1393 auto incMyNumDel = toDelegate(&inc);
1394 int delegate(ref uint) dg = incMyNumDel;
1395 auto returnVal = incMyNumDel(myNum);
1398 interface I { int opCall(); }
1399 class C: I { int opCall() { inc(myNum); return myNum;} }
1403 auto getvalc = toDelegate(c);
1404 assert(getvalc() == 2);
1406 auto getvali = toDelegate(i);
1407 assert(getvali() == 3);
1409 struct S1 { int opCall() { inc(myNum); return myNum; } }
1410 static assert(!is(typeof(&s1.opCall) == delegate));
1412 auto getvals1 = toDelegate(s1);
1413 assert(getvals1() == 4);
1415 struct S2 { static int opCall() { return 123456; } }
1416 static assert(!is(typeof(&S2.opCall) == delegate));
1418 auto getvals2 =&S2.opCall;
1419 assert(getvals2() == 123456);
1421 /* test for attributes */
1423 static int refvar = 0xDeadFace;
1425 static ref int func_ref() { return refvar; }
1426 static int func_pure() pure { return 1; }
1427 static int func_nothrow() nothrow { return 2; }
1428 static int func_property() @property { return 3; }
1429 static int func_safe() @safe { return 4; }
1430 static int func_trusted() @trusted { return 5; }
1431 static int func_system() @system { return 6; }
1432 static int func_pure_nothrow() pure nothrow { return 7; }
1433 static int func_pure_nothrow_safe() pure nothrow @safe { return 8; }
1435 auto dg_ref = toDelegate(&func_ref);
1436 int delegate() pure dg_pure = toDelegate(&func_pure);
1437 int delegate() nothrow dg_nothrow = toDelegate(&func_nothrow);
1438 int delegate() @property dg_property = toDelegate(&func_property);
1439 int delegate() @safe dg_safe = toDelegate(&func_safe);
1440 int delegate() @trusted dg_trusted = toDelegate(&func_trusted);
1441 int delegate() @system dg_system = toDelegate(&func_system);
1442 int delegate() pure nothrow dg_pure_nothrow = toDelegate(&func_pure_nothrow);
1443 int delegate() @safe pure nothrow dg_pure_nothrow_safe = toDelegate(&func_pure_nothrow_safe);
1445 //static assert(is(typeof(dg_ref) == ref int delegate())); // [BUG@DMD]
1447 assert(dg_ref() == refvar);
1448 assert(dg_pure() == 1);
1449 assert(dg_nothrow() == 2);
1450 assert(dg_property() == 3);
1451 assert(dg_safe() == 4);
1452 assert(dg_trusted() == 5);
1453 assert(dg_system() == 6);
1454 assert(dg_pure_nothrow() == 7);
1455 assert(dg_pure_nothrow_safe() == 8);
1457 /* test for linkage */
1461 extern(C) static void xtrnC() {}
1462 extern(D) static void xtrnD() {}
1464 auto dg_xtrnC = toDelegate(&S.xtrnC);
1465 auto dg_xtrnD = toDelegate(&S.xtrnD);
1466 static assert(! is(typeof(dg_xtrnC) == typeof(dg_xtrnD)));
1471 Forwards function arguments with saving ref-ness.
1473 template forward(args...)
1475 static if (args.length)
1477 import std.algorithm.mutation : move;
1479 alias arg = args[0];
1480 static if (__traits(isRef, arg))
1483 @property fwd()(){ return move(arg); }
1484 alias forward = AliasSeq!(fwd, forward!(args[1..$]));
1487 alias forward = AliasSeq!();
1495 static int foo(int n) { return 1; }
1496 static int foo(ref int n) { return 2; }
1498 int bar()(auto ref int x) { return C.foo(forward!x); }
1500 assert(bar(1) == 1);
1502 assert(bar(i) == 2);
1508 void foo(int n, ref string s) { s = null; foreach (i; 0 .. n) s ~= "Hello"; }
1510 // forwards all arguments which are bound to parameter tuple
1511 void bar(Args...)(auto ref Args args) { return foo(forward!args); }
1513 // forwards all arguments with swapping order
1514 void baz(Args...)(auto ref Args args) { return foo(forward!args[$/2..$], forward!args[0..$/2]); }
1518 assert(s == "Hello");
1520 assert(s == "HelloHello");
1525 auto foo(TL...)(auto ref TL args)
1528 foreach (i, _; args)
1530 //pragma(msg, "[",i,"] ", __traits(isRef, args[i]) ? "L" : "R");
1531 result ~= __traits(isRef, args[i]) ? "L" : "R";
1536 string bar(TL...)(auto ref TL args)
1538 return foo(forward!args);
1540 string baz(TL...)(auto ref TL args)
1543 return foo(forward!args[3], forward!args[2], 1, forward!args[1], forward!args[0], x);
1547 S makeS(){ return S(); }
1550 assert(bar(S(), makeS(), n, s) == "RRLL");
1551 assert(baz(S(), makeS(), n, s) == "LLRRRL");
1556 ref int foo(return ref int a) { return a; }
1557 ref int bar(Args)(auto ref Args args)
1559 return foo(forward!args);
1561 static assert(!__traits(compiles, { auto x1 = bar(3); })); // case of NG
1563 auto x2 = bar(value); // case of OK