www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 4264] New: Various std.algorithm.map problems

reply d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4264

           Summary: Various std.algorithm.map problems
           Product: D
           Version: unspecified
          Platform: x86
        OS/Version: Windows
            Status: NEW
          Severity: normal
          Priority: P2
         Component: Phobos
        AssignedTo: nobody puremagic.com
        ReportedBy: bearophile_hugs eml.cc



This D2 code works with DMD v2.046:

import std.stdio: writeln;
import std.algorithm: array, map;
void main() {
    int[] arr = [1, 2, 3];
    auto r1 = map!("a * a")(arr);
    writeln(array(r1));

    auto f = (int x){ return x * x; };
    auto r2 = map!(f)(arr);
    writeln(array(r2));
}

And prints:

1 4 9
1 4 9

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

But this program:

import std.stdio: writeln;
import std.algorithm: array, map;
void main() {
    int[] arr = [1, 2, 3];
    auto r3 = map!((x){ return x * x; })(arr);
    writeln(array(r3));
}


Generates the errors at compile-time:
...\src\phobos\std\algorithm.d(127): Error: forward reference to inferred
return type of function call __dgliteral1(0)
test.d(118): Error: template instance test.main.Map!(__dgliteral1,int[]) error
instantiating
test.d(5):        instantiated from here: map!(int[])
test.d(5): Error: template instance test.main.map!(__dgliteral1).map!(int[])
error instantiating

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

And this program:

import std.stdio: writeln;
import std.algorithm: array, map;
void main() {
    int[] arr = [1, 2, 3];
    auto r4 = map!((int x){ return x * x; })(arr);
    writeln(array(r4));
}


Generates the errors at compile-time:
test.d(5): Error: delegate std.algorithm.__dgliteral1 cannot access frame of
function __dgliteral1
test.d(5): Error: delegate std.algorithm.__dgliteral1 cannot access frame of
function __dgliteral1
test.d(5): Error: template instance test.main.map!(delegate int(int x)

{

return x * x;

}

) error instantiating

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

This D2 code works:

import std.stdio: writeln;
import std.algorithm: filter, array, map;
void main() {
    int[] arr = [1, 2, 3, 4, 5];
    auto r1 = array(filter!((x){ return x >= 3; })(arr));
    auto r2 = map!("a * a")(r1);
    writeln(array(r2));
}


And prints:

9 16 25

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

While this code:

import std.stdio: writeln;
import std.algorithm: filter, array, map;
void main() {
    int[] arr = [1, 2, 3, 4, 5];
    auto r1 = filter!((x){ return x >= 3; })(arr);
    auto r2 = map!("a * a")(r1);
    writeln(array(r2));
}


Generates the errors at compile-time:
...\src\phobos\std\algorithm.d(126): Error: struct
std.algorithm.Map!(result,Filter!(__dgliteral1,int[])).Map inner struct Filter
cannot be a field
...\src\phobos\std\algorithm.d(118): Error: template instance
std.algorithm.Map!(result,Filter!(__dgliteral1,int[])) error instantiating
test.d(6):        instantiated from here: map!(Filter!(__dgliteral1,int[]))
...\src\phobos\std\algorithm.d(6): Error: template instance
std.algorithm.map!("a * a").map!(Filter!(__dgliteral1,int[])) error
instantiating

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

This code:


import std.stdio: writeln;
import std.algorithm: array, map;
struct Range {
    int stop;
    int opApply(int delegate(ref int) dg) {
        int result;

        for (int i = 0; i < stop; i++) {
            result = dg(i);
            if (result)
                break;
        }

        return result;
    }
}
void main() {
    auto r = map!("a * a")(Range(6));
    writeln(array(r));
}



Generates the errors at compile-time:
...\src\phobos\std\algorithm.d(118): Error: template instance
Map!(result,Range) does not match template declaration Map(alias fun,Range) if
(isInputRange!(Range))
...\src\phobos\std\algorithm.d(118): Error: Map!(result,Range) is used as a
type
...\src\phobos\std\algorithm.d(120): Error: function expected before (), not
void of type void
...\src\phobos\std\algorithm.d(18): Error: template instance
std.algorithm.map!("a * a").map!(Range) error instantiating
test.d(18): Error: variable test.main.r voids have no value
test.d(18): Error: expression map((Range(6))) is void and has no value


