std.algorithm.expand

[dlangBugzillaToGithub]

bearophile_hugs reported this on 2014-09-14T12:20:45Z

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

CC List

• greensunny12
• hsteoh

Description

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;
}

[dlangBugzillaToGithub]

hsteoh commented on 2014-09-18T17:00:24Z

Aren't all cases of "expand" reducible to "recurrence"? Do you have an example where this isn't possible / is too ugly?

[dlangBugzillaToGithub]

bearophile_hugs commented on 2014-09-18T17:19:59Z

(In reply to hsteoh from comment #1)
> Aren't all cases of "expand" reducible to "recurrence"? Do you have an
> example where this isn't possible / is too ugly?

I think the functionality of recurrence is a superset of the functionality of this function expand. But expand looks more fundamental and cleaner.

[dlangBugzillaToGithub]

greensunny12 commented on 2018-03-31T14:47:55Z

> Aren't all cases of "expand" reducible to "recurrence"? Do you have an example where this isn't possible / is too ugly?

The closest pedant that D has to unfoldr (apart from recurrence) is its Generator:

---
import std.experimental.all;
void main()
{
    new Generator!int({
        foreach (i; 0 .. 10)
            yield(i);
    }).writeln;
}
---

https://run.dlang.io/is/DQgDN3

So I'm not sure if there's anything actionable to be taken from this issue?