Prev: The Erik Naggum cll archive
Next: a defense of ad hoc software development
From: Pillsy on 13 Jan 2010 12:04
On Jan 13, 10:57 am, Cecil Westerhof <Ce...(a)decebal.nl> wrote:
> I want to sort a property list on the property date.
> I have the function:

>     (defun dates-in-list< (first-list second-list)
>       (let ((first-date  (getf first-list  :date))
>             (second-date (getf second-list :date)))
>         (string< first-date second-date)))

> And I sort the list with:
>     (sort *measurements* 'dates-in-lists<)

> But I do not want to have the list sorted incrementing, but
> decrementing. Do I understand correctly that I need a function
> dates-in-lists>? Aka: it is not possible to negate.

It may be possible to negate. However, there's another way of doing
this sort of thing that I happen to like better. You may like it
better too.

The SORT function, in addition to the mandatory arguments for the
sequence and comparison predicate, takes the keyword argument :KEY,
specifying a function to be applied to each element before they're
compared using the comparison predicate. So you could do it like this:

(defun get-date (list)
(getf list :date))

;; stuff

(sort *measurements* #'string> :key #'get-date)

Another alternative is to define a full set of predicates for ordering
the dates in lists. I usually find that if I want one of the
predicates, I'll want all of them before long.

(defun get-date (list)
(getf list :date))

(defmacro define-date-comparision (name pred)
`(defun ,name (first-list second-list)
(,pred (get-date first-list) (get-date second-list))))

(define-date-comparison dates-in-list< string<)
(define-date-comparison dates-in-list<= string<=)
(define-date-comparison dates-in-list= string=)
(define-dare-comparison dates-in-list>= string>=)
(define-date-comparison dates-in-list> string>)

(define-date-comparison dates-in-list/= string/=)

;; stuff

(sort *measurements* #'dates-in-list>)

I wrote a simple macro to get the job done; fancier and more compact
ones are possible if you're into that sort of thing.

Lastly, be sure you use the return value of SORT! It's a common
mistake to assume that because it's a destructive operation, its side-
effects will mean that *MEASUREMENTS* will be bound to a sorted list,
but that isn't the case.

HTH,
Pillsy
From: Pascal J. Bourguignon on 13 Jan 2010 13:15
Cecil Westerhof <Cecil(a)decebal.nl> writes:

> I want to sort a property list on the property date.
> I have the function:
> (defun dates-in-list< (first-list second-list)
> (let ((first-date (getf first-list :date))
> (second-date (getf second-list :date)))
> (string< first-date second-date)))
>
> And I sort the list with:
> (sort *measurements* 'dates-in-lists<)
>
> But I do not want to have the list sorted incrementing, but
> decrementing. Do I understand correctly that I need a function
> dates-in-lists>? Aka: it is not possible to negate.

You do not want to complement, but to exchange the arguments.
(complement 'dates-in-lists<) is dates-in-lists>= which is wrong for
SORT (of course, since you added later that your dates were uniques,
it would work, but you should better take good habits soon).

Anyways, define what you mean:

(defun exchange-arguments (function)
(lambda (a b) (funcall function b a)))

(sort *measurements* (exchange-arguments (function dates-in-lists<)) )

--
__Pascal Bourguignon__ http://www.informatimago.com/
From: Kaz Kylheku on 13 Jan 2010 17:43
On 2010-01-13, Cecil Westerhof <Cecil(a)decebal.nl> wrote:
> I want to sort a property list on the property date.
> I have the function:
> (defun dates-in-list< (first-list second-list)
> (let ((first-date (getf first-list :date))
> (second-date (getf second-list :date)))
> (string< first-date second-date)))
>
> And I sort the list with:
> (sort *measurements* 'dates-in-lists<)

You cannot sort a list this way. The sort function is functional;
it returns the sorted list, so you must capture the return value.
Moreover, the function is not /purely/ functional: it destroys
the old list.

(setf *measurements* (sort *measurements* 'dates-in-lists<))

By not assigning the return value back to the variable, you not only
fail to get the sorted list, but you leave a destroyed one there.

Sort /may/ work in such a way that this will appear to work.

Or it could appear that way by coincidence in some cases. For instance if sort
sorts a list by rearranging the cons cells, then if by chance the same cons
cell stays at the front of the list, then the sorted list is EQ to the
destroyed one.

Some sort implementations work by moving around the contents of the CAR
fields of the conses, but preserve the cons structure as-is. This allows
you to simply (sort variable ...) without assigning; but such code is not
portable. Moreover, that sort implementation is nevertheless destructive,
so all the other caveats apply.

> But I do not want to have the list sorted incrementing, but
> decrementing. Do I understand correctly that I need a function
> dates-in-lists>? Aka: it is not possible to negate.

Of course it is. One way is to use a lambda function which
calls the original function with left and right reversed:

(setf *measurements*
(sort *measurements* (lambda (left right)
(dates-in-lists< right left))))

On a tangential topic, note that in addition to a sequence and a predicate
function, SORT takes a keyword argument called key. You can use key to pass in
a function which knows how to extract the relevant key from each item.

We can take use this to tell sort that each item is a plist from which a :date
property is to be extracted and used as the sort key.

Then these keys are compared with the ``date-less'' function; this compare
function just deals with dates, and not extracting dates from plists.


(setf *measurements*
(sort *measurements* #'date-less
:key (lambda (plist) (getf plist :date))))

Note that all this lambda here does is curry the argument for getf; i.e.
it's a curried getf where the indicator argument is assumed to be :date.

This can be done in a generic way, e.g. by defining a function like this:

(defun curry-left (fun captured-left-arg)
(lambda (variable-right-arg)
(funcall fun captured-left-arg variable-right-arg)))

(defun curry-right (fun captured-right-arg)
(lambda (variable-left-arg)
(funcall fun variable-left-arg captured-right-arg)))

Now you can do:

(setf *measurements*
(sort *measurements* #'date-less
:key (curry-right #'getf :date)))

This (curry-right #'getf :date) call returns a one-argument function which
takes a plist, and returns the value of its :date property.
From: Kaz Kylheku on 13 Jan 2010 17:47
On 2010-01-13, Cecil Westerhof <Cecil(a)decebal.nl> wrote:
>> Be aware that SORT may have side-effects on its first argument.
>
> I know, after the function is finished, the first argument is sorted.

After the sort function finishes, if the argument sequence is a list, that list
may have been destroyed in some way. The sorted list is returned.
It may be a new list, a rearrangement of the material from the old list,
or any combination thereof.

If the sequence is a vector, it is sorted by permuting the elements in place
(the vector is returned, and so the return value is EQ to the argument).
From: Thomas A. Russ on 13 Jan 2010 17:21
Cecil Westerhof <Cecil(a)decebal.nl> writes:

> I want to sort a property list on the property date.
> I have the function:
> (defun dates-in-list< (first-list second-list)
> (let ((first-date (getf first-list :date))
> (second-date (getf second-list :date)))
> (string< first-date second-date)))
>
> And I sort the list with:
> (sort *measurements* 'dates-in-lists<)
>
> But I do not want to have the list sorted incrementing, but
> decrementing. Do I understand correctly that I need a function
> dates-in-lists>? Aka: it is not possible to negate.

You could use the COMPLEMENT function. But that would change the
handling of = strings, since the complement of > is <= and not <.

But this is actually much simpler if you exploit the :KEY option to
SORT.

Also, remember that although SORT is destructive, it is not guaranteed
to be in-place, so you need to do

(setq *measurements* (sort *measurements* #'string>
:key #'(lambda (x) (getf x :date))))



--
Thomas A. Russ, USC/Information Sciences Institute
First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4 5
Prev: The Erik Naggum cll archive
Next: a defense of ad hoc software development