DrRacket - Intermediate Student With Lambda - List ordering

Question

I have an assignment question that asks me to write a function, using lambda, that consumes a list of numbers and removes all but the first occurrence of each number. My function is I think quite nice, with the exception that it produces the wrong result! It produces a list that contains the last occurrence of each number. It produces a list with the same values as the proper list, just in different order. Here's my code:

    (define (remove-duplicates numlist)
      (foldr (lambda (a b) 
               (cond
                 [(not (member? a b)) (cons a b)]
                 [else b])) empty numlist))

I've tried using foldl instead of foldr but, not surprisingly, it produces the correct list, but in reverse. Is there a way of producing the correct list without resorting to reversing the list created by foldl with another lambda expression?

Please keep in mind, this is homework so no explicit answers please.

Thanks everyone!

As an example, using the list '(9 0 2 1 0 9 0 2 1 0) should be producing '(9 0 2 1), instead I'm getting '(9 2 1 0). Thanks. — Mark Soric
I have a solution that uses two implementations of foldl where the first one uses the result of the second as the list on which to recurse. It seems like shoddy code that would take an extra iteration to run... — Mark Soric

Dan Burton Dan Burton · Accepted Answer · 2011-11-19T22:03:35

Think about how foldr behaves, semantically. It starts at the rightmost element of the list, and performs the fold, moving leftwards. That means that in your lambda function, a represents the element directly to the left of the thus-far-folded list, and b represents the result of folding everything to the right of the list element a. With this in mind, consider:

[(not (member? a b)) (cons a b)]
[else b]

You check whether the list b already contains a. If it does, then you discard a, keeping b as it is. This explains why your code keeps the last (rightmost) occurrence, and not the first. If you wish to perform a right fold, then, you must change your logic. You need to somehow "purge" b of the offending element a that it contains.

[(not (member? a b)) (cons a b)]
[else (cons a (purge a b))]

This way, you will eventually keep only the leftmost, rather than the rightmost, occurrence of each unique element. It may be wise to perform member? and purge simultaneously, since they both must traverse the list; this would require additional refactoring.

Note that, since the function takes O(n²) time anyways, it really doesn't hurt the time complexity to add a O(n) reverse to the foldl version.

DrRacket - Intermediate Student With Lambda - List ordering

1 Answers