Подсчет вхождений атома во вложенный список в схеме

Question

Здравствуйте, я новичок в Схеме.

Я читаю учебные материалы в Интернете, и мне интересно, как я могу подсчитать вхождения атомов во вложенные списки в Схеме.Я нашел несколько уроков, в которых упоминаются bagify и flatten;Я пытался смешать их, но я получил ошибку.Что может быть не так?

Вот код:

(define (bagify lst)
  (foldl (lambda (key ht)
         (hash-update ht key add1 0))
       #hash() lst))

(define (flatten mylist)
  (cond ((null? mylist) '())
        ((list? (car mylist)) (append (flatten (car mylist)) (flatten (cdr mylist))))
        (else (cons (car mylist) (flatten (cdr mylist))) (bagify(mylist)))))

Answer 1

Я думаю, bagify и flatten - красные сельди для такого рода проблем. Конечно, вы можете использовать flatten, а затем подсчитать вхождения в полученном сглаженном списке. Однако гораздо эффективнее и проще просто пройти по вложенному списку.

Для простоты давайте начнем с реализации функции для не вложенного случая. Вот версия, которая считает вхождения '?, для еще большей простоты:

(define count-?s
  (lambda (ls)
    (cond
      [(null? ls) 0]
      [(eq? (car ls) '?) (add1 (count-?s (cdr ls)))]
      [else (count-?s (cdr ls))])))

Чтобы изменить это для работы с вложенными списками, достаточно добавить одну cond строку. Реализация flatten, которую вы обнаружили, содержит здесь подсказку: мы хотим на каждом шаге рекурсии проверять, является ли car списка самим списком (однако использование list? является более мощным, чем нам нужно; мы вместо этого можно использовать pair?, если наш ввод всегда является правильным вложенным списком).

Как только мы узнаем, что car также является (потенциально вложенным) списком, нам нужно передать его функции, которая знает, как обрабатывать списки. К счастью, мы находимся в процессе определения одного!

(define count-?s*
  (lambda (ls)
    (cond
      [(null? ls) 0]
      [(pair? (car ls)) (+ (count-?s* (car ls)) (count-?s* (cdr ls)))]
      [(eq? (car ls) '?) (add1 (count-?s* (cdr ls)))]
      [else (count-?s* (cdr ls))])))

И это все, что нужно. Очень мало мыслей, не так ли? На самом деле так мало, что вы можете просто заменить пару выражений и получить функцию, которая делает что-то совершенно отличное от вложенного списка:

(define remove-?s*
  (lambda (ls)
    (cond
      [(null? ls) '()]
      [(pair? (car ls)) (cons (remove-?s* (car ls)) (remove-?s* (cdr ls)))]
      [(eq? (car ls) '?) (remove-?s* (cdr ls))]
      [else (cons (car ls) (remove-?s* (cdr ls)))])))

Решить проблему для вложенного списка очень легко, если вы решили ее для простого списка.

1. Начните с решения плоского списка.
2. Проверить наличие пары в car.
3. Выполните естественную рекурсию для car и cdr.
4. Объедините ответы с помощью бинарного оператора, который имеет смысл с левой стороны кейса null?, например, + / 0, * / 1, cons / '(), and / #t, or / #f.