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 }