• via Digitalmars-d-bugs (108/108) Sep 14 2014 https://issues.dlang.org/show_bug.cgi?id=13473

via Digitalmars-d-bugs <digitalmars-d-bugs puremagic.com> writes:

https://issues.dlang.org/show_bug.cgi?id=13473

          Issue ID: 13473
           Summary: std.algorithm.expand
           Product: D
           Version: D2
          Hardware: All
                OS: All
            Status: NEW
          Severity: enhancement
          Priority: P1
         Component: Phobos
          Assignee: nobody puremagic.com
          Reporter: bearophile_hugs eml.cc

I suggest to add to Phobos a function named "expand" similar to the Haskell
function "unfoldr":
http://hackage.haskell.org/package/base-4.7.0.1/docs/Data-List.html


Info on unfoldr:

- - - - - - - - - - - - - - - - -

unfoldr :: (b -> Maybe (a, b)) -> b -> [a] Source

The unfoldr function is a `dual' to foldr: while foldr reduces a list to a
summary value, unfoldr builds a list from a seed value. The function takes the
element and returns Nothing if it is done producing the list or returns Just
(a,b), in which case, a is a prepended to the list and b is used as the next
element in a recursive call. For example,

iterate f == unfoldr (\x -> Just (x, f x))

In some cases, unfoldr can undo a foldr operation:

unfoldr f' (foldr f z xs) == xs

if the following holds:

f' (f x y) = Just (x,y)
f' z       = Nothing

A simple use of unfoldr:

unfoldr (\b -> if b == 0 then Nothing else Just (b, b-1)) 10
 [10,9,8,7,6,5,4,3,2,1]

- - - - - - - - - - - - - - - - -

A basic implementation of expand with an usage example:



import std.stdio, std.typecons, std.traits, std.typetuple,
       std.range, std.algorithm;

auto expand(alias F, B)(B x) pure nothrow  safe  nogc
if (isCallable!F &&
    is(ParameterTypeTuple!F == TypeTuple!B)
    && __traits(isSame, TemplateOf!(ReturnType!F), Nullable)
    && isTuple!(TemplateArgsOf!(ReturnType!F)[0])
    && is(TemplateArgsOf!(TemplateArgsOf!(ReturnType!F)[0])[1] == B)) {

    alias NAB = ReturnType!F;
    alias AB = TemplateArgsOf!NAB[0];
    alias A = AB.Types[0];

    struct Expand {
        bool first;
        NAB last;

         property bool empty() pure nothrow  safe  nogc {
            if (first) {
                first = false;
                popFront;
            }
            return last.isNull;
        }

         property A front() pure nothrow  safe  nogc {
            if (first) {
                first = false;
                popFront;
            }
            return last.get[0];
        }

        void popFront() pure nothrow  safe  nogc {
            last = F(last.get[1]);
        }
    }

    return Expand(true, NAB(AB(A.init, x)));
}

void main() {
    Nullable!(Tuple!(int, int)) f1(int b)
    pure nothrow  safe  nogc {
        return (b == 0) ?
               typeof(return)() :
               typeof(return)(tuple(b, b - 1));
    }

    expand!f1(10).writeln;
}


Output:

[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]



A more complex usage example:


import std.stdio, std.typecons, std.traits, std.typetuple,
       std.range, std.algorithm;

auto divMod(T)(T x, T y) pure nothrow  safe  nogc {
    return tuple(x / y, x % y);
}

uint step(uint x) pure nothrow  safe  nogc {
    Nullable!(Tuple!(uint, uint)) f(uint n)
    pure nothrow  safe  nogc {
        return (n == 0) ?
               typeof(return)() :
               typeof(return)(divMod(n, 10u).reverse);
    }

    return expand!f(x).map!(x => x ^^ 2).sum;
}

uint iter(uint x) pure nothrow  nogc {
    return x
           .recurrence!((a, n) => step(a[n - 1]))
           .filter!(y => y.among!(1, 89))
           .front;
}

void main() {
    iota(1u, 100_000u)
    .filter!(n => n.iter == 89)
    .count
    .writeln;
}

--