Another way of writing a mimum value procedure in

So if i have the following, which returns the smallest value out of a set of four numbers:

(define (minimum2 a b c d)
  (cond ((and (< a b) (< a c) (< a d)) a)
        ((and (< b c) (< b d)) b)
        ((< c d) c)
        (else d)))

But, I want to write it so that I compare a to b and find the smallest value between those two, then compare c and d, and find the smallest value between those, and then compare those two smallest values together to find the actual minimum. If what I wrote was tough to understand, think of it like a tournament bracket, where a "plays" b, and the winner plays the other winner between c and d. Thank you in advance for the help!

回答1:

Here's one way to do it:

(define (min4 a b c d)
  (define (min2 x y)
    (if (< x y) x y))
  (min2 (min2 a b) (min2 c d)))

Another way to do it, if you don't want to use an internal function:

(define (min4 a b c d)
  (let ((min-ab (if (< a b) a b))
        (min-cd (if (< c d) c d)))
    (if (< min-ab min-cd) min-ab min-cd)))

回答2:

Here are two ways to do this. I think that the first, using reduce, is much more idiomatic, but it's not doing the tournament style structure, though it uses the same number of comparisons. The second, which does a tournament style structure, is actually just a special case of a generalized merge-sort. The reason that the number of comparisons is the same is that in the tournament style comparison,

min(a,b,c,d) = min(min(a,b),min(c,d))

and in the reduce formulation,

min(a,b,c,d) = min(min(min(a,b),c),d)

Both require three calls the lowest level min procedure.

A `reduce` based approach

This solution uses a fold (more commonly called reduce in Lisp languages, in my experience). Scheme (R⁵RS) doesn't include reduce or fold, but it's easy to implement:

(define (reduce function initial-value list)
  (if (null? list)
      initial-value
      (reduce function (function initial-value (car list))
              (cdr list))))

A left-associative fold is tail recursive and efficient. Given a binary function f, an initial value i, and a list [x₁,…,x_n], it returns f(f(…f(f(i, x₁), x₂)…), x_n-1), x_n).

In this case, the binary function is min2. R5R5 actually already includes an n-ary (well, it actually requires at least one arguments, it's at-least-one-ary) min, which means min would already work as a binary function, but then again, if you wanted to use the built in min, you'd just do (min a b c d) in the first place. So, for the sake of completeness, here's a min2 that accepts exactly two arguments.

(define (min2 a b)
  (if (< a b)
      a
      b))

Then our n-ary min* is simply a reduction of min2 over an initial value and a list. We can use the . notation in the argument list to make this a variadic function that requires at least one argument. This means that we can do (min* x) => x, in addition to the more typical many-argument calls.

(define (min* a . rest)
  (reduce min2 a rest))

For example:

(min* 4 2 1 3)
;=> 1

A true tournament-style solution based on merge sort

A proper tournament style min is actually isomorphic to merge sort. Merge sort recursively splits a list in half (this can be done in place using the indices of the original list, as opposed to actually splitting the list into new lists), until lists of length one are produced. Then adjacent lists are merged to produce lists of length two. Then, adjacent lists of length two are merged to produce lists of length four, and so on, until there is just one sorted list. (The numbers here don't always work out perfectly if the length of the input list isn't a power of two, but the same principle applies.) If you write an implementation of merge sort that takes the merge function as a parameter, then you can have it return the one element list that contains the smaller value.

First, we need a function to split a list into left and right sides:

(define (split lst)
  (let loop ((left '())
             (right lst)
             (len (/ (length lst) 2)))
    (if (< len 1)
        (list (reverse left) right)
        (loop (cons (car right) left)
              (cdr right)
              (- len 1)))))

> (split '(1 2 3 4))
((1 2) (3 4))
> (split '(1))
(() (1))
> (split '(1 2 3))
((1) (2 3))

Merge sort is now pretty easy to implement:

(define (merge-sort list merge)
  (if (or (null? list) (null? (cdr list))) 
      list
      (let* ((sides (split list))
             (left (car sides))
             (right (cadr sides)))
        (merge (merge-sort left merge)
               (merge-sort right merge)))))

We still need the merge procedure. Rather than the standard one that takes two lists and returns a list of their sorted elements, we need one that can take two lists, where each has at most one element, and at most one of the lists may be empty. If either list is empty, the non-empty list is returned. If both lists are non-empty, then the one with the smaller element is returned. I've called it min-list.

(define (min-list l1 l2)
  (cond
    ((null? l1) l2)
    ((null? l2) l1)
    (else (if (< (car l1) (car l2))
              l1
              l2))))

In this case, you can define min* to make a call to merge-sort, where the merge procedure is min-list. Merge-sort will return a list containing one element, so we need car to take that element from the list.

(define (min* a . rest)
  (car (merge-sort (cons a rest) min-list)))

(min* 7 2 3 6)
;=> 2