A map() from a standard library must work with that Range() too because I have
structs/classes that define opApply and I want to use map and filter on them
too.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jun 02 2010
next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4264




Another case, I don't know the cause of the problem:


import std.algorithm, std.conv, std.range;
void main() {
    auto r1 = map!(to!(int, string))(iota(20));
}


dmd v2.047 prints:
...\dmd\src\phobos\std\algorithm.d(115): Error: function
std.conv.to!(int,string).to (string value) is not callable using argument types
(uint)
...\dmd\src\phobos\std\algorithm.d(115): Error: cannot implicitly convert
expression (0u) of type uint to string


If I replace int with uint:

import std.algorithm, std.conv, std.range;
void main() {
    auto r1 = map!(to!(uint, string))(iota(20));
}


...\dmd\src\phobos\std\algorithm.d(115): Error: function
std.conv.to!(uint,string).to (string value) is not callable using argument
types (uint)
...\dmd\src\phobos\std\algorithm.d(115): Error: cannot implicitly convert
expression (0u) of type uint to string

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jul 15 2010
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4264


yebblies <yebblies gmail.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |yebblies gmail.com



The problem with the last example seems to be that the template arguments to
'to' are in the wrong order.

Also, how can the opApply example work with lazy iteration?
As far as I know opApply does not provide any way to pause and resume
iteration.

It would be possible on the other hand to allow array to work on anything that
supplies opApply.

eg.

// s defines opApply
map!func(array(s)) // no lazy iteration
// but not
array(map!func(s))

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jul 16 2010
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4264





 The problem with the last example seems to be that the
 template arguments to 'to' are in the wrong order.


But this too doesn't work:

import std.algorithm, std.conv, std.range;
void main() {
    auto r1 = map!(to!(string, uint))(iota(20));
}


import std.algorithm, std.conv, std.range;
void main() {
    auto r1 = map!(to!(string, int))(iota(20));
}

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


 Also, how can the opApply example work with lazy iteration?
 As far as I know opApply does not provide any way to pause and resume
 iteration.


If you perform a map! on an iterable that has a length, then map! detects it at
compile-time and offers a length attribute, otherwise it's not offered.

So map! and other similar higher order functions can adapt and offer as much as
possible.

If the iterable given to map! has just an opApply, then map! can offer just an
opApply, for an iteration that can't be resumed.

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


 It would be possible on the other hand to allow array to work on
 anything that supplies opApply.


array() can work with anything that can be iterated by foreach.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jul 16 2010
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4264






 
 But this too doesn't work:
 
 import std.algorithm, std.conv, std.range;
 void main() {
     auto r1 = map!(to!(string, uint))(iota(20));
 }
 
 
 import std.algorithm, std.conv, std.range;
 void main() {
     auto r1 = map!(to!(string, int))(iota(20));
 }
 


You're right.  But this is not a problem with map, I think this is bug337.

void t1(U = int)(int a)
{
}
void t1(U = int)()
{
}
void t2(U = int, T = int)(int a)
{
}
void t2(U = int, T = int)()
{
}

void main() {
    t1!()(1); // works
    t1!()(); // works
    t1!(int)(1); // fails
    t1!(int)(); // fails
    t2!()(1); // works
    t2!()(); // works
    t2!(int)(1); // works
    t2!(int)(); // works
    t2!(int,int)(1); // fails
    t2!(int,int)(); // fails
}

It can probably be worked around by combining the radix and non-radix form of
to!(string,int).
Maybe a separate bug?




 If you perform a map! on an iterable that has a length, then map! detects it at
 compile-time and offers a length attribute, otherwise it's not offered.
 
 So map! and other similar higher order functions can adapt and offer as much as
 possible.
 
 If the iterable given to map! has just an opApply, then map! can offer just an
 opApply, for an iteration that can't be resumed.


Ok, I see your point, but if map is going to work with opApply it will no
longer be able to provide the standard range interface.
Either way this is an enhancement request and not a bug.

