1

Can anyone give me a well-written implementation of how to order a list of pairs in scheme using a helper function (based on the value of the car of each of the pairs)? For example, '((3 2) (1 2) (8 4) (0 6)) should be ordered as '((0 6) (1 2) (3 2) (8 4)). This seems like such a simple thing to do, but for some reason I am drawing a blank.

Brian Tompsett - 汤莱恩
  • 5,753
  • 72
  • 57
  • 129
John Friedrich
  • 343
  • 5
  • 21
  • By the way, if you don't want to give me exact code, I would be happy with the base cases. This is apart of a larger program, and I want to make sure it is right. – John Friedrich Nov 09 '13 at 15:26

1 Answers1

1

Well, first of all you can use your favorite built-in sort routine, and specify it be sorting by car, e.g. in Common LISP

(sort ls #'< :key #'car)

if your Scheme lacks the ability to specify key, you can emulate this by a comparison procedure 

(sort ls (lambda (a b) (< (car a) (car b))))

second, if you want to reimplement this, you could use the approach of mergesort: break up your list into monotone increasing portions, then merge them pairwise until there's only one left. In Haskell,

mergesortBy f xs 
   | null xs       = []
   | [s] <- until (null.tail) (pairwise (mergeBy f)) (breakup xs) = s
pairwise g (a:b:t) = g a b : pairwise g t
pairwise _ t       = t
breakup xs         = [[x] | x <- xs] -- a list of (a list of x) for x in xs

since the portions are monotone increasing (or at least non-decreasing), mergeBy can be easily implemented.

Of course, a "well-written" implementation will replace the rudimentary breakup shown here with an initial phase which will try to make longer chunks, preserving the non-decreasing and reversing the non-increasing chunks on the go (a Haskell example is here). pairwise and mergeBy (and perhaps even breakup) functions will have to be fused into one, to make the overall implementation more on-line, since Scheme is (usually) a strict (i.e. non-lazy) language. You could use explicit suspensions in the internal lists being merged, so that taking a few first elements off a sorted list is an O(n) operation.

Community
  • 1
  • 1
Will Ness
  • 70,110
  • 9
  • 98
  • 181
  • Is there a simpler function I can create myself using a helper function that I will also create myself? I am not familiar with many of the functions that you have provided me with, and not too far into my study of Scheme. – John Friedrich Nov 09 '13 at 23:10
  • 1
    you can read Haskell as pseudocode and write it down in Scheme. You did say (in the comment) that you don't need the "exact code". :) Does your Scheme have a `sort` function? Then the second code snippet in my answer is what you want; the `lambda` is the helper function, you can just pull it aside and give it a name: `(define (my-compare a b) (< (car a) ...))`. You can read about all kind of sort algos (incl. mergesort) at the Wikipedia. – Will Ness Nov 09 '13 at 23:49