1 // Written in the D programming language.
2 
3 /**
4 Functions that manipulate other functions.
5 
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).
9 
10 $(SCRIPT inhibitQuickIndex = 1;)
11 $(DIVC quickindex,
12 $(BOOKTABLE ,
13 $(TR $(TH Function Name) $(TH Description)
14 )
15     $(TR $(TD $(LREF adjoin))
16         $(TD Joins a couple of functions into one that executes the original
17         functions independently and returns a tuple with all the results.
18     ))
19     $(TR $(TD $(LREF compose), $(LREF pipe))
20         $(TD Join a couple of functions into one that executes the original
21         functions one after the other, using one function's result for the next
22         function's argument.
23     ))
24     $(TR $(TD $(LREF lessThan), $(LREF greaterThan), $(LREF equalTo))
25         $(TD Ready-made predicate functions to compare two values.
26     ))
27     $(TR $(TD $(LREF memoize))
28         $(TD Creates a function that caches its result for fast re-evaluation.
29     ))
30     $(TR $(TD $(LREF not))
31         $(TD Creates a function that negates another.
32     ))
33     $(TR $(TD $(LREF partial))
34         $(TD Creates a function that binds the first argument of a given function
35         to a given value.
36     ))
37     $(TR $(TD $(LREF curry))
38         $(TD Converts a multi-argument function into a series of single-argument
39         functions.  f(x, y) == curry(f)(x)(y)
40     ))
41     $(TR $(TD $(LREF reverseArgs))
42         $(TD Predicate that reverses the order of its arguments.
43     ))
44     $(TR $(TD $(LREF toDelegate))
45         $(TD Converts a callable to a delegate.
46     ))
47     $(TR $(TD $(LREF unaryFun), $(LREF binaryFun))
48         $(TD Create a unary or binary function from a string. Most often
49         used when defining algorithms on ranges.
50     ))
51     $(TR $(TD $(LREF bind))
52         $(TD Passes the fields of a struct as arguments to a function.
53     ))
54 ))
55 
56 Copyright: Copyright Andrei Alexandrescu 2008 - 2009.
57 License:   $(HTTP boost.org/LICENSE_1_0.txt, Boost License 1.0).
58 Authors:   $(HTTP erdani.org, Andrei Alexandrescu)
59 Source:    $(PHOBOSSRC std/functional.d)
60 */
61 /*
62          Copyright Andrei Alexandrescu 2008 - 2009.
63 Distributed under the Boost Software License, Version 1.0.
64    (See accompanying file LICENSE_1_0.txt or copy at
65          http://www.boost.org/LICENSE_1_0.txt)
66 */
67 module std.functional;
68 
69 import std.meta : AliasSeq, Reverse;
70 import std.traits : isCallable, Parameters;
71 import std.conv : toCtString;
72 
73 import std.internal.attributes : betterC;
74 
75 public import core.lifetime : forward;
76 
77 private template needOpCallAlias(alias fun)
78 {
79     /* Determine whether or not unaryFun and binaryFun need to alias to fun or
80      * fun.opCall. Basically, fun is a function object if fun(...) compiles. We
81      * want is(unaryFun!fun) (resp., is(binaryFun!fun)) to be true if fun is
82      * any function object. There are 4 possible cases:
83      *
84      *  1) fun is the type of a function object with static opCall;
85      *  2) fun is an instance of a function object with static opCall;
86      *  3) fun is the type of a function object with non-static opCall;
87      *  4) fun is an instance of a function object with non-static opCall.
88      *
89      * In case (1), is(unaryFun!fun) should compile, but does not if unaryFun
90      * aliases itself to fun, because typeof(fun) is an error when fun itself
91      * is a type. So it must be aliased to fun.opCall instead. All other cases
92      * should be aliased to fun directly.
93      */
94     static if (is(typeof(fun.opCall) == function))
95     {
96         enum needOpCallAlias = !is(typeof(fun)) && __traits(compiles, () {
97             return fun(Parameters!fun.init);
98         });
99     }
100     else
101         enum needOpCallAlias = false;
102 }
103 
104 /**
105 Transforms a `string` representing an expression into a unary
106 function. The `string` must either use symbol name `a` as
107 the parameter or provide the symbol via the `parmName` argument.
108 
109 Params:
110     fun = a `string` or a callable
111     parmName = the name of the parameter if `fun` is a string. Defaults
112     to `"a"`.
113 Returns:
114     If `fun` is a `string`, a new single parameter function
115 
116     If `fun` is not a `string`, an alias to `fun`.
117 */
118 template unaryFun(alias fun, string parmName = "a")
119 {
120     static if (is(typeof(fun) : string))
121     {
122         static if (!fun._ctfeMatchUnary(parmName))
123         {
124             import std.algorithm, std.conv, std.exception, std.math, std.range, std.string;
125             import std.meta, std.traits, std.typecons;
126         }
127         auto unaryFun(ElementType)(auto ref ElementType __a)
128         {
129             mixin("alias " ~ parmName ~ " = __a ;");
130             return mixin(fun);
131         }
132     }
133     else static if (needOpCallAlias!fun)
134     {
135         // https://issues.dlang.org/show_bug.cgi?id=9906
136         alias unaryFun = fun.opCall;
137     }
138     else
139     {
140         alias unaryFun = fun;
141     }
142 }
143 
144 ///
145 @safe unittest
146 {
147     // Strings are compiled into functions:
148     alias isEven = unaryFun!("(a & 1) == 0");
149     assert(isEven(2) && !isEven(1));
150 }
151 
152 @safe unittest
153 {
154     static int f1(int a) { return a + 1; }
155     static assert(is(typeof(unaryFun!(f1)(1)) == int));
156     assert(unaryFun!(f1)(41) == 42);
157     int f2(int a) { return a + 1; }
158     static assert(is(typeof(unaryFun!(f2)(1)) == int));
159     assert(unaryFun!(f2)(41) == 42);
160     assert(unaryFun!("a + 1")(41) == 42);
161     //assert(unaryFun!("return a + 1;")(41) == 42);
162 
163     int num = 41;
164     assert(unaryFun!"a + 1"(num) == 42);
165 
166     // https://issues.dlang.org/show_bug.cgi?id=9906
167     struct Seen
168     {
169         static bool opCall(int n) { return true; }
170     }
171     static assert(needOpCallAlias!Seen);
172     static assert(is(typeof(unaryFun!Seen(1))));
173     assert(unaryFun!Seen(1));
174 
175     Seen s;
176     static assert(!needOpCallAlias!s);
177     static assert(is(typeof(unaryFun!s(1))));
178     assert(unaryFun!s(1));
179 
180     struct FuncObj
181     {
182         bool opCall(int n) { return true; }
183     }
184     FuncObj fo;
185     static assert(!needOpCallAlias!fo);
186     static assert(is(typeof(unaryFun!fo)));
187     assert(unaryFun!fo(1));
188 
189     // Function object with non-static opCall can only be called with an
190     // instance, not with merely the type.
191     static assert(!is(typeof(unaryFun!FuncObj)));
192 }
193 
194 /**
195 Transforms a `string` representing an expression into a binary function. The
196 `string` must either use symbol names `a` and `b` as the parameters or
197 provide the symbols via the `parm1Name` and `parm2Name` arguments.
198 
199 Params:
200     fun = a `string` or a callable
201     parm1Name = the name of the first parameter if `fun` is a string.
202     Defaults to `"a"`.
203     parm2Name = the name of the second parameter if `fun` is a string.
204     Defaults to `"b"`.
205 Returns:
206     If `fun` is not a string, `binaryFun` aliases itself away to
207     `fun`.
208 */
209 template binaryFun(alias fun, string parm1Name = "a",
210         string parm2Name = "b")
211 {
212     static if (is(typeof(fun) : string))
213     {
214         static if (!fun._ctfeMatchBinary(parm1Name, parm2Name))
215         {
216             import std.algorithm, std.conv, std.exception, std.math, std.range, std.string;
217             import std.meta, std.traits, std.typecons;
218         }
219         auto binaryFun(ElementType1, ElementType2)
220             (auto ref ElementType1 __a, auto ref ElementType2 __b)
221         {
222             mixin("alias "~parm1Name~" = __a ;");
223             mixin("alias "~parm2Name~" = __b ;");
224             return mixin(fun);
225         }
226     }
227     else static if (needOpCallAlias!fun)
228     {
229         // https://issues.dlang.org/show_bug.cgi?id=9906
230         alias binaryFun = fun.opCall;
231     }
232     else
233     {
234         alias binaryFun = fun;
235     }
236 }
237 
238 ///
239 @safe unittest
240 {
241     alias less = binaryFun!("a < b");
242     assert(less(1, 2) && !less(2, 1));
243     alias greater = binaryFun!("a > b");
244     assert(!greater("1", "2") && greater("2", "1"));
245 }
246 
247 @safe unittest
248 {
249     static int f1(int a, string b) { return a + 1; }
250     static assert(is(typeof(binaryFun!(f1)(1, "2")) == int));
251     assert(binaryFun!(f1)(41, "a") == 42);
252     string f2(int a, string b) { return b ~ "2"; }
253     static assert(is(typeof(binaryFun!(f2)(1, "1")) == string));
254     assert(binaryFun!(f2)(1, "4") == "42");
255     assert(binaryFun!("a + b")(41, 1) == 42);
256     //@@BUG
257     //assert(binaryFun!("return a + b;")(41, 1) == 42);
258 
259     // https://issues.dlang.org/show_bug.cgi?id=9906
260     struct Seen
261     {
262         static bool opCall(int x, int y) { return true; }
263     }
264     static assert(is(typeof(binaryFun!Seen)));
265     assert(binaryFun!Seen(1,1));
266 
267     struct FuncObj
268     {
269         bool opCall(int x, int y) { return true; }
270     }
271     FuncObj fo;
272     static assert(!needOpCallAlias!fo);
273     static assert(is(typeof(binaryFun!fo)));
274     assert(unaryFun!fo(1,1));
275 
276     // Function object with non-static opCall can only be called with an
277     // instance, not with merely the type.
278     static assert(!is(typeof(binaryFun!FuncObj)));
279 }
280 
281 // skip all ASCII chars except a .. z, A .. Z, 0 .. 9, '_' and '.'.
282 private uint _ctfeSkipOp(ref string op)
283 {
284     if (!__ctfe) assert(false);
285     import std.ascii : isASCII, isAlphaNum;
286     immutable oldLength = op.length;
287     while (op.length)
288     {
289         immutable front = op[0];
290         if (front.isASCII() && !(front.isAlphaNum() || front == '_' || front == '.'))
291             op = op[1..$];
292         else
293             break;
294     }
295     return oldLength != op.length;
296 }
297 
298 // skip all digits
299 private uint _ctfeSkipInteger(ref string op)
300 {
301     if (!__ctfe) assert(false);
302     import std.ascii : isDigit;
303     immutable oldLength = op.length;
304     while (op.length)
305     {
306         immutable front = op[0];
307         if (front.isDigit())
308             op = op[1..$];
309         else
310             break;
311     }
312     return oldLength != op.length;
313 }
314 
315 // skip name
316 private uint _ctfeSkipName(ref string op, string name)
317 {
318     if (!__ctfe) assert(false);
319     if (op.length >= name.length && op[0 .. name.length] == name)
320     {
321         op = op[name.length..$];
322         return 1;
323     }
324     return 0;
325 }
326 
327 // returns 1 if `fun` is trivial unary function
328 private uint _ctfeMatchUnary(string fun, string name)
329 {
330     if (!__ctfe) assert(false);
331     fun._ctfeSkipOp();
332     for (;;)
333     {
334         immutable h = fun._ctfeSkipName(name) + fun._ctfeSkipInteger();
335         if (h == 0)
336         {
337             fun._ctfeSkipOp();
338             break;
339         }
340         else if (h == 1)
341         {
342             if (!fun._ctfeSkipOp())
343                 break;
344         }
345         else
346             return 0;
347     }
348     return fun.length == 0;
349 }
350 
351 @safe unittest
352 {
353     static assert(!_ctfeMatchUnary("sqrt(ё)", "ё"));
354     static assert(!_ctfeMatchUnary("ё.sqrt", "ё"));
355     static assert(!_ctfeMatchUnary(".ё+ё", "ё"));
356     static assert(!_ctfeMatchUnary("_ё+ё", "ё"));
357     static assert(!_ctfeMatchUnary("ёё", "ё"));
358     static assert(_ctfeMatchUnary("a+a", "a"));
359     static assert(_ctfeMatchUnary("a + 10", "a"));
360     static assert(_ctfeMatchUnary("4 == a", "a"));
361     static assert(_ctfeMatchUnary("2 == a", "a"));
362     static assert(_ctfeMatchUnary("1 != a", "a"));
363     static assert(_ctfeMatchUnary("a != 4", "a"));
364     static assert(_ctfeMatchUnary("a< 1", "a"));
365     static assert(_ctfeMatchUnary("434 < a", "a"));
366     static assert(_ctfeMatchUnary("132 > a", "a"));
367     static assert(_ctfeMatchUnary("123 >a", "a"));
368     static assert(_ctfeMatchUnary("a>82", "a"));
369     static assert(_ctfeMatchUnary("ё>82", "ё"));
370     static assert(_ctfeMatchUnary("ё[ё(ё)]", "ё"));
371     static assert(_ctfeMatchUnary("ё[21]", "ё"));
372 }
373 
374 // returns 1 if `fun` is trivial binary function
375 private uint _ctfeMatchBinary(string fun, string name1, string name2)
376 {
377     if (!__ctfe) assert(false);
378     fun._ctfeSkipOp();
379     for (;;)
380     {
381         immutable h = fun._ctfeSkipName(name1) + fun._ctfeSkipName(name2) + fun._ctfeSkipInteger();
382         if (h == 0)
383         {
384             fun._ctfeSkipOp();
385             break;
386         }
387         else if (h == 1)
388         {
389             if (!fun._ctfeSkipOp())
390                 break;
391         }
392         else
393             return 0;
394     }
395     return fun.length == 0;
396 }
397 
398 @safe unittest
399 {
400 
401     static assert(!_ctfeMatchBinary("sqrt(ё)", "ё", "b"));
402     static assert(!_ctfeMatchBinary("ё.sqrt", "ё", "b"));
403     static assert(!_ctfeMatchBinary(".ё+ё", "ё", "b"));
404     static assert(!_ctfeMatchBinary("_ё+ё", "ё", "b"));
405     static assert(!_ctfeMatchBinary("ёё", "ё", "b"));
406     static assert(_ctfeMatchBinary("a+a", "a", "b"));
407     static assert(_ctfeMatchBinary("a + 10", "a", "b"));
408     static assert(_ctfeMatchBinary("4 == a", "a", "b"));
409     static assert(_ctfeMatchBinary("2 == a", "a", "b"));
410     static assert(_ctfeMatchBinary("1 != a", "a", "b"));
411     static assert(_ctfeMatchBinary("a != 4", "a", "b"));
412     static assert(_ctfeMatchBinary("a< 1", "a", "b"));
413     static assert(_ctfeMatchBinary("434 < a", "a", "b"));
414     static assert(_ctfeMatchBinary("132 > a", "a", "b"));
415     static assert(_ctfeMatchBinary("123 >a", "a", "b"));
416     static assert(_ctfeMatchBinary("a>82", "a", "b"));
417     static assert(_ctfeMatchBinary("ё>82", "ё", "q"));
418     static assert(_ctfeMatchBinary("ё[ё(10)]", "ё", "q"));
419     static assert(_ctfeMatchBinary("ё[21]", "ё", "q"));
420 
421     static assert(!_ctfeMatchBinary("sqrt(ё)+b", "b", "ё"));
422     static assert(!_ctfeMatchBinary("ё.sqrt-b", "b", "ё"));
423     static assert(!_ctfeMatchBinary(".ё+b", "b", "ё"));
424     static assert(!_ctfeMatchBinary("_b+ё", "b", "ё"));
425     static assert(!_ctfeMatchBinary("ba", "b", "a"));
426     static assert(_ctfeMatchBinary("a+b", "b", "a"));
427     static assert(_ctfeMatchBinary("a + b", "b", "a"));
428     static assert(_ctfeMatchBinary("b == a", "b", "a"));
429     static assert(_ctfeMatchBinary("b == a", "b", "a"));
430     static assert(_ctfeMatchBinary("b != a", "b", "a"));
431     static assert(_ctfeMatchBinary("a != b", "b", "a"));
432     static assert(_ctfeMatchBinary("a< b", "b", "a"));
433     static assert(_ctfeMatchBinary("b < a", "b", "a"));
434     static assert(_ctfeMatchBinary("b > a", "b", "a"));
435     static assert(_ctfeMatchBinary("b >a", "b", "a"));
436     static assert(_ctfeMatchBinary("a>b", "b", "a"));
437     static assert(_ctfeMatchBinary("ё>b", "b", "ё"));
438     static assert(_ctfeMatchBinary("b[ё(-1)]", "b", "ё"));
439     static assert(_ctfeMatchBinary("ё[-21]", "b", "ё"));
440 }
441 
442 //undocumented
443 template safeOp(string S)
444 if (S=="<"||S==">"||S=="<="||S==">="||S=="=="||S=="!=")
445 {
446     import std.traits : isIntegral;
447     private bool unsafeOp(ElementType1, ElementType2)(ElementType1 a, ElementType2 b) pure
448         if (isIntegral!ElementType1 && isIntegral!ElementType2)
449     {
450         import std.traits : CommonType;
451         alias T = CommonType!(ElementType1, ElementType2);
452         return mixin("cast(T)a "~S~" cast(T) b");
453     }
454 
455     bool safeOp(T0, T1)(auto ref T0 a, auto ref T1 b)
456     {
457         import std.traits : mostNegative;
458         static if (isIntegral!T0 && isIntegral!T1 &&
459                    (mostNegative!T0 < 0) != (mostNegative!T1 < 0))
460         {
461             static if (S == "<=" || S == "<")
462             {
463                 static if (mostNegative!T0 < 0)
464                     immutable result = a < 0 || unsafeOp(a, b);
465                 else
466                     immutable result = b >= 0 && unsafeOp(a, b);
467             }
468             else
469             {
470                 static if (mostNegative!T0 < 0)
471                     immutable result = a >= 0 && unsafeOp(a, b);
472                 else
473                     immutable result = b < 0 || unsafeOp(a, b);
474             }
475         }
476         else
477         {
478             static assert(is(typeof(mixin("a "~S~" b"))),
479                 "Invalid arguments: Cannot compare types " ~ T0.stringof ~ " and " ~ T1.stringof ~ ".");
480 
481             immutable result = mixin("a "~S~" b");
482         }
483         return result;
484     }
485 }
486 
487 @safe unittest //check user defined types
488 {
489     import std.algorithm.comparison : equal;
490     struct Foo
491     {
492         int a;
493         auto opEquals(Foo foo)
494         {
495             return a == foo.a;
496         }
497     }
498     assert(safeOp!"!="(Foo(1), Foo(2)));
499 }
500 
501 /**
502    Predicate that returns $(D_PARAM a < b).
503    Correctly compares signed and unsigned integers, ie. -1 < 2U.
504 */
505 alias lessThan = safeOp!"<";
506 
507 ///
508 pure @safe @nogc nothrow unittest
509 {
510     assert(lessThan(2, 3));
511     assert(lessThan(2U, 3U));
512     assert(lessThan(2, 3.0));
513     assert(lessThan(-2, 3U));
514     assert(lessThan(2, 3U));
515     assert(!lessThan(3U, -2));
516     assert(!lessThan(3U, 2));
517     assert(!lessThan(0, 0));
518     assert(!lessThan(0U, 0));
519     assert(!lessThan(0, 0U));
520 }
521 
522 /**
523    Predicate that returns $(D_PARAM a > b).
524    Correctly compares signed and unsigned integers, ie. 2U > -1.
525 */
526 alias greaterThan = safeOp!">";
527 
528 ///
529 @safe unittest
530 {
531     assert(!greaterThan(2, 3));
532     assert(!greaterThan(2U, 3U));
533     assert(!greaterThan(2, 3.0));
534     assert(!greaterThan(-2, 3U));
535     assert(!greaterThan(2, 3U));
536     assert(greaterThan(3U, -2));
537     assert(greaterThan(3U, 2));
538     assert(!greaterThan(0, 0));
539     assert(!greaterThan(0U, 0));
540     assert(!greaterThan(0, 0U));
541 }
542 
543 /**
544    Predicate that returns $(D_PARAM a == b).
545    Correctly compares signed and unsigned integers, ie. !(-1 == ~0U).
546 */
547 alias equalTo = safeOp!"==";
548 
549 ///
550 @safe unittest
551 {
552     assert(equalTo(0U, 0));
553     assert(equalTo(0, 0U));
554     assert(!equalTo(-1, ~0U));
555 }
556 /**
557 N-ary predicate that reverses the order of arguments, e.g., given
558 $(D pred(a, b, c)), returns $(D pred(c, b, a)).
559 
560 Params:
561     pred = A callable
562 Returns:
563     A function which calls `pred` after reversing the given parameters
564 */
565 template reverseArgs(alias pred)
566 {
567     auto reverseArgs(Args...)(auto ref Args args)
568     if (is(typeof(pred(Reverse!args))))
569     {
570         return pred(Reverse!args);
571     }
572 }
573 
574 ///
575 @safe unittest
576 {
577     alias gt = reverseArgs!(binaryFun!("a < b"));
578     assert(gt(2, 1) && !gt(1, 1));
579 }
580 
581 ///
582 @safe unittest
583 {
584     int x = 42;
585     bool xyz(int a, int b) { return a * x < b / x; }
586     auto foo = &xyz;
587     foo(4, 5);
588     alias zyx = reverseArgs!(foo);
589     assert(zyx(5, 4) == foo(4, 5));
590 }
591 
592 ///
593 @safe unittest
594 {
595     alias gt = reverseArgs!(binaryFun!("a < b"));
596     assert(gt(2, 1) && !gt(1, 1));
597     int x = 42;
598     bool xyz(int a, int b) { return a * x < b / x; }
599     auto foo = &xyz;
600     foo(4, 5);
601     alias zyx = reverseArgs!(foo);
602     assert(zyx(5, 4) == foo(4, 5));
603 }
604 
605 ///
606 @safe unittest
607 {
608     int abc(int a, int b, int c) { return a * b + c; }
609     alias cba = reverseArgs!abc;
610     assert(abc(91, 17, 32) == cba(32, 17, 91));
611 }
612 
613 ///
614 @safe unittest
615 {
616     int a(int a) { return a * 2; }
617     alias _a = reverseArgs!a;
618     assert(a(2) == _a(2));
619 }
620 
621 ///
622 @safe unittest
623 {
624     int b() { return 4; }
625     alias _b = reverseArgs!b;
626     assert(b() == _b());
627 }
628 
629 /**
630 Negates predicate `pred`.
631 
632 Params:
633     pred = A string or a callable
634 Returns:
635     A function which calls `pred` and returns the logical negation of its
636     return value.
637  */
638 template not(alias pred)
639 {
640     auto not(T...)(auto ref T args)
641     {
642         static if (is(typeof(!pred(args))))
643             return !pred(args);
644         else static if (T.length == 1)
645             return !unaryFun!pred(args);
646         else static if (T.length == 2)
647             return !binaryFun!pred(args);
648         else
649             static assert(0);
650     }
651 }
652 
653 ///
654 @safe unittest
655 {
656     import std.algorithm.searching : find;
657     import std.uni : isWhite;
658     string a = "   Hello, world!";
659     assert(find!(not!isWhite)(a) == "Hello, world!");
660 }
661 
662 @safe unittest
663 {
664     assert(not!"a != 5"(5));
665     assert(not!"a != b"(5, 5));
666 
667     assert(not!(() => false)());
668     assert(not!(a => a != 5)(5));
669     assert(not!((a, b) => a != b)(5, 5));
670     assert(not!((a, b, c) => a * b * c != 125 )(5, 5, 5));
671 }
672 
673 /**
674 $(LINK2 http://en.wikipedia.org/wiki/Partial_application, Partially
675 applies) $(D_PARAM fun) by tying its first argument to $(D_PARAM arg).
676 
677 Params:
678     fun = A callable
679     arg = The first argument to apply to `fun`
680 Returns:
681     A new function which calls `fun` with `arg` plus the passed parameters.
682  */
683 template partial(alias fun, alias arg)
684 {
685     import std.traits : isCallable;
686     // Check whether fun is a user defined type which implements opCall or a template.
687     // As opCall itself can be templated, std.traits.isCallable does not work here.
688     enum isSomeFunctor = (is(typeof(fun) == struct) || is(typeof(fun) == class)) && __traits(hasMember, fun, "opCall");
689     static if (isSomeFunctor || __traits(isTemplate, fun))
690     {
691         auto partial(Ts...)(Ts args2)
692         {
693             static if (is(typeof(fun(arg, args2))))
694             {
695                 return fun(arg, args2);
696             }
697             else
698             {
699                 static string errormsg()
700                 {
701                     string msg = "Cannot call '" ~ fun.stringof ~ "' with arguments " ~
702                         "(" ~ arg.stringof;
703                     foreach (T; Ts)
704                         msg ~= ", " ~ T.stringof;
705                     msg ~= ").";
706                     return msg;
707                 }
708                 static assert(0, errormsg());
709             }
710         }
711     }
712     else static if (!isCallable!fun)
713     {
714         static assert(false, "Cannot apply partial to a non-callable '" ~ fun.stringof ~ "'.");
715     }
716     else
717     {
718         import std.meta : Filter;
719 
720         static if (__traits(compiles, __traits(getOverloads,
721             __traits(parent, fun), __traits(identifier, fun))))
722             alias overloads = __traits(getOverloads, __traits(parent, fun),
723                 __traits(identifier, fun));
724         else
725             alias overloads = AliasSeq!(fun);
726 
727         enum isCallableWithArg(alias fun) = Parameters!fun.length > 0 &&
728             is(typeof(arg) : Parameters!fun[0]);
729         alias candidates = Filter!(isCallableWithArg, overloads);
730 
731         static if (overloads.length == 1 && Parameters!fun.length == 0)
732         {
733             static assert(0, "Cannot partially apply '" ~ fun.stringof ~ "'." ~
734                 "'" ~ fun.stringof ~ "' has 0 arguments.");
735         }
736         else static if (candidates.length == 0)
737         {
738             import std.meta : NoDuplicates, staticMap;
739 
740             enum hasParameters(alias fun) = Parameters!fun.length > 0;
741             alias firstParameter(alias fun) = Parameters!fun[0];
742             alias firstParameters = NoDuplicates!(
743                 staticMap!(firstParameter, Filter!(hasParameters, overloads)));
744 
745             string errorMsg()
746             {
747                 string msg = "Argument mismatch for '" ~ fun.stringof ~
748                     "': expected " ~ firstParameters[0].stringof;
749                 static foreach (firstParam; firstParameters[1 .. $])
750                     msg ~= " or " ~ firstParam.stringof;
751                 msg ~= ", but got " ~ typeof(arg).stringof ~ ".";
752 
753                 return msg;
754             }
755             static assert(0, errorMsg());
756         }
757         else
758         {
759             import std.traits : ReturnType;
760             static foreach (candidate; candidates)
761                 ReturnType!candidate partial(Parameters!candidate[1..$] args2)
762                 {
763                     return candidate(arg, args2);
764                 }
765         }
766     }
767 }
768 
769 ///
770 @safe unittest
771 {
772     int fun(int a, int b) { return a + b; }
773     alias fun5 = partial!(fun, 5);
774     assert(fun5(6) == 11);
775     // Note that in most cases you'd use an alias instead of a value
776     // assignment. Using an alias allows you to partially evaluate template
777     // functions without committing to a particular type of the function.
778 }
779 
780 // https://issues.dlang.org/show_bug.cgi?id=21457
781 ///
782 @safe unittest
783 {
784     // Overloads are resolved when the partially applied function is called
785     // with the remaining arguments.
786     struct S
787     {
788         static char fun(int i, string s) { return s[i]; }
789         static int fun(int a, int b) { return a * b; }
790     }
791     alias fun3 = partial!(S.fun, 3);
792     assert(fun3("hello") == 'l');
793     assert(fun3(10) == 30);
794 }
795 
796 // tests for partially evaluating callables
797 @safe unittest
798 {
799     static int f1(int a, int b) { return a + b; }
800     assert(partial!(f1, 5)(6) == 11);
801 
802     int f2(int a, int b) { return a + b; }
803     int x = 5;
804     assert(partial!(f2, x)(6) == 11);
805     x = 7;
806     assert(partial!(f2, x)(6) == 13);
807     static assert(partial!(f2, 5)(6) == 11);
808 
809     auto dg = &f2;
810     auto f3 = &partial!(dg, x);
811     assert(f3(6) == 13);
812 
813     static int funOneArg(int a) { return a; }
814     assert(partial!(funOneArg, 1)() == 1);
815 
816     static int funThreeArgs(int a, int b, int c) { return a + b + c; }
817     alias funThreeArgs1 = partial!(funThreeArgs, 1);
818     assert(funThreeArgs1(2, 3) == 6);
819     static assert(!is(typeof(funThreeArgs1(2))));
820 
821     enum xe = 5;
822     alias fe = partial!(f2, xe);
823     static assert(fe(6) == 11);
824 }
825 
826 // tests for partially evaluating templated/overloaded callables
827 @safe unittest
828 {
829     static auto add(A, B)(A x, B y)
830     {
831         return x + y;
832     }
833 
834     alias add5 = partial!(add, 5);
835     assert(add5(6) == 11);
836     static assert(!is(typeof(add5())));
837     static assert(!is(typeof(add5(6, 7))));
838 
839     // taking address of templated partial evaluation needs explicit type
840     auto dg = &add5!(int);
841     assert(dg(6) == 11);
842 
843     int x = 5;
844     alias addX = partial!(add, x);
845     assert(addX(6) == 11);
846 
847     static struct Callable
848     {
849         static string opCall(string a, string b) { return a ~ b; }
850         int opCall(int a, int b) { return a * b; }
851         double opCall(double a, double b) { return a + b; }
852     }
853     Callable callable;
854     assert(partial!(Callable, "5")("6") == "56");
855     assert(partial!(callable, 5)(6) == 30);
856     assert(partial!(callable, 7.0)(3.0) == 7.0 + 3.0);
857 
858     static struct TCallable
859     {
860         auto opCall(A, B)(A a, B b)
861         {
862             return a + b;
863         }
864     }
865     TCallable tcallable;
866     assert(partial!(tcallable, 5)(6) == 11);
867     static assert(!is(typeof(partial!(tcallable, "5")(6))));
868 
869     static struct NonCallable{}
870     static assert(!__traits(compiles, partial!(NonCallable, 5)), "Partial should not work on non-callable structs.");
871     static assert(!__traits(compiles, partial!(NonCallable.init, 5)),
872         "Partial should not work on instances of non-callable structs.");
873 
874     static A funOneArg(A)(A a) { return a; }
875     alias funOneArg1 = partial!(funOneArg, 1);
876     assert(funOneArg1() == 1);
877 
878     static auto funThreeArgs(A, B, C)(A a, B b, C c) { return a + b + c; }
879     alias funThreeArgs1 = partial!(funThreeArgs, 1);
880     assert(funThreeArgs1(2, 3) == 6);
881     static assert(!is(typeof(funThreeArgs1(1))));
882 
883     auto dg2 = &funOneArg1!();
884     assert(dg2() == 1);
885 }
886 
887 // Fix https://issues.dlang.org/show_bug.cgi?id=15732
888 @safe unittest
889 {
890     // Test whether it works with functions.
891     auto partialFunction(){
892         auto fullFunction = (float a, float b, float c) => a + b / c;
893         alias apply1 = partial!(fullFunction, 1);
894         return &apply1;
895     }
896     auto result = partialFunction()(2, 4);
897     assert(result == 1.5f);
898 
899     // And with delegates.
900     auto partialDelegate(float c){
901         auto fullDelegate = (float a, float b) => a + b / c;
902         alias apply1 = partial!(fullDelegate, 1);
903         return &apply1;
904     }
905     auto result2 = partialDelegate(4)(2);
906     assert(result2 == 1.5f);
907 }
908 
909 /**
910 Takes a function of (potentially) many arguments, and returns a function taking
911 one argument and returns a callable taking the rest.  f(x, y) == curry(f)(x)(y)
912 
913 Params:
914     F = a function taking at least one argument
915     t = a callable object whose opCall takes at least 1 object
916 Returns:
917     A single parameter callable object
918 */
919 template curry(alias F)
920 if (isCallable!F && Parameters!F.length)
921 {
922     //inspired from the implementation from Artur Skawina here:
923     //https://forum.dlang.org/post/mailman.1626.1340110492.24740.digitalmars-d@puremagic.com
924     //This implementation stores a copy of all filled in arguments with each curried result
925     //this way, the curried functions are independent and don't share any references
926     //eg: auto fc = curry!f;  auto fc1 = fc(1); auto fc2 = fc(2); fc1(3) != fc2(3)
927     struct CurryImpl(size_t N)
928     {
929         alias FParams = Parameters!F;
930         FParams[0 .. N] storedArguments;
931         static if (N > 0)
932         {
933             this(U : FParams[N - 1])(ref CurryImpl!(N - 1) prev, ref U arg)
934             {
935                 storedArguments[0 .. N - 1] = prev.storedArguments[];
936                 storedArguments[N-1] = arg;
937             }
938         }
939 
940         auto opCall(U : FParams[N])(auto ref U arg) return scope
941         {
942             static if (N == FParams.length - 1)
943             {
944                 return F(storedArguments, arg);
945             }
946             else
947             {
948                 return CurryImpl!(N + 1)(this, arg);
949             }
950         }
951     }
952 
953     auto curry()
954     {
955         CurryImpl!0 res;
956         return res; // return CurryImpl!0.init segfaults for delegates on Windows
957     }
958 }
959 
960 ///
961 pure @safe @nogc nothrow unittest
962 {
963     int f(int x, int y, int z)
964     {
965         return x + y + z;
966     }
967     auto cf = curry!f;
968     auto cf1 = cf(1);
969     auto cf2 = cf(2);
970 
971     assert(cf1(2)(3) == f(1, 2, 3));
972     assert(cf2(2)(3) == f(2, 2, 3));
973 }
974 
975 ///ditto
976 auto curry(T)(T t)
977 if (isCallable!T && Parameters!T.length)
978 {
979     static auto fun(ref T inst, ref Parameters!T args)
980     {
981         return inst(args);
982     }
983 
984     return curry!fun()(t);
985 }
986 
987 ///
988 pure @safe @nogc nothrow unittest
989 {
990     //works with callable structs too
991     struct S
992     {
993         int w;
994         int opCall(int x, int y, int z)
995         {
996             return w + x + y + z;
997         }
998     }
999 
1000     S s;
1001     s.w = 5;
1002 
1003     auto cs = curry(s);
1004     auto cs1 = cs(1);
1005     auto cs2 = cs(2);
1006 
1007     assert(cs1(2)(3) == s(1, 2, 3));
1008     assert(cs1(2)(3) == (1 + 2 + 3 + 5));
1009     assert(cs2(2)(3) ==s(2, 2, 3));
1010 }
1011 
1012 
1013 @safe pure @nogc nothrow unittest
1014 {
1015     //currying a single argument function does nothing
1016     int pork(int a){ return a*2;}
1017     auto curryPork = curry!pork;
1018     assert(curryPork(0) == pork(0));
1019     assert(curryPork(1) == pork(1));
1020     assert(curryPork(-1) == pork(-1));
1021     assert(curryPork(1000) == pork(1000));
1022 
1023     //test 2 argument function
1024     double mixedVeggies(double a, int b, bool)
1025     {
1026         return a + b;
1027     }
1028 
1029     auto mixedCurry = curry!mixedVeggies;
1030     assert(mixedCurry(10)(20)(false) == mixedVeggies(10, 20, false));
1031     assert(mixedCurry(100)(200)(true) == mixedVeggies(100, 200, true));
1032 
1033     // struct with opCall
1034     struct S
1035     {
1036         double opCall(int x, double y, short z) const pure nothrow @nogc
1037         {
1038             return x*y*z;
1039         }
1040     }
1041 
1042     S s;
1043     auto curriedStruct = curry(s);
1044     assert(curriedStruct(1)(2)(short(3)) == s(1, 2, short(3)));
1045     assert(curriedStruct(300)(20)(short(10)) == s(300, 20, short(10)));
1046 }
1047 
1048 pure @safe nothrow unittest
1049 {
1050     auto cfl = curry!((double a, int b)  => a + b);
1051     assert(cfl(13)(2) == 15);
1052 
1053     int c = 42;
1054     auto cdg = curry!((double a, int b)  => a + b + c);
1055     assert(cdg(13)(2) == 57);
1056 
1057     static class C
1058     {
1059         int opCall(int mult, int add) pure @safe nothrow @nogc scope
1060         {
1061             return  mult * 42 + add;
1062         }
1063     }
1064 
1065     scope C ci = new C();
1066     scope cc = curry(ci);
1067     assert(cc(2)(4) == ci(2, 4));
1068 }
1069 
1070 // Disallows callables without parameters
1071 pure @safe @nogc nothrow unittest
1072 {
1073     static void noargs() {}
1074     static assert(!__traits(compiles, curry!noargs()));
1075 
1076     static struct NoArgs
1077     {
1078         void opCall() {}
1079     }
1080 
1081     static assert(!__traits(compiles, curry(NoArgs.init)));
1082 }
1083 
1084 private template Iota(size_t n)
1085 {
1086     static if (n == 0)
1087         alias Iota = AliasSeq!();
1088     else
1089         alias Iota = AliasSeq!(Iota!(n - 1), n - 1);
1090 }
1091 
1092 /**
1093 Takes multiple functions and adjoins them together.
1094 
1095 Params:
1096     F = the call-able(s) to adjoin
1097 Returns:
1098     A new function which returns a $(REF Tuple, std,typecons). Each of the
1099     elements of the tuple will be the return values of `F`.
1100 
1101 Note: In the special case where only a single function is provided
1102 ($(D F.length == 1)), adjoin simply aliases to the single passed function
1103 (`F[0]`).
1104 */
1105 template adjoin(F...)
1106 if (F.length >= 1)
1107 {
1108     static if (F.length == 1)
1109         alias adjoin = F[0];
1110     else
1111         auto adjoin(V...)(auto ref V a)
1112         {
1113             import std.typecons : tuple;
1114             import std.meta : staticMap;
1115 
1116             auto resultElement(size_t i)()
1117             {
1118                 return F[i](a);
1119             }
1120 
1121             return tuple(staticMap!(resultElement, Iota!(F.length)));
1122         }
1123 }
1124 
1125 ///
1126 @safe unittest
1127 {
1128     import std.typecons : Tuple;
1129     static bool f1(int a) { return a != 0; }
1130     static int f2(int a) { return a / 2; }
1131     auto x = adjoin!(f1, f2)(5);
1132     assert(is(typeof(x) == Tuple!(bool, int)));
1133     assert(x[0] == true && x[1] == 2);
1134 }
1135 
1136 @safe unittest
1137 {
1138     import std.typecons : Tuple;
1139     static bool F1(int a) { return a != 0; }
1140     auto x1 = adjoin!(F1)(5);
1141     static int F2(int a) { return a / 2; }
1142     auto x2 = adjoin!(F1, F2)(5);
1143     assert(is(typeof(x2) == Tuple!(bool, int)));
1144     assert(x2[0] && x2[1] == 2);
1145     auto x3 = adjoin!(F1, F2, F2)(5);
1146     assert(is(typeof(x3) == Tuple!(bool, int, int)));
1147     assert(x3[0] && x3[1] == 2 && x3[2] == 2);
1148 
1149     bool F4(int a) { return a != x1; }
1150     alias eff4 = adjoin!(F4);
1151     static struct S
1152     {
1153         bool delegate(int) @safe store;
1154         int fun() { return 42 + store(5); }
1155     }
1156     S s;
1157     s.store = (int a) { return eff4(a); };
1158     auto x4 = s.fun();
1159     assert(x4 == 43);
1160 }
1161 
1162 @safe unittest
1163 {
1164     import std.meta : staticMap;
1165     import std.typecons : Tuple, tuple;
1166     alias funs = staticMap!(unaryFun, "a", "a * 2", "a * 3", "a * a", "-a");
1167     alias afun = adjoin!funs;
1168     assert(afun(5) == tuple(5, 10, 15, 25, -5));
1169 
1170     static class C{}
1171     alias IC = immutable(C);
1172     IC foo(){return typeof(return).init;}
1173     Tuple!(IC, IC, IC, IC) ret1 = adjoin!(foo, foo, foo, foo)();
1174 
1175     static struct S{int* p;}
1176     alias IS = immutable(S);
1177     IS bar(){return typeof(return).init;}
1178     enum Tuple!(IS, IS, IS, IS) ret2 = adjoin!(bar, bar, bar, bar)();
1179 }
1180 
1181 // https://issues.dlang.org/show_bug.cgi?id=21347
1182 @safe @betterC unittest
1183 {
1184     alias f = (int n) => n + 1;
1185     alias g = (int n) => n + 2;
1186     alias h = (int n) => n + 3;
1187     alias i = (int n) => n + 4;
1188 
1189     auto result = adjoin!(f, g, h, i)(0);
1190 
1191     assert(result[0] == 1);
1192     assert(result[1] == 2);
1193     assert(result[2] == 3);
1194     assert(result[3] == 4);
1195 }
1196 
1197 /**
1198    Composes passed-in functions $(D fun[0], fun[1], ...).
1199 
1200    Params:
1201         fun = the call-able(s) or `string`(s) to compose into one function
1202     Returns:
1203         A new function `f(x)` that in turn returns `fun[0](fun[1](...(x)))...`.
1204 
1205    See_Also: $(LREF pipe)
1206 */
1207 template compose(fun...)
1208 if (fun.length > 0)
1209 {
1210     static if (fun.length == 1)
1211     {
1212         alias compose = unaryFun!(fun[0]);
1213     }
1214     else
1215     {
1216         alias fun0 = unaryFun!(fun[0]);
1217         alias rest = compose!(fun[1 .. $]);
1218 
1219         auto compose(Args...)(Args args)
1220         {
1221             return fun0(rest(args));
1222         }
1223     }
1224 }
1225 
1226 ///
1227 @safe unittest
1228 {
1229     import std.algorithm.comparison : equal;
1230     import std.algorithm.iteration : map;
1231     import std.array : split;
1232     import std.conv : to;
1233 
1234     // First split a string in whitespace-separated tokens and then
1235     // convert each token into an integer
1236     assert(compose!(map!(to!(int)), split)("1 2 3").equal([1, 2, 3]));
1237 }
1238 
1239 // https://issues.dlang.org/show_bug.cgi?id=6484
1240 @safe unittest
1241 {
1242     int f(int a) { return a; }
1243     int g(int a) { return a; }
1244     int h(int a,int b,int c) { return a * b * c; }
1245 
1246     alias F = compose!(f,g,h);
1247     assert(F(1,2,3) == f(g(h(1,2,3))));
1248 }
1249 
1250 /**
1251    Pipes functions in sequence. Offers the same functionality as $(D
1252    compose), but with functions specified in reverse order. This may
1253    lead to more readable code in some situation because the order of
1254    execution is the same as lexical order.
1255 
1256    Params:
1257         fun = the call-able(s) or `string`(s) to compose into one function
1258     Returns:
1259         A new function `f(x)` that in turn returns `fun[$-1](...fun[1](fun[0](x)))...`.
1260 
1261    Example:
1262 
1263 ----
1264 // Read an entire text file, split the resulting string in
1265 // whitespace-separated tokens, and then convert each token into an
1266 // integer
1267 int[] a = pipe!(readText, split, map!(to!(int)))("file.txt");
1268 ----
1269 
1270    See_Also: $(LREF compose)
1271  */
1272 alias pipe(fun...) = compose!(Reverse!(fun));
1273 
1274 ///
1275 @safe unittest
1276 {
1277     import std.conv : to;
1278     string foo(int a) { return to!(string)(a); }
1279     int bar(string a) { return to!(int)(a) + 1; }
1280     double baz(int a) { return a + 0.5; }
1281     assert(compose!(baz, bar, foo)(1) == 2.5);
1282     assert(pipe!(foo, bar, baz)(1) == 2.5);
1283 
1284     assert(compose!(baz, `to!(int)(a) + 1`, foo)(1) == 2.5);
1285     assert(compose!(baz, bar)("1"[]) == 2.5);
1286 
1287     assert(compose!(baz, bar)("1") == 2.5);
1288 
1289     assert(compose!(`a + 0.5`, `to!(int)(a) + 1`, foo)(1) == 2.5);
1290 }
1291 
1292 /**
1293  * $(LINK2 https://en.wikipedia.org/wiki/Memoization, Memoizes) a function so as
1294  * to avoid repeated computation. The memoization structure is a hash table keyed by a
1295  * tuple of the function's arguments. There is a speed gain if the
1296  * function is repeatedly called with the same arguments and is more
1297  * 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).
1298 
1299 Example:
1300 ----
1301 double transmogrify(int a, string b)
1302 {
1303    ... expensive computation ...
1304 }
1305 alias fastTransmogrify = memoize!transmogrify;
1306 unittest
1307 {
1308     auto slow = transmogrify(2, "hello");
1309     auto fast = fastTransmogrify(2, "hello");
1310     assert(slow == fast);
1311 }
1312 ----
1313 
1314 Params:
1315     fun = the call-able to memozie
1316     maxSize = The maximum size of the GC buffer to hold the return values
1317 Returns:
1318     A new function which calls `fun` and caches its return values.
1319 
1320 Note:
1321     Technically the memoized function should be pure because `memoize` assumes it will
1322     always return the same result for a given tuple of arguments. However, `memoize` does not
1323     enforce that because sometimes it is useful to memoize an impure function, too.
1324 */
1325 template memoize(alias fun)
1326 {
1327     import std.traits : ReturnType;
1328      // https://issues.dlang.org/show_bug.cgi?id=13580
1329     // alias Args = Parameters!fun;
1330 
1331     ReturnType!fun memoize(Parameters!fun args)
1332     {
1333         alias Args = Parameters!fun;
1334         import std.typecons : Tuple;
1335         import std.traits : Unqual;
1336 
1337         static Unqual!(ReturnType!fun)[Tuple!Args] memo;
1338         auto t = Tuple!Args(args);
1339         if (auto p = t in memo)
1340             return *p;
1341         auto r = fun(args);
1342         memo[t] = r;
1343         return r;
1344     }
1345 }
1346 
1347 /// ditto
1348 template memoize(alias fun, uint maxSize)
1349 {
1350     import std.traits : ReturnType;
1351      // https://issues.dlang.org/show_bug.cgi?id=13580
1352     // alias Args = Parameters!fun;
1353     ReturnType!fun memoize(Parameters!fun args)
1354     {
1355         import std.meta : staticMap;
1356         import std.traits : hasIndirections, Unqual;
1357         import std.typecons : tuple;
1358         static struct Value { staticMap!(Unqual, Parameters!fun) args; Unqual!(ReturnType!fun) res; }
1359         static Value[] memo;
1360         static size_t[] initialized;
1361 
1362         if (!memo.length)
1363         {
1364             import core.memory : GC;
1365 
1366             // Ensure no allocation overflows
1367             static assert(maxSize < size_t.max / Value.sizeof);
1368             static assert(maxSize < size_t.max - (8 * size_t.sizeof - 1));
1369 
1370             enum attr = GC.BlkAttr.NO_INTERIOR | (hasIndirections!Value ? 0 : GC.BlkAttr.NO_SCAN);
1371             memo = (cast(Value*) GC.malloc(Value.sizeof * maxSize, attr))[0 .. maxSize];
1372             enum nwords = (maxSize + 8 * size_t.sizeof - 1) / (8 * size_t.sizeof);
1373             initialized = (cast(size_t*) GC.calloc(nwords * size_t.sizeof, attr | GC.BlkAttr.NO_SCAN))[0 .. nwords];
1374         }
1375 
1376         import core.bitop : bt, bts;
1377         import core.lifetime : emplace;
1378 
1379         size_t hash;
1380         foreach (ref arg; args)
1381             hash = hashOf(arg, hash);
1382         // cuckoo hashing
1383         immutable idx1 = hash % maxSize;
1384         if (!bt(initialized.ptr, idx1))
1385         {
1386             emplace(&memo[idx1], args, fun(args));
1387             // only set to initialized after setting args and value
1388             // https://issues.dlang.org/show_bug.cgi?id=14025
1389             bts(initialized.ptr, idx1);
1390             return memo[idx1].res;
1391         }
1392         else if (memo[idx1].args == args)
1393             return memo[idx1].res;
1394         // FNV prime
1395         immutable idx2 = (hash * 16_777_619) % maxSize;
1396         if (!bt(initialized.ptr, idx2))
1397         {
1398             emplace(&memo[idx2], memo[idx1]);
1399             bts(initialized.ptr, idx2);
1400         }
1401         else if (memo[idx2].args == args)
1402             return memo[idx2].res;
1403         else if (idx1 != idx2)
1404             memo[idx2] = memo[idx1];
1405 
1406         memo[idx1] = Value(args, fun(args));
1407         return memo[idx1].res;
1408     }
1409 }
1410 
1411 /**
1412  * To _memoize a recursive function, simply insert the memoized call in lieu of the plain recursive call.
1413  * For example, to transform the exponential-time Fibonacci implementation into a linear-time computation:
1414  */
1415 @safe nothrow
1416 unittest
1417 {
1418     ulong fib(ulong n) @safe nothrow
1419     {
1420         return n < 2 ? n : memoize!fib(n - 2) + memoize!fib(n - 1);
1421     }
1422     assert(fib(10) == 55);
1423 }
1424 
1425 /**
1426  * To improve the speed of the factorial function,
1427  */
1428 @safe unittest
1429 {
1430     ulong fact(ulong n) @safe
1431     {
1432         return n < 2 ? 1 : n * memoize!fact(n - 1);
1433     }
1434     assert(fact(10) == 3628800);
1435 }
1436 
1437 /**
1438  * This memoizes all values of `fact` up to the largest argument. To only cache the final
1439  * result, move `memoize` outside the function as shown below.
1440  */
1441 @safe unittest
1442 {
1443     ulong factImpl(ulong n) @safe
1444     {
1445         return n < 2 ? 1 : n * factImpl(n - 1);
1446     }
1447     alias fact = memoize!factImpl;
1448     assert(fact(10) == 3628800);
1449 }
1450 
1451 /**
1452  * When the `maxSize` parameter is specified, memoize will used
1453  * a fixed size hash table to limit the number of cached entries.
1454  */
1455 @system unittest // not @safe due to memoize
1456 {
1457     ulong fact(ulong n)
1458     {
1459         // Memoize no more than 8 values
1460         return n < 2 ? 1 : n * memoize!(fact, 8)(n - 1);
1461     }
1462     assert(fact(8) == 40320);
1463     // using more entries than maxSize will overwrite existing entries
1464     assert(fact(10) == 3628800);
1465 }
1466 
1467 @system unittest // not @safe due to memoize
1468 {
1469     import core.math : sqrt;
1470     alias msqrt = memoize!(function double(double x) { return sqrt(x); });
1471     auto y = msqrt(2.0);
1472     assert(y == msqrt(2.0));
1473     y = msqrt(4.0);
1474     assert(y == sqrt(4.0));
1475 
1476     // alias mrgb2cmyk = memoize!rgb2cmyk;
1477     // auto z = mrgb2cmyk([43, 56, 76]);
1478     // assert(z == mrgb2cmyk([43, 56, 76]));
1479 
1480     //alias mfib = memoize!fib;
1481 
1482     static ulong fib(ulong n) @safe
1483     {
1484         alias mfib = memoize!fib;
1485         return n < 2 ? 1 : mfib(n - 2) + mfib(n - 1);
1486     }
1487 
1488     auto z = fib(10);
1489     assert(z == 89);
1490 
1491     static ulong fact(ulong n) @safe
1492     {
1493         alias mfact = memoize!fact;
1494         return n < 2 ? 1 : n * mfact(n - 1);
1495     }
1496     assert(fact(10) == 3628800);
1497 
1498     // https://issues.dlang.org/show_bug.cgi?id=12568
1499     static uint len2(const string s) { // Error
1500     alias mLen2 = memoize!len2;
1501     if (s.length == 0)
1502         return 0;
1503     else
1504         return 1 + mLen2(s[1 .. $]);
1505     }
1506 
1507     int _func(int x) @safe { return 1; }
1508     alias func = memoize!(_func, 10);
1509     assert(func(int.init) == 1);
1510     assert(func(int.init) == 1);
1511 }
1512 
1513 // https://issues.dlang.org/show_bug.cgi?id=16079
1514 // memoize should work with arrays
1515 @system unittest // not @safe with -dip1000 due to memoize
1516 {
1517     int executed = 0;
1518     T median(T)(const T[] nums) {
1519         import std.algorithm.sorting : sort;
1520         executed++;
1521         auto arr = nums.dup;
1522         arr.sort();
1523         if (arr.length % 2)
1524             return arr[$ / 2];
1525         else
1526             return (arr[$ / 2 - 1]
1527                 + arr[$ / 2]) / 2;
1528     }
1529 
1530     alias fastMedian = memoize!(median!int);
1531 
1532     assert(fastMedian([7, 5, 3]) == 5);
1533     assert(fastMedian([7, 5, 3]) == 5);
1534 
1535     assert(executed == 1);
1536 }
1537 
1538 // https://issues.dlang.org/show_bug.cgi?id=16079: memoize should work with structs
1539 @safe unittest
1540 {
1541     int executed = 0;
1542     T pickFirst(T)(T first)
1543     {
1544         executed++;
1545         return first;
1546     }
1547 
1548     struct Foo { int k; }
1549     Foo A = Foo(3);
1550 
1551     alias first = memoize!(pickFirst!Foo);
1552     assert(first(Foo(3)) == A);
1553     assert(first(Foo(3)) == A);
1554     assert(executed == 1);
1555 }
1556 
1557 // https://issues.dlang.org/show_bug.cgi?id=20439 memoize should work with void opAssign
1558 @safe unittest
1559 {
1560     static struct S
1561     {
1562         void opAssign(S) {}
1563     }
1564 
1565     assert(memoize!(() => S()) == S());
1566 }
1567 
1568 // https://issues.dlang.org/show_bug.cgi?id=16079: memoize should work with classes
1569 @system unittest // not @safe with -dip1000 due to memoize
1570 {
1571     int executed = 0;
1572     T pickFirst(T)(T first)
1573     {
1574         executed++;
1575         return first;
1576     }
1577 
1578     class Bar
1579     {
1580         size_t k;
1581         this(size_t k)
1582         {
1583             this.k = k;
1584         }
1585         override size_t toHash()
1586         {
1587             return k;
1588         }
1589         override bool opEquals(Object o)
1590         {
1591             auto b = cast(Bar) o;
1592             return b && k == b.k;
1593         }
1594     }
1595 
1596     alias firstClass = memoize!(pickFirst!Bar);
1597     assert(firstClass(new Bar(3)).k == 3);
1598     assert(firstClass(new Bar(3)).k == 3);
1599     assert(executed == 1);
1600 }
1601 
1602 // https://issues.dlang.org/show_bug.cgi?id=20302
1603 @system unittest
1604 {
1605     version (none) // TODO change `none` to `all` and fix remaining limitations
1606         struct S { const int len; }
1607     else
1608         struct S { int len; }
1609 
1610     static       string  fun000(      string str,       S s) { return str[0 .. s.len] ~ "123"; }
1611     static       string  fun001(      string str, const S s) { return str[0 .. s.len] ~ "123"; }
1612     static       string  fun010(const string str,       S s) { return str[0 .. s.len] ~ "123"; }
1613     static       string  fun011(const string str, const S s) { return str[0 .. s.len] ~ "123"; }
1614     static const(string) fun100(      string str,       S s) { return str[0 .. s.len] ~ "123"; }
1615     static const(string) fun101(      string str, const S s) { return str[0 .. s.len] ~ "123"; }
1616     static const(string) fun110(const string str,       S s) { return str[0 .. s.len] ~ "123"; }
1617     static const(string) fun111(const string str, const S s) { return str[0 .. s.len] ~ "123"; }
1618 
1619     static foreach (fun; AliasSeq!(fun000, fun001, fun010, fun011, fun100, fun101, fun110, fun111))
1620     {{
1621         alias mfun = memoize!fun;
1622         assert(mfun("abcdefgh", S(3)) == "abc123");
1623 
1624         alias mfun2 = memoize!(fun, 42);
1625         assert(mfun2("asd", S(3)) == "asd123");
1626     }}
1627 }
1628 
1629 private struct DelegateFaker(F)
1630 {
1631     import std.typecons : FuncInfo, MemberFunctionGenerator;
1632 
1633     // for @safe
1634     static F castToF(THIS)(THIS x) @trusted
1635     {
1636         return cast(F) x;
1637     }
1638 
1639     /*
1640      * What all the stuff below does is this:
1641      *--------------------
1642      * struct DelegateFaker(F) {
1643      *     extern(linkage)
1644      *     [ref] ReturnType!F doIt(Parameters!F args) [@attributes]
1645      *     {
1646      *         auto fp = cast(F) &this;
1647      *         return fp(args);
1648      *     }
1649      * }
1650      *--------------------
1651      */
1652 
1653     // We will use MemberFunctionGenerator in std.typecons.  This is a policy
1654     // configuration for generating the doIt().
1655     template GeneratingPolicy()
1656     {
1657         // Inform the genereator that we only have type information.
1658         enum WITHOUT_SYMBOL = true;
1659 
1660         // Generate the function body of doIt().
1661         template generateFunctionBody(unused...)
1662         {
1663             enum generateFunctionBody =
1664             // [ref] ReturnType doIt(Parameters args) @attributes
1665             q{
1666                 // When this function gets called, the this pointer isn't
1667                 // really a this pointer (no instance even really exists), but
1668                 // a function pointer that points to the function to be called.
1669                 // Cast it to the correct type and call it.
1670 
1671                 auto fp = castToF(&this);
1672                 return fp(args);
1673             };
1674         }
1675     }
1676     // Type information used by the generated code.
1677     alias FuncInfo_doIt = FuncInfo!(F);
1678 
1679     // Generate the member function doIt().
1680     mixin( MemberFunctionGenerator!(GeneratingPolicy!())
1681             .generateFunction!("FuncInfo_doIt", "doIt", F) );
1682 }
1683 
1684 /**
1685  * Convert a callable to a delegate with the same parameter list and
1686  * return type, avoiding heap allocations and use of auxiliary storage.
1687  *
1688  * Params:
1689  *     fp = a function pointer or an aggregate type with `opCall` defined.
1690  * Returns:
1691  *     A delegate with the context pointer pointing to nothing.
1692  *
1693  * Example:
1694  * ----
1695  * void doStuff() {
1696  *     writeln("Hello, world.");
1697  * }
1698  *
1699  * void runDelegate(void delegate() myDelegate) {
1700  *     myDelegate();
1701  * }
1702  *
1703  * auto delegateToPass = toDelegate(&doStuff);
1704  * runDelegate(delegateToPass);  // Calls doStuff, prints "Hello, world."
1705  * ----
1706  *
1707  * BUGS:
1708  * $(UL
1709  *   $(LI Does not work with `@safe` functions.)
1710  *   $(LI Ignores C-style / D-style variadic arguments.)
1711  * )
1712  */
1713 auto toDelegate(F)(auto ref F fp)
1714 if (isCallable!(F))
1715 {
1716     static if (is(F == delegate))
1717     {
1718         return fp;
1719     }
1720     else static if (is(typeof(&F.opCall) == delegate)
1721                 || (is(typeof(&F.opCall) V : V*) && is(V == function)))
1722     {
1723         return toDelegate(&fp.opCall);
1724     }
1725     else
1726     {
1727         alias DelType = typeof(&(new DelegateFaker!(F)).doIt);
1728 
1729         static struct DelegateFields {
1730             union {
1731                 DelType del;
1732                 //pragma(msg, typeof(del));
1733 
1734                 struct {
1735                     void* contextPtr;
1736                     void* funcPtr;
1737                 }
1738             }
1739         }
1740 
1741         // fp is stored in the returned delegate's context pointer.
1742         // The returned delegate's function pointer points to
1743         // DelegateFaker.doIt.
1744         DelegateFields df;
1745 
1746         df.contextPtr = cast(void*) fp;
1747 
1748         DelegateFaker!(F) dummy;
1749         auto dummyDel = &dummy.doIt;
1750         df.funcPtr = dummyDel.funcptr;
1751 
1752         return df.del;
1753     }
1754 }
1755 
1756 ///
1757 @system unittest
1758 {
1759     static int inc(ref uint num) {
1760         num++;
1761         return 8675309;
1762     }
1763 
1764     uint myNum = 0;
1765     auto incMyNumDel = toDelegate(&inc);
1766     auto returnVal = incMyNumDel(myNum);
1767     assert(myNum == 1);
1768 }
1769 
1770 @system unittest // not @safe due to toDelegate
1771 {
1772     static int inc(ref uint num) {
1773         num++;
1774         return 8675309;
1775     }
1776 
1777     uint myNum = 0;
1778     auto incMyNumDel = toDelegate(&inc);
1779     int delegate(ref uint) dg = incMyNumDel;
1780     auto returnVal = incMyNumDel(myNum);
1781     assert(myNum == 1);
1782 
1783     interface I { int opCall(); }
1784     class C: I { int opCall() { inc(myNum); return myNum;} }
1785     auto c = new C;
1786     auto i = cast(I) c;
1787 
1788     auto getvalc = toDelegate(c);
1789     assert(getvalc() == 2);
1790 
1791     auto getvali = toDelegate(i);
1792     assert(getvali() == 3);
1793 
1794     struct S1 { int opCall() { inc(myNum); return myNum; } }
1795     static assert(!is(typeof(&s1.opCall) == delegate));
1796     S1 s1;
1797     auto getvals1 = toDelegate(s1);
1798     assert(getvals1() == 4);
1799 
1800     struct S2 { static int opCall() { return 123456; } }
1801     static assert(!is(typeof(&S2.opCall) == delegate));
1802     S2 s2;
1803     auto getvals2 =&S2.opCall;
1804     assert(getvals2() == 123456);
1805 
1806     /* test for attributes */
1807     {
1808         static int refvar = 0xDeadFace;
1809 
1810         static ref int func_ref() { return refvar; }
1811         static int func_pure() pure { return 1; }
1812         static int func_nothrow() nothrow { return 2; }
1813         static int func_property() @property { return 3; }
1814         static int func_safe() @safe { return 4; }
1815         static int func_trusted() @trusted { return 5; }
1816         static int func_system() @system { return 6; }
1817         static int func_pure_nothrow() pure nothrow { return 7; }
1818         static int func_pure_nothrow_safe() pure nothrow @safe { return 8; }
1819 
1820         auto dg_ref = toDelegate(&func_ref);
1821         int delegate() pure dg_pure = toDelegate(&func_pure);
1822         int delegate() nothrow dg_nothrow = toDelegate(&func_nothrow);
1823         int delegate() @property dg_property = toDelegate(&func_property);
1824         int delegate() @safe dg_safe = toDelegate(&func_safe);
1825         int delegate() @trusted dg_trusted = toDelegate(&func_trusted);
1826         int delegate() @system dg_system = toDelegate(&func_system);
1827         int delegate() pure nothrow dg_pure_nothrow = toDelegate(&func_pure_nothrow);
1828         int delegate() @safe pure nothrow dg_pure_nothrow_safe = toDelegate(&func_pure_nothrow_safe);
1829 
1830         //static assert(is(typeof(dg_ref) == ref int delegate())); // [BUG@DMD]
1831 
1832         assert(dg_ref() == refvar);
1833         assert(dg_pure() == 1);
1834         assert(dg_nothrow() == 2);
1835         assert(dg_property() == 3);
1836         assert(dg_safe() == 4);
1837         assert(dg_trusted() == 5);
1838         assert(dg_system() == 6);
1839         assert(dg_pure_nothrow() == 7);
1840         assert(dg_pure_nothrow_safe() == 8);
1841     }
1842     /* test for linkage */
1843     {
1844         struct S
1845         {
1846             extern(C) static void xtrnC() {}
1847             extern(D) static void xtrnD() {}
1848         }
1849         auto dg_xtrnC = toDelegate(&S.xtrnC);
1850         auto dg_xtrnD = toDelegate(&S.xtrnD);
1851         static assert(! is(typeof(dg_xtrnC) == typeof(dg_xtrnD)));
1852     }
1853 }
1854 
1855 /**
1856  * Passes the fields of a struct as arguments to a function.
1857  *
1858  * Can be used with a $(LINK2 https://dlang.org/spec/expression.html#function_literals,
1859  * function literal) to give temporary names to the fields of a struct or
1860  * tuple.
1861  *
1862  * Params:
1863  *   fun = Callable that the struct's fields will be passed to.
1864  *
1865  * Returns:
1866  *   A function that accepts a single struct as an argument and passes its
1867  *   fields to `fun` when called.
1868  */
1869 template bind(alias fun)
1870 {
1871     /**
1872      * Params:
1873      *   args = The struct or tuple whose fields will be used as arguments.
1874      *
1875      * Returns: `fun(args.tupleof)`
1876      */
1877     auto ref bind(T)(auto ref T args)
1878     if (is(T == struct))
1879     {
1880         import std.meta : Map = staticMap;
1881         import core.lifetime : move;
1882 
1883         // Forwards the i'th member of `args`
1884         // Needed because core.lifetime.forward doesn't work on struct members
1885         template forwardArg(size_t i)
1886         {
1887             static if (__traits(isRef, args) || !is(typeof(move(args.tupleof[i]))))
1888                 enum forwardArg = "args.tupleof[" ~ toCtString!i ~ "], ";
1889             else
1890                 enum forwardArg = "move(args.tupleof[" ~ toCtString!i ~ "]), ";
1891         }
1892 
1893         static if (args.tupleof.length == 0)
1894             enum argList = "";
1895         else
1896             alias argList = Map!(forwardArg, Iota!(args.tupleof.length));
1897 
1898         return mixin("fun(", argList, ")");
1899     }
1900 }
1901 
1902 /// Giving names to tuple elements
1903 @safe unittest
1904 {
1905     import std.typecons : tuple;
1906 
1907     auto name = tuple("John", "Doe");
1908     string full = name.bind!((first, last) => first ~ " " ~ last);
1909     assert(full == "John Doe");
1910 }
1911 
1912 /// Passing struct fields to a function
1913 @safe unittest
1914 {
1915     import std.algorithm.comparison : min, max;
1916 
1917     struct Pair
1918     {
1919         int a;
1920         int b;
1921     }
1922 
1923     auto p = Pair(123, 456);
1924     assert(p.bind!min == 123); // min(p.a, p.b)
1925     assert(p.bind!max == 456); // max(p.a, p.b)
1926 }
1927 
1928 /// In a range pipeline
1929 @safe unittest
1930 {
1931     import std.algorithm.iteration : map, filter;
1932     import std.algorithm.comparison : equal;
1933     import std.typecons : tuple;
1934 
1935     auto ages = [
1936         tuple("Alice", 35),
1937         tuple("Bob",   64),
1938         tuple("Carol", 21),
1939         tuple("David", 39),
1940         tuple("Eve",   50)
1941     ];
1942 
1943     auto overForty = ages
1944         .filter!(bind!((name, age) => age > 40))
1945         .map!(bind!((name, age) => name));
1946 
1947     assert(overForty.equal(["Bob", "Eve"]));
1948 }
1949 
1950 // Zero arguments
1951 @safe unittest
1952 {
1953     struct Empty {}
1954 
1955     assert(Empty().bind!(() => 123) == 123);
1956 }
1957 
1958 // Non-copyable arguments
1959 @safe unittest
1960 {
1961     import std.typecons : tuple;
1962 
1963     static struct NoCopy
1964     {
1965         int n;
1966         @disable this(this);
1967     }
1968 
1969     static struct Pair
1970     {
1971         NoCopy a, b;
1972     }
1973 
1974     static auto fun(NoCopy a, NoCopy b)
1975     {
1976         return tuple(a.n, b.n);
1977     }
1978 
1979     auto expected = fun(NoCopy(1), NoCopy(2));
1980     assert(Pair(NoCopy(1), NoCopy(2)).bind!fun == expected);
1981 }
1982 
1983 // ref arguments
1984 @safe unittest
1985 {
1986     import std.typecons : tuple;
1987 
1988     auto t = tuple(123, 456);
1989     t.bind!((ref int a, int b) { a = 789; b = 1011; });
1990 
1991     assert(t[0] == 789);
1992     assert(t[1] == 456);
1993 }
1994 
1995 // auto ref arguments
1996 @safe unittest
1997 {
1998     import std.typecons : tuple;
1999 
2000     auto t = tuple(123);
2001     t.bind!((auto ref x) {
2002         static assert(__traits(isRef, x));
2003     });
2004     tuple(123).bind!((auto ref x) {
2005         static assert(!__traits(isRef, x));
2006     });
2007 }