map!func(structWithOpApply) would also no longer work with most of
std.algorithm without extensive (and maybe impossible) modifications.




 array() can work with anything that can be iterated by foreach.


Agreed.
array() is special in that it always evaluates the entire range immediately.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jul 16 2010
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4264




yebblies:


 Ok, I see your point, but if map is going to work with opApply it will no
 longer be able to provide the standard range interface.


Yes, that's what I meant with giving as many capabilities as possible.



 Either way this is an enhancement request and not a bug.


Here there is a blurry line between bug and enhancement request. If map!
doesn't work with opApply I have to write new versions of map, filter, etc,
different from the standard ones. Missing one crucial functionality can be seen
as a kind of bug.



 map!func(structWithOpApply) would also no longer work with most of
 std.algorithm without extensive (and maybe impossible) modifications.


I am not asking for impossible changes. Just to make them work with what can
work. Othrwise I have to reinvent the wheel in my code.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jul 17 2010
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4264


David Simcha <dsimcha yahoo.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |dsimcha yahoo.com



Since everything you mention except the opApply issue is fixed either in 2.048
or in SVN, and the discussion has moved beyond Map to std.algorithm/std.range
in general, I've changed the name of this bug.

I've thought about supporting opApply in some std.range and std.algorithm
types.  I think it's useful and conceptually feasible (ignoring implementation
minutiae) for at least the following, and probably more:

std.algorithm.map
std.algorithm.filter
std.algorithm.uniq
std.algorithm.until
std.range.chain
std.range.retro (if your object defines opApplyReverse)
std.range.stride
std.range.cycle

It's definitely not feasible for anything that requires random access or
manipulating multiple ranges in lockstep.  I also don't see how to do it for
std.range.splitter

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Aug 21 2010
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4264


David Simcha <dsimcha yahoo.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Depends on|                            |2443, 4707
            Summary|Various std.algorithm.map   |Support opApply in
                   |problems                    |std.algorithm, std.range
                   |                            |where possible
           Severity|normal                      |enhancement



Please disregard my last post.  I hit commit by accident when I was half-done
typing it.

Since everything you mention except the opApply issue is fixed either in 2.048
or in SVN, and the discussion has moved beyond Map to std.algorithm/std.range
in general, I've changed the name of this bug and made it into an enhancement
request.

I've thought about supporting opApply in some std.range and std.algorithm
types.  I think it's useful and conceptually feasible (ignoring implementation
minutiae) for at least the following, and probably more:

std.algorithm.map
std.algorithm.filter
std.algorithm.uniq
std.algorithm.until
std.range.chain
std.range.retro (if your object defines opApplyReverse)
std.range.stride
std.range.cycle

It's definitely not feasible for anything that requires random access or
manipulating multiple ranges in lockstep, backtracking other than to the
beginning of the iteration, or doing stuff with ranges of ranges (Transversal,
etc).

Here are some of the bigger issues I see at the implementation level:

1.  Bugs 2443, 4707 make dealing correctly with ref in the opApply case near
impossible.  I've made them blockers for this issue.  Even if these get fixed,
supporting ref correctly would be non-trivial enough that I don't want to
implement everything w/o ref support and then have to go back later and add ref
support.

2.  If we start building higher order iterables out of opApply, things could
become slow as molasses through multiple layers of delegate calls.  I know LDC
can inline these at least in simple cases, but what about when you have N > 1
levels of them?  

3.  This is a big enough change to the way std.range/std.algorithm work that I
think it needs to be discussed first, rather than just being checked in one day
like a bug fix or minor enhancement.  Maybe you should bring it up on the
newsgroup.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Aug 21 2010
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4264




Thank you for your answer David Simcha.



 Since everything you mention except the opApply issue is fixed either
 in 2.048 or in SVN,


Yes, indeed now all tests but the one that uses map() work.

I agree with more or less all your points here. And I have no final answer for
your doubts. Here are few comments.



 Even if these get fixed, supporting ref correctly would be non-trivial
 enough that I don't want to implement everything w/o ref support and
 then have to go back later and add ref support.


