Comment #0 by bearophile_hugs — 2014-09-14T12:20:45Z
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;
}
Comment #1 by hsteoh — 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?
Comment #2 by bearophile_hugs — 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.
Comment #3 by greensunny12 — 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?
Comment #4 by robert.schadek — 2024-12-01T16:22:22Z