www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Sorting after map

reply clueless <invalid email.address> writes:
Hi. I want to have a sorted result of map-function, that is (in pseudocode):

sorted(map!(fun)(arr))

How can I do that? I have tried something like:

auto s = map!(fun)(arr);
//sort(s);
//sort(s[]);
//sort(s.dup);
writeln(s);

but without success.

Thanks in advance.
Oct 19 2010
next sibling parent Lutger <lutger.blijdestijn gmail.com> writes:
clueless wrote:


 Hi. I want to have a sorted result of map-function, that is (in
 pseudocode):
 
 sorted(map!(fun)(arr))
 
 How can I do that? I have tried something like:
 
 auto s = map!(fun)(arr);
 //sort(s);
 //sort(s[]);
 //sort(s.dup);
 writeln(s);
 
 but without success.
 
 Thanks in advance.


Hi, I'm not sure if it is supposed to work or not. sort is inplace but map   
does not offer opIndexAssign which sort needs. You can circumvent it by 
creating an array of the map:

import std.array;

auto s = array(map!fun(arr));
sort(s);
Oct 20 2010
prev sibling next sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
clueless Wrote:

 ...


From your post I have added a comment here, comment 8:
http://d.puremagic.com/issues/show_bug.cgi?id=5076#c8

Bye,
bearophile
Oct 20 2010
parent spir <denis.spir gmail.com> writes:
On Wed, 20 Oct 2010 19:33:50 -0400
bearophile <bearophileHUGS lycos.com> wrote:


 clueless Wrote:

 ...


=20
 From your post I have added a comment here, comment 8:
 http://d.puremagic.com/issues/show_bug.cgi?id=3D5076#c8
=20
 Bye,
 bearophile



Hello Bearophile,

Just a comment:
I think the issue you point at here and address at http://d.puremagic.com/i=
ssues/show_bug.cgi?id=3D5076 is a general one with "transformation" methods=
 (or funcs). Transformations are routines which result is of the _same_ typ=
e as the object it applies on (receiver in case of method). I use here "fun=
ction" in the sense of Pascal, as opposed to "action":
* an action performs an effect (and should not return any result)
* a function returns a result (and should not perform any effect)
Actions do, functions make; action executions are statements, function exec=
utions are expressions.
Typically, a sorting method is a transformation: it operates on and results=
 in a sequence. Under the light of the above distinction, we could have it =
implemented either as action operating on-place on the sequence (name shoul=
d then be "sort"), or as a function creating a new sequence (name should th=
en be "sorted"):
    s.sort();
or
    s2 =3D s1.sorted();
The issue is that both cases are useful. If sorting is an action, then to u=
se it as an expression, one must first explicitely copy. If sorting is a fu=
nction, then to use it as a statement, one must reassign the result to the =
original variable name -- and a possibly useless copy has been created:
    s2 =3D s1.copy();
    s2.sort();
or
    s1 =3D s1.sort();

In a language where statements and expression are cleanly distinct (I guess=
 the is not true for D, as a legacy from C?), then one could have specially=
 marked "transformation" funcs or methods able to be used either as actions=
/statements or as functions/expression.
    s.sorting();                // 1
    s2 =3D s1.sorting();          // 2
    doSomething(s.sorting());   // 3
Basically, transformations would do the minimum, meaning no copy, which is =
allright for case 1. When used as expressions (cases 2 & 3), then the compi=
ler would insert a copy operation:
    s2 =3D s1.copy().sorting();
    doSomething(s.copy().sorting());
This indeed require having a default copy() method for all possible types (=
--> common issue when elements are referenced: should we deepcopy or not?).

Another approach is to wonder which kinds of transformations should be perf=
ormed as actions or functions. There is an obvious efficiency point, that c=
opying is costly in terms of both time & space. On the other hand, copying =
is safer (analog to immutable, huge advantage for concurrency). Also, creat=
ing a new object sometimes simplifies algorithms of _global_ transformation=
s (eg some kinds of sorting, precisely); and anyway on-place algorithms usu=
ally require copying most or all elements.
Can we draw a clear and sensible separation line? If yes, we could promote =
a convention stating which kinds of transformations should be implemented a=
s actions or functions. I am thinking at the following:
* partial transformations (operating on part of the object: element, slice)=
 are implemented as actions; eg s.changeElement(index, element) (s[i] =3D e=
) s.changeSlice(interval, subseq) (s[i,j] =3D ss)
* global transformations are implemented as functions; eg s.sorted()
* ambiguous cases are implemented in both forms; eg s.replace(e1,e2) vs s.r=
eplaced(e1,e2), or s1.extend(s2) vs s1.extended(s2) ("s1 ~=3D s2" vs "s1 ~ =
s2")

Hope this makes sense for you ;-)

Thanks for reading,
Denis
-- -- -- -- -- -- --
vit esse estrany =E2=98=A3

spir.wikidot.com
Oct 21 2010
prev sibling parent =?iso-8859-2?B?VG9tZWsgU293afFza2k=?= <just ask.me> writes:
Dnia 20-10-2010 o 08:26:12 clueless <invalid email.address> napisa=B3(a)=
:


 Hi. I want to have a sorted result of map-function, that is (in  =



 pseudocode):

 sorted(map!(fun)(arr))

 How can I do that? I have tried something like:

 auto s =3D map!(fun)(arr);
 //sort(s);
 //sort(s[]);
 //sort(s.dup);
 writeln(s);

 but without success.


Map is a range of computed values, so you can't assign elements to it. U=
se  =

an external index:

auto m =3D map!"a*a"([9,1,3,2]);
auto idx =3D new uint[](m.length);
makeIndex(m, idx);
foreach(i; idx)
     writeln(m[i]);

Prints:

1
4
9
81

One problem: makeIndex() doesn't return a SortedRange. Yet.
http://d.puremagic.com/issues/show_bug.cgi?id=3D5106
But you can still make a SortedRange of your own that accounts for  =

dereferencing (see bug description).

-- =

Tomek
Oct 23 2010