map, filter, zip, not with functional arrays/associative arrays

[dlangBugzillaToGithub]

bearophile_hugs reported this on 2012-09-23T15:52:06Z

Transfered from https://issues.dlang.org/show_bug.cgi?id=8715

CC List

• timon.gehr

Description

I suggest to add the higher order function "zipWith" to Phobos, similar to the Haskell function present in the Prelude:

Prelude> zipWith (+) [1,2,3] [10,20,30]
[11,22,33]
Prelude> data Vec = Vec Int Int deriving (Show)
Prelude> zipWith Vec [1,2,3] [10,20,30]
[Vec 1 10,Vec 2 20,Vec 3 30]

As you see it's handy in two use cases: the first case is a zip that applies a given function to the pairs. The other important use case is when you don't need zip() to build an iterable of generic tuples, but you want it to build a range of a specific given struct/tuple.

The Haskell code in D using the current Phobos:

import std.algorithm, std.range;
void main() {
    auto r1 = zip([1,2,3], [10,20,30]).map!(p => p[0] + p[1])();
    static struct Vec { int x, y; }
    auto r2 = zip([1,2,3], [10,20,30]).map!(p => Vec(p.tupleof))();
}


With a zipWith() the code becomes simpler and more readable:

import std.range;
void main() {
    auto r1 = zipWith!q{a + b}([1,2,3], [10,20,30]);
    static struct Vec { int x, y; }
    auto r2 = zipWith!Vec([1,2,3], [10,20,30]);
}

[dlangBugzillaToGithub]

timon.gehr commented on 2012-09-23T16:34:39Z

I suggest to add anything that is not yet there and applicable to ranges listed
here up to and excluding 'special lists':

http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data-List.html

[dlangBugzillaToGithub]

bearophile_hugs commented on 2012-09-23T17:48:57Z

A simpler alternative idea is to just extend zip() to optionally accept a function/constructor (it's also good for map() to accept a struct name):

import std.range;
void main() {
    auto r1 = zip!q{a + b}([1,2,3], [10,20,30]);
    static struct Vec { int x, y; }
    auto r2 = zip!Vec([1,2,3], [10,20,30]);
}

[dlangBugzillaToGithub]

timon.gehr commented on 2012-09-23T18:04:46Z

(In reply to comment #2)
> A simpler alternative idea is to just extend zip() to optionally accept a
> function/constructor (it's also good for map() to accept a struct name):
> 
> import std.range;
> void main() {
>     auto r1 = zip!q{a + b}([1,2,3], [10,20,30]);
>     static struct Vec { int x, y; }
>     auto r2 = zip!Vec([1,2,3], [10,20,30]);
> }

I prefer this. 'zip' would become 'zipWith' with a default template argument of
'tuple'. (map already accepts a struct with an appropriate constructor as that
fits the 'callable' definition.)

[dlangBugzillaToGithub]

bearophile_hugs commented on 2012-10-12T16:22:58Z

(In reply to comment #3)

> (map already accepts a struct with an appropriate constructor as that
> fits the 'callable' definition.)

Right. But this shows a different limit. I think code like this is accepted in Clojure:


import std.algorithm: map;
void main() {
    auto keys = [1, 2, 1, 1, 1];
    auto a = [0, 10, 20];
    auto r1 = map!(k => a[k])(keys); // OK
    auto r2 = map!a(keys);           // Error
    auto aa = [1: 10, 2: 20];
    auto r3 = map!(k => aa[k])(keys); // OK
    auto r4 = map!aa(keys);           // Error
}

[dlangBugzillaToGithub]

bearophile_hugs commented on 2012-12-13T02:53:58Z

Another example:

import std.stdio: writeln;
import std.algorithm: map, filter;
void main() {
    int[] data = [0, 1, 2, 3];
    bool[] mask = [true, false, true, false];
    int[int] conv = [0:10, 1:20, 2:30, 3:40];
    auto r1 = data
              .filter!(i => mask[i])()
              .map!(i => conv[i])();
    writeln(r1); // Prints: [10, 30]
}


This is nicer:

import std.stdio: writeln;
import std.algorithm: map, filter;
void main() {
    int[] data = [0, 1, 2, 3];
    bool[] mask = [true, false, true, false];
    int[int] conv = [0:10, 1:20, 2:30, 3:40];
    auto r2 = data.filter!mask().map!conv();
    writeln(r2);
}

[dlangBugzillaToGithub]

bearophile_hugs commented on 2012-12-30T18:14:53Z

Two more examples:


import std.algorithm: filter;
import std.functional: not;
void main() {
    bool[] bad = [true, true, false, false, true, false];
    auto items = [0, 1, 2, 3, 4, 5];
    auto r1 = items.filter!bad();
    auto r2 = items.filter!(not!bad)();
}


...\dmd2\src\phobos\std\algorithm.d(1226): Error: function expected before (), not bad of type bool[]
...\dmd2\src\phobos\std\algorithm.d(1248): Error: function expected before (), not bad of type bool[]
...\dmd2\src\phobos\std\algorithm.d(1214): Error: template instance test.main.FilterResult!(bad, int[]) error instantiating
test.d(6):        instantiated from here: filter!(int[])
test.d(6): Error: template instance test.main.filter!(bad).filter!(int[]) error instantiating
...\dmd2\src\phobos\std\algorithm.d(1226): Error: template test.main.not!(bad).not does not match any function template declaration. Candidates are:
...\dmd2\src\phobos\std\functional.d(184):        test.main.not!(bad).not(T...)(T args) if (is(typeof(!unaryFun!(pred)(args))) || is(typeof(!binaryFun!(pred)(args))))
...\dmd2\src\phobos\std\algorithm.d(1226): Error: template test.main.not!(bad).not(T...)(T args) if (is(typeof(!unaryFun!(pred)(args))) || is(typeof(!binaryFun!(pred)(args)))) cannot deduce template function from argument types !()(int)
...\dmd2\src\phobos\std\algorithm.d(1248): Error: template test.main.not!(bad).not does not match any function template declaration. Candidates are:
...\dmd2\src\phobos\std\functional.d(184):        test.main.not!(bad).not(T...)(T args) if (is(typeof(!unaryFun!(pred)(args))) || is(typeof(!binaryFun!(pred)(args))))
...\dmd2\src\phobos\std\algorithm.d(1248): Error: template test.main.not!(bad).not(T...)(T args) if (is(typeof(!unaryFun!(pred)(args))) || is(typeof(!binaryFun!(pred)(args)))) cannot deduce template function from argument types !()(int)
...\dmd2\src\phobos\std\algorithm.d(1214): Error: template instance std.algorithm.FilterResult!(not, int[]) error instantiating
test.d(7):        instantiated from here: filter!(int[])
test.d(7): Error: template instance std.algorithm.filter!(not).filter!(int[]) error instantiating

- - - - - - - - - - - - - - - -

import std.algorithm: filter;
struct IsOdd {
    static bool opCall(in int n) {
        return n % 2 == 1;
    }
}
void main() {
    auto items = [0, 1, 2, 3, 4, 5, 6, 7, 8];
    auto r1 = items.filter!(i => IsOdd(i))(); // OK
    auto r2 = items.filter!IsOdd(); // Error.
}


test.d(10): Error: template instance filter!(IsOdd) filter!(IsOdd) does not match template declaration filter(alias pred) if (is(typeof(unaryFun!(pred))))