Position of minimum element in list

Question

I would like to write a Racket function that takes a list and returns the position of the smallest element of that list. I already wrote a function that works:

  (define (min-position xs)
    (define (min-position2 count pos xs)
      (cond ((null? xs) #f)
            ((= 1 (length xs)) pos)
            ((< (car xs) (cadr xs))
             (min-position2 (+ count 1) pos (cons (car xs) (cddr xs))))
            (else (min-position2 0 (+ count pos 1) (cons (cadr xs) (cddr xs))))))
    (min-position2 0 0 xs))

Example inputs and outputs:

> (min-position '(9 8 7 6 5))
4
> (min-position '(9 8 1 6 5))
2
> (min-position '(0 1 2))
0

But is there a more elegant way to write this?

Answer 1

Well, it all depends on your definition of elegant. For me, an elegant solution is one that is short, clear, idiomatic and uses existing procedures (that is, it doesn't reinvent the wheel). Here's my shot:

(require srfi/1)  ; import `list-index`
(require srfi/26) ; import `cute`

(define (min-position lst)
  (and (not (null? lst))
       (list-index (cute = (apply min lst) <>) lst)))

Here's how it works:

• (apply min lst) finds the minimum element in the list, using the built-in min procedure
• (cute = (apply min lst) <>) uses cute for creating a specialized predicate that will return #t whenever an element is equal to the minimum, making sure that we find the minimum only once
• (list-index (cute = (apply min lst) <>) lst) uses list-index with the previous predicate to find the index with the first minimum element in the list
• The (and (not (null? lst)) … ) part is there for handling the edge case where the input list is empty

Short and sweet. The only disadvantage is that it traverses the input list twice, once for finding the minimum element and once again for finding the index of that element. But that's a small price to pay, and it's still an O(n) solution that works as expected:

(min-position '(9 8 7 6 5))
=> 4
(min-position '(9 8 1 6 5))
=> 2
(min-position '(0 1 2))
=> 0
(min-position '())
=> #f

Answer 2

I'm not sure what you mean by "elegant". There may be a spiffier algorithm, for example. But here's how I would make the code more readable (IMHO) while retaining your basic approach.

Step by step:

Your input/ouput examples, rewritten as check-equal? tests:

#lang racket
(require rackunit)
(define (test f)
  (check-equal? (f '(9 8 7 6 5)) 4)
  (check-equal? (f '(9 8 1 6 5)) 2)
  (check-equal? (f '(0 1)) 0)
  (check-equal? (f '(0 1 2)) 0))

Your original, but using [] instead of () for cond clauses.

(define (min-position/v0 xs)
  (define (min-position2 count pos xs)
    (cond [(null? xs) #f]
          [(= 1 (length xs)) pos]
          [(< (car xs) (cadr xs))
           (min-position2 (+ count 1) pos (cons (car xs) (cddr xs)))]
          [else
           (min-position2 0 (+ count pos 1) (cons (cadr xs) (cddr xs)))]))
  (min-position2 0 0 xs))
(test min-position/v0)

Using match to destructure the list and use names like this and next instead of (car xs) and (cadr xs):

(define (min-position/match xs)
  (define (min-position2 count pos xs)
    (match xs
      [(list) #f]
      [(list _) pos]
      [(list this next more ...)
       (cond [(< this next)
              (min-position2 (+ count 1) pos (cons this more))]
             [else
              (min-position2 0 (+ count pos 1) (cons next more))])]))
  (min-position2 0 0 xs))
(test min-position/match)

Changing the internal function to a let loop .... Really the same thing, just a bit more concise.

(define (min-position/match&loop xs)
  (let loop ([count 0] [pos 0] [xs xs])
    (match xs
      [(list) #f]
      [(list _) pos]
      [(list this next more ...)
       (cond [(< this next) (loop (+ count 1) pos (cons this more))]
             [else          (loop 0 (+ count pos 1) (cons next more))])])))
(test min-position/match&loop)

Again, this is the same algorithm as your original. But I would find it easier to grok quickly.

Answer 3

A named let is a common idiom in Scheme:

(define (min-position xs)
  (let loop ((xs xs) (pos 0) (mn #f) (mnpos #f))
    (if (null? xs)
        mnpos
        (let ((c (car xs)))
          (if (or (not mn) (< c mn))
              (loop (cdr xs) (add1 pos) c pos)
              (loop (cdr xs) (add1 pos) mn mnpos))))))

In Racket, you also have for/fold and in-indexed to make the code even shorter:

(define (min-position xs)
  (define-values (mn mnpos)
    (for/fold ((mn #f) (mnpos #f)) (((c pos) (in-indexed xs)))
      (if (or (not mn) (< c mn))
          (values c pos)
          (values mn mnpos))))
  mnpos)