Note: This website is archived. For up-to-date information about D projects and development, please visit wiki.dlang.org.

# Changeset 2271

Show
Ignore:
Timestamp:
01/04/11 03:46:01 (5 years ago)
Message:

Files:

Unmodified
Removed
Modified
Copied
Moved
• ## trunk/phobos/std/functional.d

r2195 r2271
99
1212Authors:   \$(WEB erdani.org, Andrei Alexandrescu)
1313*/

501501----
502502 */
503
504503template pipe(fun...)
505504{

509508unittest
510509{
513     // double baz(int a) { return a + 0.5; }
514     // assert(compose!(baz, bar, foo)(1) == 2.5);
515     // assert(pipe!(foo, bar, baz)(1) == 2.5);
516
517     // assert(compose!(baz, `to!(int)(a) + 1`, foo)(1) == 2.5);
518     // assert(compose!(baz, bar)("1"[]) == 2.5);
519
520     // @@@BUG@@@
521     //assert(compose!(baz, bar)("1") == 2.5);
512    double baz(int a) { return a + 0.5; }
513    assert(compose!(baz, bar, foo)(1) == 2.5);
514    assert(pipe!(foo, bar, baz)(1) == 2.5);
515
516    assert(compose!(baz, `to!(int)(a) + 1`, foo)(1) == 2.5);
517    assert(compose!(baz, bar)("1"[]) == 2.5);
518
519    assert(compose!(baz, bar)("1") == 2.5);
522520
523521    // @@@BUG@@@
524522    //assert(compose!(`a + 0.5`, `to!(int)(a) + 1`, foo)(1) == 2.5);
523}
524
525/**
526 * \$(LUCKY Memoizes) a function so as to avoid repeated
527 * computation. The memoization structure is a hash table keyed by a
528 * tuple of the function's arguments. There is a speed gain if the
529 * function is repeatedly called with the same arguments and is more
530 * expensive than a hash table lookup.
531
532Example:
533----
534double transmogrify(int a, string b)
535{
536   ... expensive computation ...
537}
538alias memoize!transmogrify fastTransmogrify;
539unittest
540{
541    auto slow = transmogrify(2, "hello");
542    auto fast = fastTransmogrify(2, "hello");
543    assert(slow == fast);
544}
545----
546
547Technically the memoized function should be pure because \$(D memoize) assumes it will
548always return the same result for a given tuple of arguments. However, \$(D memoize) does not
549enforce that because sometimes it
550is useful to memoize an impure function, too.
551
552To _memoize a recursive function, simply insert the memoized call in lieu of the plain recursive call.
553For example, to transform the exponential-time Fibonacci implementation into a linear-time computation:
554
555Example:
556----
557ulong fib(ulong n)
558{
559    alias memoize!fib mfib;
560    return n < 2 ? 1 : mfib(n - 2) + mfib(n - 1);
561}
562...
563assert(fib(10) == 89);
564----
565
566To improve the speed of the factorial function,
567
568Example:
569----
570ulong fact(ulong n)
571{
572    alias memoize!fact mfact;
573    return n < 2 ? 1 : n * mfact(n - 1);
574}
575...
576assert(fact(10) == 3628800);
577----
578
579This memoizes all values of \$(D fact) up to the largest argument. To only cache the final
580result, move \$(D memoize) outside the function as shown below.
581
582Example:
583----
584ulong factImpl(ulong n)
585{
586    return n < 2 ? 1 : n * mfact(n - 1);
587}
588alias memoize!factImpl fact;
589...
590assert(fact(10) == 3628800);
591----
592
593The \$(D maxSize) parameter is a cutoff for the cache size. If upon a miss the length of the hash
594table is found to be \$(D maxSize), the table is simply cleared.
595
596Example:
597----
598// Memoize no more than 128 values of transmogrify
599alias memoize!(transmogrify, 128) fastTransmogrify;
600----
601*/
602template memoize(alias fun, uint maxSize = uint.max)
603{
604    ReturnType!fun memoize(ParameterTypeTuple!fun args)
605    {
606        static ReturnType!fun[Tuple!(typeof(args))] memo;
607        auto t = tuple(args);
608        auto p = t in memo;
609        if (p) return *p;
610        static if (maxSize != uint.max)
611        {
612            if (memo.length >= maxSize) memo = null;
613        }
614        auto r = fun(args);
615        //writeln("Inserting result ", typeof(r).stringof, "(", r, ") for parameters ", t);
616        memo[t] = r;
617        return r;
618    }
619}
620
621unittest
622{
623    alias memoize!(function double(double x) { return sqrt(x); }) msqrt;
624    auto y = msqrt(2.0);
625    assert(y == msqrt(2.0));
626    y = msqrt(4.0);
627    assert(y == sqrt(4.0));
628
629    // alias memoize!rgb2cmyk mrgb2cmyk;
630    // auto z = mrgb2cmyk([43, 56, 76]);
631    // assert(z == mrgb2cmyk([43, 56, 76]));
632
633    //alias memoize!fib mfib;
634
635    static ulong fib(ulong n)
636    {
637        alias memoize!fib mfib;
638        return n < 2 ? 1 : mfib(n - 2) + mfib(n - 1);
639    }
640
641    auto z = fib(10);
642    assert(z == 89);
643
644    static ulong fact(ulong n)
645    {
646        alias memoize!fact mfact;
647        return n < 2 ? 1 : n * mfact(n - 1);
648    }
649    assert(fact(10) == 3628800);
525650}
526651

571696}
572697
573 /**Convert a callable to a delegate with the same parameter list and
698/**
699 * Convert a callable to a delegate with the same parameter list and
574700 * return type, avoiding heap allocations and use of auxiliary storage.
575701 *
576702 * Examples:
577  * ---
703 * ----
578704 * void doStuff() {
579705 *     writeln("Hello, world.");

586712 * auto delegateToPass = toDelegate(&doStuff);
587713 * runDelegate(delegateToPass);  // Calls doStuff, prints "Hello, world."
588  * ---
714 * ----
589715 *
590716 * BUGS:

594720 * )
595721 */
596 auto toDelegate(F)(auto ref F fp) if (isCallable!(F)) {
597
722auto toDelegate(F)(auto ref F fp) if (isCallable!(F))
723
598724    static if (is(F == delegate))
599725    {

727853    }
728854}
855