Comparing lists, ignoring internal ordering

The case frequently arises where you want to compare two lists, but don't care about internal ordering within the lists. Unfortunately, equal? will not do what you want here.

Instead, you can provide a function that sorts the lists before comparing for equality. The following code assumes a list of strings; the lambda expression can be modified to work on any appropriate data type.

#lang scheme
(provide compare-no-order)

(define (my-sort a-list)
  (if (list? a-list)
      (sort a-list
            (lambda (x y)
              (and (string? x)
                   (string? y)
                   (string<? x y))))
      a-list))
  
(define (compare-no-order l1 l2)
  (equal? (my-sort l1) (my-sort l2)))

As for all equality functions, this should be placed in a file (say, unsortedlistcompare.ss) in the provided folder. Then, the following options should appear in an options.ss folder, likely seen in precisely the following order (see BitterSuiteScheme for an explanation of the options):

(modules "unsortedlistcompare.ss")
(loadcode ...)
(equal compare-no-order)

Note that additional modules can be added to the modules list, and the ... in loadcode should be replaced with the appropriate student file.

Explanation of code

The lambda expression is designed with the expectation that the question specifies list of strings, and that all expected solutions will be lists of strings. It should be modified to handle any other appropriate data type. The type checks are essential as there is no guarantee that students will give us the correct data type; this program should not crash, but at this point ordering no longer matters as we know equal? will fail, so just return false and let any arbitrary ordering within the list happen.

Because we cannot trust student code, the my-sort function must also first check if the value consumed by it really is a list, just re-producing the value if it is not.

Topic revision: r1 - 2010-03-08 - TerryVaskor
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2019 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback