Possible bug in sort

[William James]

Code Select Expand


;; Function composition.
(define (f<g= f g)
  (expand (fn (a b) (f (g a) (g b))) 'f 'g))

((f<g= < last) '(a 2) '(b 3))
 ==> true

((f<g= < last) '(b 3) '(a 2))
 ==> nil

(set 'lst '((b 5) (a 2)))
(sort lst (f<g= < last))
 ==> ((a 2) (b 5))

(set 'lst '((a 2) (b 5)))
(sort lst (f<g= < last))
 ==> ((a 2) (b 5))


(set 'lst '((c 4) (b 5) (a 2)))
(sort lst (f<g= < last))

  [ crashes ]



[Lutz]

This happens when the sorting function gets generated at sort execution.



This is fixed for the next version here:

http://www.newlisp.org/downloads/development/inprogress/">http://www.newlisp.org/downloads/develo ... nprogress/">http://www.newlisp.org/downloads/development/inprogress/



as a workaround make the function first, then  pass it to 'sort':

Code Select Expand

(set 'fun (f<g= < last))
(sort lst fun)


[William James]

Thanks for the fast and helpful reply.



Function composition is a powerful and fun technique.

I'm hoping that

Code Select Expand

(sort (copy test-list) (f<g= < last))
won't be slower than

Code Select Expand

(sort (copy test-list) (fn (a b) (< (last a) (last b))))

[Lutz]

The (f<g= < last) expression is only evaluated once. So there will be a small difference on very short lists but no measurable difference on longer lists, when much more work is done sorting.

[William James]

I just tested the speed using Lutz's 'fun workaround.



The composed function is just as fast as the lambda (fn (a b) (< (last a) (last b))).



Perhaps I should explain the name f<g=.



If I remember correctly, J (descended from APL) gives names to its operators that compose functions like fork, atop, cap, hook.  It's not easy to remember exactly what they do.  So I'm trying to use a naming convention that shows how the operator works.  The function composition used above could be diagrammed this way:

Code Select Expand


    f
    /
   g   g
   |   |
   a   b

The name looks somewhat like the diagram rotated 90 degrees counterclockwise.



Another example:

Code Select Expand


    f
    /
   g   h
     /
     a

This could be used to calculate the average of a list of numbers.

Code Select Expand

((f<gh> / sum length) numbers)
It seems rather nice to program without explicit, named parameters.