Possible bug in sort

[William James]

Code: Select all

;; 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/develo ... nprogress/

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

Code: Select all

(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 all

(sort (copy test-list) (f<g= < last))

won't be slower than

Code: Select all

(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 all

     f
    / \
   g   g
   |   |
   a   b

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

Another example:

Code: Select all

     f
    / \
   g   h
    \ / 
     a

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

Code: Select all

((f<gh> / sum length) numbers)

It seems rather nice to program without explicit, named parameters.