сколько элементов в списке со схемой

Question

Мне нужно написать функцию, которая вычисляет, сколько элементов в списке на языке схем.

например

(howMany 'a) возвращает 0
(howMany '(a b)) возвращает 1
(howMany '(a (b c))) возвращает 2

как я могу это сделать? я не хотел рабочий код, просто идея для этого. так что, возможно, вам следует рассмотреть возможность удаления рабочих кодов. :) спасибо

Answer 1

Сложенные ответы будут работать. Однако, если это домашнее задание, вы можете попытаться сделать это, используя только простые встроенные функции. Есть два возможных ответа.

Вот наивный способ:

(define (howMany list)
  (if (null? list)
      0
      (+ 1 (howMany (cdr list)))
  )
)

(Ваша реализация Схемы может иметь функцию empty? вместо null?.)

Однако этот алгоритм будет занимать объем пространства, линейно пропорциональный количеству элементов в списке, потому что он будет хранить (+ 1 ...) для каждого элемента списка перед выполнением любого из дополнений. Интуитивно, вам это не нужно. Вот лучший алгоритм, который позволяет избежать этой проблемы:

(define (howMany list)
   (define (iter numSoFar restOfList)
      (if (null? restOfList)  
          numSoFar
          (iter (+ numSoFar 1) (cdr restOfList))
      )
   )
   (iter 0 list)
)

(Бонусные баллы: используйте синтаксис Scheme (let iter ...), чтобы написать это более кратко. Я использовал этот стиль, потому что он более понятен, если вы знаете только несколько примитивов Scheme.)

Answer 2

Скорее всего, за эту фразу проголосуют, но я не знаю схемы. Я, однако, знаком с функциональным программированием.

Если для этого нет встроенных функций, начните с «сворачивания» списка со начальным значением 0 и добавьте 1 к каждому дополнительному сгибу.

Answer 3

Это просто подсчет количества элементов в списке.

(define howMany
   (lambda (list)
      (cond
         [(not (list? list)) 0]
         [(null? list) 0]
         [else (+ 1 (howMany (cdr list)))])))