Sorting after map

spir denis.spir at gmail.com
Thu Oct 21 04:40:16 PDT 2010


On Wed, 20 Oct 2010 19:33:50 -0400
bearophile <bearophileHUGS at lycos.com> wrote:

> 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


Hello Bearophile,

Just a comment:
I think the issue you point at here and address at http://d.puremagic.com/issues/show_bug.cgi?id=5076 is a general one with "transformation" methods (or funcs). Transformations are routines which result is of the _same_ type as the object it applies on (receiver in case of method). I use here "function" 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 executions 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 should then be "sort"), or as a function creating a new sequence (name should then be "sorted"):
    s.sort();
or
    s2 = s1.sorted();
The issue is that both cases are useful. If sorting is an action, then to use it as an expression, one must first explicitely copy. If sorting is a function, 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 = s1.copy();
    s2.sort();
or
    s1 = 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 = 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 compiler would insert a copy operation:
    s2 = 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 performed as actions or functions. There is an obvious efficiency point, that copying is costly in terms of both time & space. On the other hand, copying is safer (analog to immutable, huge advantage for concurrency). Also, creating a new object sometimes simplifies algorithms of _global_ transformations (eg some kinds of sorting, precisely); and anyway on-place algorithms usually 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 as 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] = e) s.changeSlice(interval, subseq) (s[i,j] = ss)
* global transformations are implemented as functions; eg s.sorted()
* ambiguous cases are implemented in both forms; eg s.replace(e1,e2) vs s.replaced(e1,e2), or s1.extend(s2) vs s1.extended(s2) ("s1 ~= s2" vs "s1 ~ s2")

Hope this makes sense for you ;-)

Thanks for reading,
Denis
-- -- -- -- -- -- --
vit esse estrany ☣

spir.wikidot.com



More information about the Digitalmars-d-learn mailing list