I see. Working and fixing the std lib is a lot of work, so I suggest to keep
Phobos as short (as in number of lines) as possible, so when bugs gets fixed
you don't need a week to update it.

A possible good solution is to wait and not support opApply until those bugs
are fixed, to reduce your work. Sometimes the typical laziness of the
programmer is positive.



 2.  If we start building higher order iterables out of opApply, things could
 become slow as molasses through multiple layers of delegate calls.  I know LDC
 can inline these at least in simple cases, but what about when you have N > 1
 levels of them?


LDC can currently inline one level of opApply, but probably not much more than
that. Performance may indeed be reduced (even if we assume LLVM will get a bit
better with time).

On the other hand:
- D is not a functional language, D programmers don't write
map(filter(chain(map(... all the time. They usually use no more than one or two
level of lazy chaining.
- Several operations (like zip) are not possible with opApply, so this reduces
the places where they may be abused and where they can slow down code.
- In a normal program a good percentage of its code doesn't need to be
high-performance, for example you need to covert to numbers few (no more than
5) strings coming from args[] into numbers, and you use a
map!(to!(int))(args[1..$]). Many (but not all) of the usages of std.algorithm
are to shorten code, to make it more readable or less buggy, but they are not
used where max performance is necessary. This means that in practice a map()
performed on a struct that defines opApply is often not a performance problem.
(But programmers will need to be careful).



 3.  This is a big enough change to the way std.range/std.algorithm work that I
 think it needs to be discussed first, rather than just being checked in one day
 like a bug fix or minor enhancement.  Maybe you should bring it up on the
 newsgroup.


I will write a small post about this in the main D newsgroup soon then.

I don't have a final answer for your doubts. Generally I am not for pure
solutions, I think that ranges are good, but life is complex, and if you try to
cram everything into a single abstraction, you will have problems.

If std.algorithm doesn't support opApply at all, then opApply itself becomes
much less useful. In D1 I have seen that you can implement most of
std.algorithm using opApply only.

Supporting opApply in Phobos may be a lot of work, but it's work done once.
Then all D programs are able to use this hard work. This is why I like std libs
as flexible as possible, to make them support both fixed-sized arrays and
opApply, because this later makes user code simpler and more uniform, and this
Python shows that this usage uniformity is _very_ important to make the
language (its std lib) handy and quick to use.

Another thing about ranges is more general. opApply and ranges may be used for
the same purposes, like to create a lazy generator of items, or to offer a way
to scan the leaves of a tree through a simple foreach. But if you try to write
a tree visit using opApply or using the Range protocol you see that they are
not the same thing.

You may see other examples here:
http://code.activestate.com/recipes/221457/

For example (Python 2.x code):


def A006068():
    yield 0
    for x in A006068():
        if x & 1:
            yield 2*x+1
            yield 2*x
        else:
            if x:
                yield 2*x
            yield 2*x+1


It's not too much hard to implement this using opApply, the code is similar to
that Python code, just much more noisy. But if you use the Range protocol you
need to manage the state manually.

With this I am trying to say that the Range protocol doesn't replace opApply,
there are algorithms more naturally implemented with opApply. If you try to
cram everything into the Range idea, you risk losing something.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Aug 22 2010
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4264





 Maybe you should bring it up on the newsgroup.


http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=115950

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Aug 22 2010
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4264




*** Issue 5952 has been marked as a duplicate of this issue. ***

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
May 08 2011
prev sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4264




This code:

import std.stdio: writeln;
struct Iter2 {
    int stop, current;
     property int front() { return current; }
     property bool empty() { return current == stop; }
    void popFront() { current++; }
}
void main() {
    writeln(Iter2(10));
}


Shows that writeln supports the range protocol:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]


While this code:

import std.stdio: writeln;
struct Iter {
    int stop;
    int opApply(int delegate(ref int) dg) {
        int result;
        for (int i = 0; i < stop; i++) {
            result = dg(i);
            if (result) break;
        }
        return result;
    }
}
void main() {
    writeln(Iter(10));
}


Outputs this, showing writeln doesn't support opApply iterables:
Iter(10)

I'd like writeln() to show the items here too.

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