[Issue 4705] Redesign of std.algorithm.max()/min() + mins()/maxs()
https://d.puremagic.com/issues/show_bug.cgi?id=4705
--- Comment #18 from bearophile_h...@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: ---
[Issue 4705] Redesign of std.algorithm.max()/min() + mins()/maxs()
http://d.puremagic.com/issues/show_bug.cgi?id=4705
--- Comment #17 from bearophile_h...@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: ---
[Issue 4705] Redesign of std.algorithm.max()/min() + mins()/maxs()
http://d.puremagic.com/issues/show_bug.cgi?id=4705
--- Comment #16 from bearophile_h...@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: ---
[Issue 4705] Redesign of std.algorithm.max()/min() + mins()/maxs()
http://d.puremagic.com/issues/show_bug.cgi?id=4705 --- Comment #15 from bearophile_h...@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: ---
[Issue 4705] Redesign of std.algorithm.max()/min() + mins()/maxs()
http://d.puremagic.com/issues/show_bug.cgi?id=4705
--- Comment #14 from bearophile_h...@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: ---
[Issue 4705] Redesign of std.algorithm.max()/min() + mins()/maxs()
http://d.puremagic.com/issues/show_bug.cgi?id=4705 --- Comment #13 from bearophile_h...@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.Darticle_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: ---
[Issue 4705] Redesign of std.algorithm.max()/min() + mins()/maxs()
http://d.puremagic.com/issues/show_bug.cgi?id=4705
--- Comment #9 from bearophile_h...@eml.cc 2011-05-23 05:12:44 PDT ---
Another example, compared to using minPos():
import std.stdio, std.algorithm, std.array;
void main() {
string[] data = [red, hello, yes, no, roger, bud];
// works in DMD 2.053
string r1 = minPos!q{ walkLength(a) walkLength(b) }(data).front();
writeln(r1);
// proposed
string r2 = max!q{ walkLength(a) }(items);
writeln(r2);
}
The second version is shorter and more readable, and just like schwartzSort()
the modified max() is more efficient than using minPos when the mapping
function becomes costly to compute.
--
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
--- You are receiving this mail because: ---
[Issue 4705] Redesign of std.algorithm.max()/min() + mins()/maxs()
http://d.puremagic.com/issues/show_bug.cgi?id=4705
--- Comment #10 from bearophile_h...@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: ---
[Issue 4705] Redesign of std.algorithm.max()/min() + mins()/maxs()
http://d.puremagic.com/issues/show_bug.cgi?id=4705 --- Comment #11 from bearophile_h...@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: ---
[Issue 4705] Redesign of std.algorithm.max()/min() + mins()/maxs()
http://d.puremagic.com/issues/show_bug.cgi?id=4705 --- Comment #8 from bearophile_h...@eml.cc 2011-03-25 10:35:06 PDT --- A max/min with a comparing function is present in the Haskel standard library too, named maximumBy: import Data.List import Data.Ord longestWord words = maximumBy (comparing length) words listx = [x, yyy, zz] main = print $ longestWord listx Prints: yyy -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 4705] Redesign of std.algorithm.max()/min() + mins()/maxs()
http://d.puremagic.com/issues/show_bug.cgi?id=4705
--- Comment #7 from bearophile_h...@eml.cc 2011-03-24 15:07:40 PDT ---
The examples hopefully show how much useful are the new max/min.
This is part of the pivoting part of a LU decomposition algorithm:
T imax = mat[j][j];
int nrow = j;
foreach (i; j .. N) {
if (mat[i][j] imax) {
imax = mat[i][j];
nrow = i;
}
}
With the improved max() it becomes:
int nrow = max!((int i){ return mat[i][j]; })(iota(j, N));
That is similar to this Python code:
nrow = max(xrange(j, N), key=lambda i: mat[i][j])
Python designers have recognized this is a common pattern in code.
--
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
--- You are receiving this mail because: ---
[Issue 4705] Redesign of std.algorithm.max()/min() + mins()/maxs()
http://d.puremagic.com/issues/show_bug.cgi?id=4705
--- Comment #6 from bearophile_h...@eml.cc 2011-02-13 05:51:55 PST ---
Two more usage examples of the improved max. This program finds the longest
common subsequence with a recursive algorithm:
import std.stdio;
T[] lcs(T)(T[] a, T[] b) {
T[] longest(T)(T[] s, T[] t) {
return s.length t.length ? s : t;
}
if (!a.length || !b.length)
return null;
if (a[0] == b[0])
return a[0] ~ lcs(a[1..$], b[1..$]);
return longest(lcs(a, b[1..$]), lcs(a[1..$], b));
}
void main() {
writeln(lcs(thisisatest, testing123testing));
}
With a key-mapping max() you are able to remove the inner function and simplify
the code (untested):
import std.stdio;
T[] lcs(T)(T[] a, T[] b) {
if (!a.length || !b.length)
return null;
if (a[0] == b[0])
return a[0] ~ lcs(a[1..$], b[1..$]);
return max!q{a.length}([lcs(a, b[1..$]), lcs(a[1..$], b)]);
}
void main() {
writeln(lcs(thisisatest, testing123testing));
}
--
This program shows the most common anagrams from a dictionary file of different
words:
import std.stdio, std.algorithm;
void main() {
string[][string] anags;
foreach (w; File(unixdict.txt).byLine())
anags[w.sort.idup] ~= w.idup;
int m = reduce!max(map!q{a.length}(anags.values));
writeln(filter!((wl){ return wl.length == m; })(anags.values));
}
A key-mapping max() makes the code shorter and more readable (untested):
import std.stdio, std.algorithm;
void main() {
string[][string] anags;
foreach (w; File(unixdict.txt).byLine())
anags[w.sort.idup] ~= w.idup;
int m = max!q{a.length}(anags.values);
writeln(filter!((wl){ return wl.length == m; })(anags.values));
}
maxs() simplifies the code even more (untested):
import std.stdio, std.algorithm;
void main() {
string[][string] anags;
foreach (w; File(unixdict.txt).byLine())
anags[w.sort.idup] ~= w.idup;
writeln(maxs!q{a.length}(anags.values));
}
--
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
--- You are receiving this mail because: ---
[Issue 4705] Redesign of std.algorithm.max()/min() + mins()/maxs()
http://d.puremagic.com/issues/show_bug.cgi?id=4705
--- Comment #5 from bearophile_h...@eml.cc 2011-01-01 06:33:02 PST ---
Another example to show why a better max() is useful. The task is ot show how
the number less than 1000 which has the longest hailstone sequence. For the
hailstone see:
http://en.wikipedia.org/wiki/Collatz_conjecture
The code, DMD 2.051:
import std.stdio, std.algorithm, std.range, std.typecons;
auto hailstone(int n) {
auto result = [n];
while (n != 1) {
n = n 1 ? n*3 + 1 : n/2;
result ~= n;
}
return result;
}
void main() {
auto r = reduce!max(map!((i){return tuple(hailstone(i).length,
i);})(iota(1, 1000)))[1];
writeln(r);
}
With a max that supports a key function and iterables the line of code in the
main() becomes just:
auto r = max!hailstone(iota(1, 1000));
With the enhancement request 5395 it becomes even more readable:
auto r = max!hailstone(1 .. 1000);
--
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
--- You are receiving this mail because: ---
[Issue 4705] Redesign of std.algorithm.max()/min() + mins()/maxs()
http://d.puremagic.com/issues/show_bug.cgi?id=4705 Denis Derman denis.s...@gmail.com changed: What|Removed |Added CC||denis.s...@gmail.com --- Comment #2 from Denis Derman denis.s...@gmail.com 2010-12-24 11:12:14 PST --- (In reply to comment #0) I also suggest to create two new functions, that I have just called maxs() and mins() similar to max and min, that find all the max or min items of a given collection. They don't need the case with two or three items: maxs(collection) maxs!(callable)(collection) mins(collection) mins!(callable)(collection) Why I understand the utility of maxs/mins, I wonder about them in std lib. Aren't they niche domain tools? Also, I wonder about maxs(collection) without any trnasform func: if you don't map, then there is logically a single max value (even if can occur several times in collection). maxS/minS seems useful only in presence of a transform func on which results comparison is done: the compared value is (in your case string len) unique, but there may be several original values in coll that map to it. To say it deifferently, in your case mins(collection) would return possibly multiple specimens of the same string. And mins(lenghts) would return [5,5]. Unless I misunderstand your point. Denis -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 4705] Redesign of std.algorithm.max()/min() + mins()/maxs()
http://d.puremagic.com/issues/show_bug.cgi?id=4705 --- Comment #3 from Denis Derman denis.s...@gmail.com 2010-12-24 11:17:33 PST --- Aside the posted comment, I rather support this proposal. Have you ever called an external func for min(a,b) or sum(a,b)? (lol ;-) So, according to me, what we need is a simple and efficient implementation of min/max (and sum, etc...) for what is the common need: over a collection. An variant with transform func would also be nice, indeed. Denis -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 4705] Redesign of std.algorithm.max()/min() + mins()/maxs()
http://d.puremagic.com/issues/show_bug.cgi?id=4705 --- Comment #4 from bearophile_h...@eml.cc 2010-12-24 22:53:27 PST --- (In reply to comment #2) Aren't they niche domain tools? The opposite is true. Functions and HOFs like max, min, sum, maxs, map, filter, reduce, and so on are basic building blocks that are useful to build most other programs. So their place is in the standard library, or sometimes even in the language itself. Also, I wonder about maxs(collection) without any trnasform func: if you don't map, then there is logically a single max value (even if can occur several times in collection). maxS/minS seems useful only in presence of a transform func on which results comparison is done: the compared value is (in your case string len) unique, but there may be several original values in coll that map to it. To say it deifferently, in your case mins(collection) would return possibly multiple specimens of the same string. And mins(lenghts) would return [5,5]. Unless I misunderstand your point. maxs with no transform function is useful even with integers, to count how many equal max values are present: maxs([5, 1, 5, 3]).length == 2 And if your collection contains objects, they may compare as equal despite being distinct. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
