Как добавить в список в ракетке

Question

For example:
• (sum empty) ⇒ 0
• (sum (list 1 2 3)) ⇒ 6
• (sum (list 1 (list 2) 3 (list 4 5))) ⇒ 15

Что у меня так далеко. Он рассчитывает сумму чисел в списке. Тест проходит для некоторых примеров. Тем не менее, я не знаю, как добавить, если он состоит из чисел, например, пример 3.

(define (sum lloi)
  (cond
    [(empty? lloi) 0]
    [else (+ (first lloi) (sum (rest lloi)))]))

Answer 1

Немного поздно, но вот мое мнение:

(define (sum lloi)
  (cond
    [(empty? lloi) 0]
    [(number? lloi) lloi]
    [else (apply + (map sum lloi))]))

Список ввода может содержать числа, пустые списки или списки в том же формате, что и список ввода. Чтобы найти сумму этого списка, мы складываем все его элементы.

• , если элемент является пустым списком, добавляем 0
• , если элемент является числом, добавляем число
• если элемент является списком, сначала найдите сумму этого списка, затем добавьте ее (рекурсия здесь)

(map sum lloi) применяет функцию sum к каждому элемент lloi.

(map sum '(a b c d)) => '((sum a) (sum b) (sum c) (sum d))

(apply + list) складывает все элементы списка. Вы не можете просто сделать это как (+ list), потому что + принимает в качестве аргументов только цифры, а не списки.

(apply + (1 2 3 4)) => (+ 1 2 3 4)

Answer 2

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

Входные данные представляют собой список, который может содержать числа и списки чисел. Сейчас я предполагаю, что списки могут быть вложены дальше, чем это. Если разрешить произвольно вложенные списки, то это сделает дерево чисел, а не просто список.

;; A NumTree is one of:
;;  - Number
;;  - [Listof NumTree]

;; sum : NumTree -> Number
(define (sum nt)
  ???)

«Один из» в приведенном выше определении данных означает функцию следует использовать условное выражение с вопросом для каждого маркера в поле «один из».

;; sum : NumTree -> Number
(define (sum nt)
  (cond [(number? nt) ???]
        [(list? nt) ???]))

В случаях определения данных нет никаких «подчастей», поэтому следующим шагом является поиск ссылок на сложные определения данных, включая собственные ссылки, и вставка вспомогательных функций для них. [Listof NumTree] является сложным определением данных, поэтому создайте вспомогательную функцию для его суммирования.

Сначала добавьте эту функцию в свой "список wi sh", к ней вы вернетесь позже.

;; sum-listofnumtree : [Listof NumTree] -> Number
(define (sum-listof-numtree lont)
  ???)

Теперь, когда он находится в вашем списке wi sh, используйте его, чтобы завершить sh, определяя остальную часть sum.

;; sum : NumTree -> Number
(define (sum nt)
  (cond [(number? nt) nt]
        [(list? nt) (sum-listof-numtree nt)]))

Теперь, когда это сделано, go вернитесь к ваш список sh и работа на sum-listof-numtree. Опять же, вы можете основать его на определении данных, на этот раз для Listof.

;; A [Listof NumTree] is one of:
;;  - '()
;;  - (cons NumTree [Listof NumTree])

;; sum-listofnumtree : [Listof NumTree] -> Number
(define (sum-listof-numtree lont)
  ???)

Снова "один из" превращается в cond, с ветвью для каждой точки маркера.

;; sum-listofnumtree : [Listof NumTree] -> Number
(define (sum-listof-numtree lont)
  (cond [(empty? lont) ???]
        [(cons? lont) ???]))

Здесь корпус cons состоит из двух частей: first и rest.

;; sum-listofnumtree : [Listof NumTree] -> Number
(define (sum-listof-numtree lont)
  (cond [(empty? lont) ???]
        [(cons? lont) (.... (first lont) (rest lont) ....)]))

Следующим шагом является проверка наличия какой-либо из частей сложные определения данных, и, если они есть, вставка вспомогательных функций. В этом случае оба являются сложными данными. (first lont) - это NumTree, а (rest lont) - это [Listof NumTree].

Функция "helper" для NumTree здесь равна sum, поэтому в шаблоне вы можете использовать (sum (first lont)). А «вспомогательная» функция для [Listof NumTree] равна sum-listof-numtree, поэтому вы можете использовать для этого (sum-listof-numtree (rest lont)).

;; sum-listofnumtree : [Listof NumTree] -> Number
(define (sum-listof-numtree lont)
  (cond [(empty? lont) ???]
        [(cons? lont) (.... (sum (first lont)) (sum-listof-numtree (rest lont)) ....)]))

Теперь просто заполните отверстия тем, что имеет смысл для суммирования.

;; sum-listofnumtree : [Listof NumTree] -> Number
(define (sum-listof-numtree lont)
  (cond [(empty? lont) 0]
        [(cons? lont) (+ (sum (first lont)) (sum-listof-numtree (rest lont)))]))

В совокупности они образуют пару взаимно рекурсивных функций, работающих с парой взаимно рекурсивных определений данных.

;; A NumTree is one of:
;;  - Number
;;  - [Listof NumTree]

;; A [Listof NumTree] is one of:
;;  - '()
;;  - (cons NumTree [Listof NumTree])

;; sum : NumTree -> Number
(define (sum nt)
  (cond [(number? nt) nt]
        [(list? nt) (sum-listof-numtree nt)]))

;; sum-listofnumtree : [Listof NumTree] -> Number
(define (sum-listof-numtree lont)
  (cond [(empty? lont) 0]
        [(cons? lont) (+ (sum (first lont)) (sum-listof-numtree (rest lont)))]))

Answer 3

Задача

OP является примером более общего класса задач, связанных с вложенными списками, часто решаемыми с помощью выравнивания деревьев или выравнивания списков .

С вложенный список, каждый элемент является списком или атомом (игнорируя неправильные списки). Рекурсивная процедура может проходить через входные данные и выравнивать любые встречающиеся подсписки, объединяя результаты в окончательный плоский список.

(define (my-flatten xs)
  (cond ((null? xs)
         '())
        ((list? (first xs))
         (append (my-flatten (first xs))
                 (my-flatten (rest xs))))
        (else
         (cons (first xs)
               (my-flatten (rest xs))))))

Здесь, если первый элемент ввода представляет собой список, он выравнивается и объединяется с результат сглаживания остальной части списка. В противном случае первый элемент не является списком, поэтому он cons добавляется к результату выравнивания остальной части списка.

Этот же шаблон можно использовать для разработки процедуры, которая суммирует все элементы вложенный список.

(define (my-sum xs)
  (cond ((null? xs)
         0)
        ((list? (first xs))
         (+ (my-sum (first xs))
            (my-sum (rest xs))))
        (else
         (+ (first xs)
            (my-sum (rest xs))))))

Можно также использовать процедуру my-flatten для упрощения разработки процедуры суммирования. Существует несколько способов разработки такой процедуры; здесь процедура sum-1 сначала выравнивает список ввода перед использованием именованного let для рекурсивного суммирования по простому списку.

(define (sum-1 tr)
  (let ((xs (my-flatten tr)))
    (let sum-helper ((xs xs))
      (if (null? xs)
          0
          (+ (first xs)
             (sum-helper (rest xs)))))))

Ракетка уже имеет встроенный flatten, который указывает, что такая процедура может быть полезной абстракцией. Обратите внимание, что встроенная процедура Racket является более сложной, чем простая my-flatten, определенная выше; Одним из улучшений является то, что он обрабатывает как неправильные списки, так и правильные списки.

Процедура flatten действительно вступает в свои права в сочетании с другими процедурами более высокого порядка, которые часто используются в стилях функционального программирования. Задача суммирования OP может быть решена очень кратко, используя apply или foldl с flatten.

(define (sum-2 tr)
  (apply + (flatten tr)))

(define (sum-3 tr)
  (foldl + 0 (flatten tr)))

Пример взаимодействия REPL:

scratch.rkt> (my-flatten '((1 2) 3 (4 (5 6 (7 8 9) 10)) 11))
'(1 2 3 4 5 6 7 8 9 10 11)
scratch.rkt> (my-sum '((1 2) 3 (4 (5 6 (7 8 9) 10)) 11))
66
scratch.rkt> (sum-1 '((1 2) 3 (4 (5 6 (7 8 9) 10)) 11))
66
scratch.rkt> (sum-2 '((1 2) 3 (4 (5 6 (7 8 9) 10)) 11))
66
scratch.rkt> (sum-3 '((1 2) 3 (4 (5 6 (7 8 9) 10)) 11))
66

Answer 4

Вот начало:

(define (sum lloi)
  (cond
    [(empty? lloi) 0]
    [(number? (first lloi)) (+ (first lloi) (sum (rest lloi)))]
    [(list?   (first lloi)) ???]))

Если (first lloi) - это список, вам нужно найти его сумму, а затем добавить ее к сумме оставшихся элементов.

Answer 5

(define (sum l)
  (foldl (lambda(x acc) (+ acc (if (pair? x) (sum x) x)))
  0
  l))

 > (sum '(1 2 3 (1 2 3)))
12
> (sum '(1 2 3))
6