Упрощение функции ракетки

Question

У меня есть следующая функция «изменить», которая берет определенную сумму денег для оплаты, размер счета / монеты, использованной для оплаты, и возвращает список с количеством «монет» ($ 50, $ 20 $ 10 $ 5 $ 2 и $ 1) можно получить после завершения транзакции:

(define (change total payment)
  (let [(x (- payment total))]
    (change-aux x '(50 20 10 5 2 1))))

(define (change-aux change coins)
  (cond
    [(empty? coins) empty]
    [else (let [(num-coins (floor (/ change (car coins))))]
            (append (list num-coins)
                    (change-aux (- change (* (car coins) num-coins)) (cdr coins))))]))

Итак, если я введу эти параметры:

> (change 44 200)

Возвращает вывод:

'(3 0 0 1 0 1)

Это 200-44 = 156, что соответствует 3 монетам на 50 долларов, 1 на 5 долларов и 1 на 1 доллар.

Мой вопрос будет, если есть более элегантный и упрощенный способ написать аналогичную процедуру, не полагаясь на вспомогательные функции, и лучше использовать лямбду, фильтр, карту, сворачивание, сворачивание и т. д. c?

Заранее спасибо.

Answer 1

Вот решение на другом диалекте Lisp , в котором показано, как сделать это с левым сгибом (уменьшением) без какой-либо мутации переменной-накопителя, как своего рода функциональный контрапункт существующему решению.

(defun change (amount coins)
  (reduce-left (tb ((counts . rem) next-coin)
                 (let* ((coin-count (floor rem next-coin))
                        (coin-value (* coin-count next-coin)))
                   (cons (cons coin-count counts)
                         (- rem coin-value))))
               coins
               (cons '() amount)))


3> (change 156 '(50 20 10 5 2 1))
((1 0 1 0 0 3) . 0)

4> (change 88 '(50 20 10 5 2 1))
((1 1 1 1 1 1) . 0)

Обратите внимание, что значения в конечном итоге сообщаются в обратном порядке и помещаются в дополнительную ячейку cons; «фарфоровая» функция могла бы использоваться вокруг этого «трубопровода», чтобы сообщить результат в ожидаемой форме.

Идея состоит в том, что у нас есть аккумулятор, который выглядит следующим образом: (counts . remainder). Часть counts накопителя, хранящаяся в car, представляет собой список монет, накопленных до настоящего времени. Когда сокращение сделано, это держит окончательный список. Поле cdr содержит оставшуюся сумму для обработки; поскольку последняя монета равна 1, она всегда будет равна нулю.

Используя эту структуру аккумулятора, мы обрабатываем список монет.

При каждом вызове нашей функции ядра сокращения, левый аргумент является аккумулятором, а правильный аргумент next-coin является следующим значением достоинства монеты.

Я использовал макрос, называемый макросом tb ("связывание дерева"), который является своего рода lambda это обеспечивает встроенную деструктуризацию, чтобы она выглядела так, как будто у нас есть три параметра.

Начальным значением для задания сокращения является начальный аккумулятор, в котором есть пустой список монет и полная исходная сумма: (cons nil amount) (который я переписал для (cons '() amount) для лучшей совместимости схемы).

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

Надеемся, что это указывает на "более элегантный и упрощенный способ написать аналогичную процедуру, не полагаясь на вспомогательные функции, и скорее использовать лямбду, фильтр, отображение , foldr, foldl et c ", с которыми вы можете работать в Racket. Удачи!

Answer 2

Конечно, вы можете.

Окончательное решение

(define (change total payment (coins '(50 20 10 5 2 1)))
  (let ((rest-diff (- payment total)))
    (map (lambda (coin)
           (let ((num-coins (floor (/ rest-diff coin))))
             (set! rest-diff (- rest-diff (* num-coins coin)))
             num-coins))
         coins)))

Шаг за шагом

Прежде всего, используя внутренний define, вы можете избавиться от вспомогательная функция из глобального пространства имен.

(define (change total payment)
  (define (change-aux change coins)
    (cond
      [(empty? coins) empty]
      [else (let [(num-coins (floor (/ change (car coins))))]
              (append (list num-coins)
                      (change-aux (- change (* (car coins) num-coins)) (cdr coins))))]))
  (let [(x (- payment total))]
    (change-aux x '(50 20 10 5 2 1))))

Затем вы можете включить некоторые переменные вспомогательных функций в лямбда-список глобальной функции.

(define (change total payment (coins '(50 20 10 5 2 1)))
  (define (change-aux change) ;; eliminate coins in the inner lambda list
    (cond
      [(empty? coins) empty] ;; coins in function body looked up from outer arguments
      [else (let [(num-coins (floor (/ change (car coins))))]
              (append (list num-coins)
                      (change-aux (- change (* (car coins) num-coins)) (cdr coins))))]))
  (let [(x (- payment total))]
    (change-aux x))) ;; eliminate coins in the call

Затем, посмотрев код change-aux, каждый понимает, что на самом деле это циклическое прохождение и попытка вписать максимальные кратные текущего значения в остальную оставшуюся разницу - и сбор этих результатов. Можно l oop, используя map и использовать set!, чтобы изменить остальные.

(define (change total payment (coins '(50 20 10 5 2 1)))
  (let ((rest-diff (- payment total)))
    (map (lambda (coin)
           (let ((num-coins (floor (/ rest-diff coin))))
             (set! rest-diff (- rest-diff (* num-coins coin)))
             num-coins))
         coins)))

Затем вы звоните как выше:

(change 44 200)
;; '(3 0 0 1 0 1)