[Issue 4705] Redesign of std.algorithm.max()/min() + mins()/maxs()

[d-bugmail at puremagic.com]

https://d.puremagic.com/issues/show_bug.cgi?id=4705



--- Comment #18 from bearophile_hugs at eml.cc 2014-03-18 16:59:19 PDT ---
This Python program finds the number that has the largest minimum prime factor:


def decompose(n):
    result = []
    i = 2
    while n >= i * i:
        while n % i == 0:
            result.append(i)
            n //= i
        i += 1
    if n != 1:
        result.append(n)
    return result

def main():
    data = [    2 ** 59 - 1,      2 ** 59 - 1,
                2 ** 59 - 1,  112272537195293,
            115284584522153,  115280098190773,
            115797840077099,  112582718962171,
            112272537095293, 1099726829285419]

    print "N. with largest min factor: ",
    print max(data, key= lambda n: min(decompose(n)))

main()


Its output:

N. with largest min factor:  115797840077099



A similar D program:

ulong[] decompose(ulong n) pure nothrow {
    typeof(return) result;
    for (ulong i = 2; n >= i * i; i++)
        for (; n % i == 0; n /= i)
            result ~= i;
    if (n != 1)
        result ~= n;
    return result;
}

void main() {
    import std.stdio, std.algorithm, std.typecons;

    immutable ulong[] data = [
              2UL ^^ 59 - 1,         2UL ^^ 59 - 1,
              2UL ^^ 59 - 1,   112_272_537_195_293UL,
        115_284_584_522_153,   115_280_098_190_773,
        115_797_840_077_099,   112_582_718_962_171,
        112_272_537_095_293, 1_099_726_829_285_419];

    immutable res = data
                    .map!(n => cast(ulong[2])[n.decompose.reduce!min, n])
                    .reduce!max[1];
    writeln("N. with largest min factor: ", res);
}


But the optional key for the max() template allows to compute the result with:

immutable res = data.reduce!(max!(n => n.decompose.reduce!min)));

That is not too much worse than the Python version:

max(data, key= lambda n: min(decompose(n)))

The Python version is shorter because in Python max works on both items and
iterables:

>>> max(5)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'int' object is not iterable
>>> max(5, 3)
5
>>> max(5, 3, 6)
6
>>> max([5, 3, 6])
6


Currently the D max/min don't accept a single argument:

    max(5).writeln;
    max([5, 6]).writeln;

Gives:

test6.d(25,8): Error: template std.algorithm.max cannot deduce function from
argument types !()(int), candidates are:
...\dmd2\src\phobos\std\algorithm.d(7085,11):        std.algorithm.max(T...)(T
args) if (T.length >= 2)
test6.d(26,8): Error: template std.algorithm.max cannot deduce function from
argument types !()(int[]), candidates are:
...\dmd2\src\phobos\std\algorithm.d(7085,11):        std.algorithm.max(T...)(T
args) if (T.length >= 2)

So max/min could be extended to see a single argument as an iterable:

someRange.max === someRange.reduce!max
someRange.min === someRange.reduce!min

With such improvement the D code becomes similar to the Python version and very
readable:

immutable res = data.max!(n => n.decompose.min);

This is how I'd like max/min of Phobos to behave.

-- 
Configure issuemail: https://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------