[Issue 13473] New: std.algorithm.expand
via Digitalmars-d-bugs
digitalmars-d-bugs at puremagic.com
Sun Sep 14 05:20:45 PDT 2014
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 at puremagic.com
Reporter: bearophile_hugs at 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;
}
--
More information about the Digitalmars-d-bugs
mailing list