> > I'd like to propose a simple extension of the common > > bubble sort algorithm. Sometimes it is necessary to > > know how many exchanges took place during the sorting. > > There would be also another option to count the number of swappings. > If you look at the definition of the SortingPackage, it has two > parameters. One is the Aggregate object (List in your case) over which > the sorting is done and the first argument specifies the element type > of the entries.
Yes, of course. > Looking at the source code reveals that there is a swap! function that > is called each time two elements have to be exchanged. So another idea > to achieve counting, would be to create a "wrapper" domain around your > aggregate. Which again only works if we call swap for adjacent elements, no? Otherwise the function f() could be defined f(i,j) to resolve this. I must admit that I did not study this code in every detail. It seems to me that this is a similar idea, decorating a function with some kind of "callback hook" to get some information out of the deeper layers. Anyway, many thanks for this example too! > ---rhxBEGIN mya.spad > )abbrev domain MYA MyA > Z ==> Integer > ACat ==> Join(IndexedAggregate(Integer, S), finiteAggregate, > shallowlyMutable) > MyA(S: Type, A: ACat, f: () -> Void): ACat with > coerce: A -> % > coerce: % -> A > == A add > coerce(a: A): % == a pretend % > coerce(x: %): A == x pretend A > swap!(x: %, i: Z, j: Z): Void == (f(); swap!(x::A, i, j)) > ---rhxEND mya.spad > > Then in the interpreter say... > > (1) -> )compile mya.spad > > (1) -> Z := Integer; LZ := List Z > > (1) List(Integer) > Type: > Type > (2) -> l: LZ := [4,3,2,1,0] > > (2) [4,3,2,1,0] > Type: List(Integer) > (3) -> cc:Record(cnt: Z) := [0] > > (3) [cnt= 0] > Type: Record(cnt: Integer) > (4) -> countx(): Void == cc.cnt := cc.cnt+1 > Function declaration countx : () -> Void has been added to > workspace. > Type: Void > (5) -> MA := MyA(Z, LZ, countx) > Compiling function countx with type () -> Void > > (5) MyA(Integer,List(Integer),theMap(*0;countx;1;frame1)) > Type: Type > (6) -> bubbleSort!(l::MA)$SortPackage(Z, MA)::LZ > > (6) [0,1,2,3,4] > Type: List(Integer) > (7) -> cc > > (7) [cnt= 10] > Type: Record(cnt: Integer) > Of course, that's quite a lot of overhead for such a simple task, And this is exactly the point why I would like to add the new functions. Solving this task should be as easy as calling one simple function. > but I hope I could demonstrate that SPAD allows for more abstract ways of > programming. You did! > There is no need to implement every little function (and > thus perhaps partly copying code -- which makes maintenance a > nightmare). Well, but instead of a new function, we would add a new domain? I'm not really convinced by this point, because the code has to go somewhere. Either in one central place f.e. in SortPackage (no matter if its the function or domain) or where it is used (this would be the VA package, and maybe even duplicated in the Clifford package and so on) > SPAD is more about writing generic functions and then putting together > all the pieces in order to achieve what one wants. Yes, sure ... Do you think that the counting function(s) working on arbitrary Element and "List" types (as specified in the SortPackage) are not generic enough? If not, maybe we could extend the "callback-hook" trick and make it generic enough to go into the library? I would expect this to hit the performance of sorting. Probably we would need to do this as separate functions to avoid that drawback in the normal use case. For the moment I have what I need to continue with VA code. -- You received this message because you are subscribed to the Google Groups "FriCAS - computer algebra system" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/fricas-devel?hl=en.
