How to save and sort coordinates (of points) in scheme ?

Question

Hi, I want to save coordinates of points (X,Y) in a list. Also I want to sort the list by X or Y value every time I add points in that list.

How can I do that?

Thanks in advance.

Answer 1

There are many ways you can do this in Scheme. In this answer I'll use PLT Scheme (as your tag suggested). I'll give links to the PLT Scheme documentation where you can read more about these things.

First of all we can define a point structure.

 (define-struct point (x y) #:transparent)

This simple definition will automatically create many useful function which we can use when working with our points

• (make-point 3 4) will create a new point with coordinates (3,4)
• (point-x <some-point>) returns the x coordinate, ex. (point-x (make-point 3 4)) evaluates to 3

To sort a list of points by their y coordinates:

(define (sort-by-y lst)
  (sort lst
        <
        #:key point-y))

If you want to keep the list sorted when you insert a new point you can do something like

(define (insert x xs #:predicate (p <) #:key (k (lambda (x) x)))
   (if (null? xs)
       (list x)
       (let ((y (car xs)))
         (if (p (k x) (k y))
             (cons x xs)
             (cons y (insert x 
                             (cdr xs) 
                             #:predicate p 
                             #:key k))))))

The insert function takes two optional arguments:

• a predicate function, which can be used to keep the list sorted according to different orderings (defaults to <)
• a key function which can be used to extract an element from some structure (defaults to the identity function)

This function can be used like this:

> (insert 3 (list 1 2 4 5 6))
(1 2 3 4 5 6)

> (insert (make-point 3 5) plist #:key point-y)
(#(struct:point 2 1) 
 #(struct:point 9 2) 
 #(struct:point 1 3) 
 #(struct:point 3 5) 
 #(struct:point 6 6))

> (insert (make-point 3 5) (reverse plist) #:predicate > #:key point-y)
(#(struct:point 6 6) 
 #(struct:point 3 5) 
 #(struct:point 1 3) 
 #(struct:point 9 2) 
 #(struct:point 2 1))

where plist is a sorted list of points.