Scheme,level intermediate student, find min without recursion

0
votes

How can I write a function using abstract list functions (foldr, map, and filter) without recursion that consumes a list of numbers (list a1 a2 a3 ...) and produces a new list removing the minimum number from the original list?

The recursion code is:

(define (find-min lst)
  (cond
    [(empty? (rest lst)) (first lst)]
    [else
     (local [(define min-rest (find-min (rest lst)))]
       (cond
         [(< (first lst) min-rest) (first lst)]
         [else min-rest]))]))
3
schemeracket
What have you done so far? What have you tried? What worked? What didn't? This looks like a homework exercise, and I fell you will learn more approaching the problem this way than if we provide code directly. - chwarr
I can do it with recursion, but don't know how to do without recursion. This is not the homework question. The homework question is to calculate a grade from a list of grades without the lowest and the excused grades. I can remove the excused grades and calculate the grade. But not able to remove the lowest grade without recursion. I don't know how to get this part. - Cylia
What have you done so far? What have you tried? What worked? What didn't? How would you do it using recursion? - chwarr
I tried to write the code with recursion, and tried to dig something from it but failed. I also tried to compare the first of the list with the second and then use filter, but it doesn't work either. - Cylia
You might find the answers to Another way of writing a minimum value procedure in Scheme? useful. I bet some of them are within the syntactic restrictions that you have. - Joshua Taylor

3 Answers

-2
votes
(define (comparator n) (local [(define (compare v) (not (equal? v n)))] compare))
(define (without-min list) (filter (comparator (foldr min (foldr max 0 list) list)) list))
2
votes

A fold applies a 2-argument function against a given value and the car of a list uses the result against the successive cars or the cdrs or the list. this is what we want.

Whereas map returns a new list by doing something with each element of a list.

And filter returns a smaller or equal list based on some predicate.

Now just to formulate a function that can choose the lessor of two arguments

(define (the-lessor x y)
 (if (< x  y)
     x
     y))

From there implementation is straightforward.

(define (min L) (fold the-lessor (car L) (cdr L)))
1
votes

Since this looks like a homework question, I'm not going to provide all the code, but hopefully push you in the right direction.

From the HTDP book, we see that "The Intermediate Student language adds local bindings and higher-order functions." The trick here is probably going to using "local bindings".

Some assumptions:

  • (remove-min-from-list '()) => not allowed: input list must be non-empty
  • (remove-min-from-list '(1)) => '()
  • (remove-min-from-list '(1 2 3 1 2 3)) => '(2 3 2 3) ; all instances of 1 were removed

Somehow, we need to find the minimum value of the list. Call this function min-of-list. What are its inputs and outputs? It's input is a list of numbers and its output is a number. Of the abstract list functions, which ones allow us to turn a list of numbers into a number? (And not another list.) This looks like foldl/foldr to me.

(define (min-of-list lst)
    (foldr some-function some-base lst))

Since you already showed that you could write min-of-list recursively, let's move on. See @WorBlux's answer for hints there.

How would we use this in our next function remove-min-from-list? What are the inputs and outputs of remove-min-from-list? It takes a list of numbers and returns a list of numbers. Okay, that looks like map or filter. However, the input list is potentially shorter than that output list, so filter and not map.

(define (remove-min-from-list lst)
    ....
    (filter some-predicate list))

What does some-predicate look like? It needs to return #f for the minimum value of the list.

Let's pull this all together and use local to write one function:

(define (remove-min-from-list lst)
  (local [(define min-value ...)
          (define (should-stay-in-list? number) ...min-value ...)]
    (filter should-stay-in-list? lst)))

The key here, is that the definition for should-stay-in-list? can refer to min-value because min-value came before it in the local definitions block and that the filter later on can use should-stay-in-list? because it is in the body of the local.