Friday, March 18, 2011

A couple of puzzles

  • Write a program that finds the smallest element in a list.
  • Write a program that, given a predicate, finds an extremum from a list. That is, if the predicate is <, the smallest is returned, if the predicate is >, the largest is returned.
    (define (longer? a b) (> (string-length a) (string-length b)))
    Given longer? it would find the longest string in a list.
C.A.R. “Tony” Hoare proposed a selection algorithm to find the kth order statistic in a collection of elements. The obvious solution is this:
(define (list-select predicate list index)
  (list-ref (sort list predicate) index))

;; Examples:
;;
;; Find the smallest element:
;;   (list-select < list 0)
;;
;; Find the second longest string:
;;   (lsit-select longer? list 1)
The “obvious” solution is O(n log n), but one can do better.
at

4 comments:

  1. John CowanMarch 18, 2011 at 9:30 AM

    Here's the classical O(n) solution, which if I remember correctly I learned back in 8th grade hacking Basic:

    > (define (extremum-1 fn old list)
        (cond
          ((null? list) old)
          ((fn (car list) old) (extremum-1 fn (car list) (cdr list)))
          (else (extremum-1 fn old (cdr list)))))
    > (define (extremum fn list)
        (extremum-1 fn (car list) list))
    > (extremum < '(3 2 1 4 5))
    1
    > (extremum > '(3 2 1 4 5))
    5

    But what I'd really like to see is a monadic solution in Scheme, rather than threading the current extremum through the calls as this one does.

    ReplyDelete
  2. Reid KMarch 18, 2011 at 10:23 AM

    QuickSelect, for finding the k'th item of a sorted list without sorting it, of course. :)

    There is potential O(n^2) behavior if the list is already sorted. You can randomize pivot selection and get expected O(n), but it adds some heavy constant factors for iterating the list. Of course, if you care about perf beyond asymptotics, you probably shouldn't be using singly linked lists.

    ReplyDelete
  3. UnknownMarch 23, 2011 at 1:34 PM

    John, It could use some syntactic sugar like Haskell's do notation, but below is a monadic version of the classical O(n) solution.

    (define (>>= m f)
    (lambda (st)
    (let ((res (m st)))
    ((f (car res)) (cdr res)))))

    (define (return v)
    (lambda (st)
    (cons v st)))

    (define (state-get)
    (lambda (st)
    (cons st st)))

    (define (state-put! v)
    (lambda (st)
    (cons '() v)))

    (define (extremum fn lst)
    (>>= (return lst)
    (lambda (l)
    (if (null? l)
    (return '())
    (>>= (state-get)
    (lambda (s)
    (if (fn (car l) s)
    (>>= (state-put! (car l))
    (lambda (ignore)
    (extremum fn (cdr lst))))
    (>>= (state-put! s)
    (lambda (ignore)
    (extremum fn (cdr lst)))))))))))

    (define (run monad st)
    (cdr (monad st)))

    (define test-list '(3 2 1 4 5))

    (run (extremum < test-list) (car test-list))
    ; => 1
    (run (extremum > test-list) (car test-list))
    ; => 5

    ReplyDelete
  4. Joe MarshallMarch 23, 2011 at 3:32 PM

    Previous comment reformatted.

    (define (>>= m f)
      (lambda (st)
        (let ((res (m st)))
          ((f (car res)) (cdr res)))))

    (define (return v)
      (lambda (st)
        (cons v st)))

    (define (state-get)
      (lambda (st)
        (cons st st)))

    (define (state-put! v)
      (lambda (st)
        (cons '() v)))

    (define (extremum fn lst)
      (>>= (return lst)
           (lambda (l)
             (if (null? l)
                 (return '())
                 (>>= (state-get)
                      (lambda (s)
                        (if (fn (car l) s)
                            (>>= (state-put! (car l))
                                 (lambda (ignore)
                                   (extremum fn (cdr lst))))
                            (>>= (state-put! s)
                                 (lambda (ignore)
                                   (extremum fn (cdr lst)))))))))))

    (define (run monad st)
      (cdr (monad st)))

    (define test-list '(3 2 1 4 5))

    (run (extremum < test-list) (car test-list))
    ; => 1
    (run (extremum > test-list) (car test-list))
    ; => 5

    The problem with using a monad in this example is that it doesn't hide anything. A monad allows you to abstract out the state from the parts of the code that don't need it. But there is only one function and it needs it, so nothing gets abstracted.

    ReplyDelete