list - Scheme: Counting Structures

Question

(count-by-type
(list
(make-animal "Slytherin" "snake" (make-date 2013 8 23))
(make-animal "Toby" "dog" (make-date 2014 3 20))
(make-animal "Curly" "dog" (make-date 2014 1 18))
(make-animal "Maximus" "cat" (make-date 2013 10 7))
(make-animal "Mia" "cat" (make-date 2013 10 7))))
=> (list (list 2 "cat") (list 2 "dog") (list 1 "snake"))

;; A Date is a structure (make-date y m d), where
;; y is positive integer (year),
;; m is an integer between 1 and 12 (month),
;; d is an integer between 1 and 31 (day of the month).
(define-struct date (year month day))
;; An Animal is a structure (make-structure n t a), where
;; n is a nonempty string (name of animal),
;; t is a nonempty string (type of animal),
;; a is a Date (date animal arrived at the shelter).
(define-struct animal (name type arrival))

Note: The applicable data structures as at the top.

So I am trying to make a function (in Scheme using Dr. Racket) that consumes a list of Animal structures and produces a list of lists.

The elements in the produced lists are of the form (list number type) where type is the type of animal and number is the number of that animal type in the consumed list.

This much is doable for me, but here is where the issues comes in: -> The list needs to be in descending order -> Even worse, in the event of a tie between any number of pairs of lists, alphabetical sorting is utilized.

Note: I wish to only solve this using abstract list functions excluding build-list and lambda (as I wish to strengthen my ability to solve such problems without advanced abstract functions)

Keeping that in mind, I know this problem will use the abstract functions map, filter, and foldr, but can't quite think of how.

Any help is appreciated.

Answer 1

If you do (map animal-type list-of-animals) you get a list consisting just of the types like ("snake" "dog" "cat" "dog" "cat")

I imagine your list can be mixed (like in my example) so if you (sort list-of-animal-types string>?) you have a sorted list in descending order.

Given the list has at least one element:

(let rec ((cur (car sorted-list-of-animal-types))
          (cnt 1)
          (lst (cdr sorted-list-of-animal-types))
          (acc '()))
  (cond ((equal? cur <??>) (rec cur (add1 <??>) <??> acc))
        (else (rec <??> 1 <??> (cons (list cnt cur) <??>)))))

This will produce a list in ascending order with counts. It's possible to do this with a fold, but it's probably not fewer lines than using a named let.

If you sort again:

(sort list-of-animal-types-and-counts (lambda (x y) (>= (car x) (car y)))

sort in Racket is stable. That means if you have two with equal counts in the list they will end up in their original order. The original order was the ascending animal order so the result is ordered by count descending, then name ascending.

I guess your procedure can be made by chaining these together using let to store intermediates to make expressions shorter and more readable.

Using a hash you could do it with only one pass through the unsorted list, then produced a list that then was sorted with a sepcial sort function that sorts by count, then animal type.