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



--- Comment #10 from bearophile_hugs@eml.cc 2011-05-23 16:12:53 PDT ---
The code that uses minPos() also leads to a possible bug (a real bug I have
found in my code), shown here:


import std.stdio, std.algorithm, std.math, std.range, std.random;
int gen(int x) { return uniform(-100, 100); }
void main() {
    auto data = map!gen(iota(10));
    writeln(data);
    writeln(data);
    int result = minPos!((a, b){ return abs(a) < abs(b); })(data).front();
    writeln(result);
}


The output shows that gen is recomputed every time data is used, so
abs(a)<abs(b) gives bogus results:
[-87, -1, 86, -93, -89, 16, 17, -91, 55, 88]
[-36, 91, 38, 6, 23, 85, 60, -25, -48, -100]
-97

(Maybe I'd like an annotation to tell the compiler that "data" is an an Input
Range, unlike iota() that map is iterating on.)


To avoid that bug you have to turn data into an array:

import std.stdio, std.algorithm, std.math, std.range, std.random;
int gen(int x) { return uniform(-100, 100); }
void main() {
    auto data = array(map!gen(iota(10)));
    writeln(data);
    writeln(data);
    int result = minPos!((a, b){ return abs(a) < abs(b); })(data).front();
    writeln(result);
}


Now abs(a)<abs(b) gets computed on something that's not changing under the
carpet, and there is no bug:
[-41, -36, -15, -35, 91, 31, -5, -67, -91, -65]
[-41, -36, -15, -35, 91, 31, -5, -67, -91, -65]
-5



In code like this there is no need to turn data into an array, the result is correct even keeping "data" lazy because items of data are accessed only once to compute abs(a):


import std.stdio, std.algorithm, std.math, std.range, std.random;
int gen(int x) { return uniform(-100, 100); }
void main() {
    auto data = map!gen(iota(10));
    int result = min!q{ abs(a) }(data);
    writeln(result);
}

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

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



--- Comment #11 from bearophile_hugs@eml.cc 2011-05-23 16:16:25 PDT ---
(In reply to comment #10)

> (Maybe I'd like an annotation to tell the compiler that "data" is an an Input
> Range, unlike iota() that map is iterating on.)

This bug doesn't happen if the mapping function of map() is pure.

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

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



--- Comment #12 from bearophile_hugs@eml.cc 2011-09-14 15:51:52 PDT ---
Another use case. Given this struct:

struct Foo {
    double x;
    int[100] a;
}


This D code finds the struct with the smallest x and assigns it to good[index]:

size_t idmin = 0;
foreach (size_t i; 1 .. N)
    if (foos[i].x < foos[idmin].x)
        idmin = i;
good[index] = foos[idmin];


With the improvement I have proposed you are allowed to replace it with a higher level code, that expresses the  idea clearly, is less bug-prone, and reqires one 1 instead of 5:


good[index] = min!q{ a.x }(foos);

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

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



--- Comment #13 from bearophile_hugs@eml.cc 2011-10-12 15:55:39 PDT ---
Part of A comment by Andrei Alexandrescu: http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=144562

> Second, you propose
> 
> mins(collection)
> mins!(callable)(collection)
> maxs(collection)
> maxs!(callable)(collection)
> 
> that return all elements. I'm not sure how you plan to return - create a new array, or iterate a la filter? The latter is interesting, but for either variant is quite difficult to find use examples that are frequent enough to make min followed by filter too verbose.

It's not a problem of verbosity. If you have to find all the min or max items
of a lazy iterable, and you want to use min followed by filter, then you have
to scan the sequence two times. This is a problem because:
- Two scans are a waste of time if the sequence is a large array, because of
CPU cache issues.
- It becomes worse if the sequence is a lazy range, because you have to compute
every item two times. This is sometimes not acceptable. I have found situations
like this, where the range was coming from a map with a costly mapping
function.

So maxs/mins is a common enough pattern (I have just hit another use case), it's not trivial to implement manually (because you have to efficiently manage the cache of the max/min items found so far), and I think it can't be trivially and efficiently implemented using existing std.range/std.algorithm tools. This makes it a worth candidate for a specilized higher order function.

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

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



--- Comment #14 from bearophile_hugs@eml.cc 2012-01-29 12:53:57 PST ---
Another example of the usefulness of maxs/mins:

http://rosettacode.org/wiki/Ordered_words#D
> Define an ordered word as a word in which the letters of the word appear in alphabetic order. Examples include 'abbey' and 'dirt'. The task is to find and display all the ordered words in this dictionary that have the longest word length.


A D2 solution:


import std.stdio, std.algorithm, std.range, std.file;
void main() {
    auto ws = filter!isSorted(readText("unixdict.txt").split());
    immutable maxl = reduce!max(map!walkLength(ws));
    writeln(filter!(w => w.length == maxl)(ws));
}


With a maxs the code becomes shorter, simpler, more readable and it needs to scan the items only once, instead of two as the reduce-max + filter. When the items are many scanning them only once speeds up the code, and it's usable with InputRanges too that allow only a single scan of the items:


import std.stdio, std.algorithm, std.range, std.file;
void main() {
    auto ws = filter!sorted?(readText("unixdict.txt").split());
    writeln(maxs!walkLength(ws));
}


Another hint of the usefulness of the maxs (and mins) function comes from looking at the Haskell solution, that contains the keepLongest function that essentially is a maxs!length (but it returns the items in reverse order, for efficiency because it uses a list): http://rosettacode.org/wiki/Ordered_words#Haskell


isOrdered wws@(_ : ws) = and $ zipWith (<=) wws ws

keepLongest _ acc [] = acc
keepLongest max acc (w : ws) =
  let len = length w in
  case compare len max of
    LT -> keepLongest max acc ws
    EQ -> keepLongest max (w : acc) ws
    GT -> keepLongest len [w] ws

longestOrderedWords = reverse . keepLongest 0 [] . filter isOrdered

main = do
  str <- getContents
  let ws = longestOrderedWords $ words str
  mapM_ putStrLn ws

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

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



--- Comment #15 from bearophile_hugs@eml.cc 2013-03-20 06:16:14 PDT ---
In Haskell the reduce!min and reduce!max are named "minimum" and "maximum".

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

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



--- Comment #16 from bearophile_hugs@eml.cc 2013-04-14 14:23:35 PDT ---
I still think mins()/maxs() are useful. But years after the original proposal
an API change in max/min is now problematic (unless you want to introduce
maximum/minimum functions). So I propose a small change in my original request.

Now I suggest to keep the max/min functions diadic as they are now, and add the optional 'key' function. This is a backwards-compatible change in max/min.

This is the updated example code presented here: http://d.puremagic.com/issues/show_bug.cgi?id=4705#c5


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

auto hailstone(int n) pure nothrow {
    auto result = [n];
    while (n != 1) {
        n = (n & 1) ? (n * 3 + 1) : (n / 2);
        result ~= n;
    }
    return result;
}

void main() {
    iota(1, 1000)
    .map!(i => tuple(i.hailstone.length, i))
    .reduce!max[1]
    .writeln; // 871
}


With the original proposal the main() becomes (with the maximum the code is
very similar):

void main() {
    iota(1, 1000)
    max!(i => i.hailstone.length)
    .writeln;
}



With the reduced proposal the main() becomes:

void main() {
    iota(1, 1000)
    reduce!(max!(i => i.hailstone.length))
    .writeln;
}

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

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



--- Comment #17 from bearophile_hugs@eml.cc 2013-09-03 09:45:18 PDT ---
In dmd 2.064alpha you can't use minPos on a byKey range:

import std.algorithm: minPos;
void main() {
    int[int] aa = [1: 2];
    int m1 = aa.byKey.minPos!((a, b) => a > b)[0]; // errors
    int m2 = aa.keys.minPos!((a, b) => a > b)[0];
}



test.d(4): Error: template std.algorithm.minPos does not match any function
template declaration. Candidates are:
...\dmd2\src\phobos\std\algorithm.d(6436):        std.algorithm.minPos(alias
pred = "a < b", Range)(Range range) if (isForwardRange!Range &&
!isInfinite!Range && is(typeof(binaryFun!pred(range.front, range.front))))
test.d(4): Error: template std.algorithm.minPos(alias pred = "a < b",
Range)(Range range) if (isForwardRange!Range && !isInfinite!Range &&
is(typeof(binaryFun!pred(range.front, range.front)))) cannot deduce template
function from argument types !(__lambda3)(Result)
test.d(4): Error: template instance minPos!(__lambda3) errors instantiating
template

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