计划：计数结构 [英] Scheme: Counting Structures

问题描述

$ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $）$ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ b（make-animalTobydog（make-date 2014 3 20））
（make-animalCurlydog（make-date 2014 1 18））
（make-动物Maximus猫（make-date 2013 10 7））
（make-animalMiacat（make-date 2013 10 7）））
=> （list（list 2cat）（list 2dog）（list 1snake））

;;日期是一个结构（make-date y m d），其中
;; y是正整数（年），
;; m是1到12（月）之间的整数，
;; d是1到31之间的整数（月的日期）。
（define-struct date（年月日））
;;动物是一个结构（make-structure n t a），其中
;; n是一个非空字符串（动物名称），
;; t是一个非空字符串（动物类型），
;; a是Date（日期动物到达避难所）。
（define-struct animal（name type arrival））

注意：适用的数据结构作为顶部。

所以我正在尝试使用一个功能（在Scheme中使用Dr.Racket），它消耗Animal结构列表并生成列表列表。

生成的列表中的元素是格式（列表编号类型），其中type是动物的类型，number是消费列表中动物类型的编号

这对我来说太多了，但这里是问题出在哪里： - >列表需要降序 - >更糟糕的是，在事件任何数量的列表之间的一个关系，使用字母排序。

注意：我只想解决这个使用抽象列表功能，不包括构建列表和lambda因为我希望加强我的能力来解决这些问题而不需要先进的抽象功能）

记住这一点，我知道这个问题会使用abstra ct函数map，filter和foldr，但不能完全想到如何。

任何帮助都不胜感激。

解决方案

如果你做（地图动物类型的动物列表），你会得到一个列表， （snakedogcatdogcat）

（如我的例子），所以如果你（sort list-of-animal-types string>？）你有一个排序列表按降序。

鉴于该列表至少有一个元素：

 （let rec（（cur（car sorted-list-of-animal-types））
（cnt 1）
（lst cdr sorted-list-of-animal-types））
（acc'（）））
（cond（（equal？ （<α>）>）（rec cur（add1< ??>）< ??> acc））
 （cons（list cnt cur）< ??>）））））
  

列表按升序排列与计数。可以使用折叠来做到这一点，但它可能不比使用命名的 let 更少的行。

如果您再次排序：

 （sort list-of-animal-types-and-counting（lambda（xy）（> =（car x）（car y）））
  

sort 在Racket中是稳定的，这意味着如果您在列表中有两个相同的数量，他们将最终在他们的原始原来的订单是上升的动物订单，所以结果是按计数降序排序，然后是升序。

我猜你的程序可以通过链接在一起使用让存储中间体以使表达式更短，更易读。

使用哈希，只能使用一个通过未排序的列表，然后生成一个列表，然后按照计数排序的sepcial排序函数排序，然后按类型排序。

(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.

解决方案

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.

这篇关于计划：计数结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！