Лучшая практика для схем / ракеток - рекурсия против накопления переменных

Question

Я новичок в Scheme (через Racket) и (в меньшей степени) функциональном программировании, и мог бы воспользоваться некоторыми советами о плюсах и минусах накопления через переменные по сравнению с рекурсией. Для целей этого примера я пытаюсь вычислить скользящее среднее. Таким образом, для списка '(1 2 3 4 5) скользящая средняя за 3 периода будет '(1 2 2 3 4). Идея состоит в том, что любые числа перед периодом еще не являются частью вычисления, и как только мы достигнем длины периода в наборе, мы начинаем усреднять подмножество списка в соответствии с выбранным периодом.

Итак, моя первая попытка выглядела примерно так:

(define (avg lst)
  (cond
   [(null? lst) '()]
   [(/ (apply + lst) (length lst))]))

(define (make-averager period)
  (let ([prev '()])
    (lambda (i)
      (set! prev (cons i prev))
      (cond
       [(< (length prev) period) i]
       [else (avg (take prev period))]))))

(map (make-averager 3) '(1 2 3 4 5))

> '(1 2 2 3 4)

Это работает. И мне нравится использование карты. Это кажется сложным и открытым для рефакторинга. Я мог видеть в будущем двоюродных братьев, таких как:

(map (make-bollinger 5) '(1 2 3 4 5))
(map (make-std-deviation 2) '(1 2 3 4 5))

и т.д.

Но это не в духе Схемы (верно?), Потому что я накапливаю побочные эффекты. Поэтому я переписал это так:

(define (moving-average l period)
  (let loop ([l l] [acc '()])
    (if (null? l)
        l
        (let* ([acc (cons (car l) acc)]
               [next
                 (cond
                  [(< (length acc) period) (car acc)]
                  [else (avg (take acc period))])])
          (cons next (loop (cdr l) acc))))))

 (moving-average '(1 2 3 4 5) 3)
 > '(1 2 2 3 4)

Теперь эту версию сложнее понять с первого взгляда. Итак, у меня есть пара вопросов:

1. Есть ли более элегантный способ выражения рекурсивной версии с использованием некоторых встроенных итерационных конструкций ракетки (например, for/fold)? Это даже хвост рекурсивно, как написано?

2. Можно ли написать первую версию без использования переменной аккумулятора?

3. Является ли этот тип проблемы частью более широкой схемы, для которой существуют принятые передовые практики, особенно в Схеме?

Answer 1

Мне немного странно, что вы начинаете перед первым списком, но резко останавливаетесь в конце.То есть вы берете первый элемент отдельно и первые два элемента сами по себе, но вы не делаете то же самое для последнего элемента или последних двух элементов.

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

# lang racket

(require rackunit)

;; given a list of numbers and a period, 
;; return a list of the averages of all 
;; consecutive sequences of 'period' 
;; numbers taken from the list.
(define ((moving-average period) l)
  (cond [(< (length l) period) empty]
        [else (cons (mean (take l period)) 
                    ((moving-average period) (rest l)))]))

;; compute the mean of a list of numbers
(define (mean l)
  (/ (apply + l) (length l)))

(check-equal? (mean '(4 4 1)) 3)
(check-equal? ((moving-average 3) '(1 3 2 7 6)) '(2 4 5))

Answer 2

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

(define (partition lst default size)
  (define (iter lst len result)
    (if (< len 3)
      (reverse result)
      (iter (rest lst)
            (- len 1)
            (cons (take lst 3) result))))
  (iter (cons default (cons default lst))
        (+ (length lst) 2)
        empty))

(define (avg lst)
  (cond
   [(null? lst) 0]
   [(/ (apply + lst) (length lst))]))

(map avg (partition (list 1 2 3 4 5) 0 3))

Также обратите внимание, что функция partition является хвост-рекурсивной, поэтомуон не поглощает место в стеке - это точка вызова result и reverse.Я явно отслеживаю длину списка, чтобы избежать либо повторного вызова length (что приведет к O (N ^ 2) времени выполнения), либо хакерства вместе функции at-least-size-3.Если вам не нужна хвостовая рекурсия, должен работать следующий вариант partition:

(define (partition lst default size)
  (define (iter lst len)
    (if (< len 3)
      empty
      (cons (take lst 3)
            (iter (rest lst)
                  (- len 1)))))
  (iter (cons default (cons default lst))
        (+ (length lst) 2)))

Последний комментарий - использование '() в качестве значения по умолчанию для пустого списка может быть опасным, если вы нене проверяйте это явно.Если ваши числа больше 0, 0 (или -1), вероятно, будут работать лучше в качестве значения по умолчанию - они не будут уничтожать любой код, использующий это значение, но их легко проверить и они не могут отображаться в качестве допустимого среднего

Answer 3

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

Я приготовил это за три минуты; это, вероятно, неправильно во многих отношениях, но это должно дать вам представление:

;;;
;;; Traverse a list from left to right and call fn with the "windows"
;;; of the list.  fn will be called like this:
;;;
;;;     (fn prev cur next accum)
;;;
;;; where cur is the "current" element, prev and next are the
;;; predecessor and successor of cur, and accum either init or the
;;; accumulated result from the preceeding call to fn (like
;;; fold-left).
;;;
;;; The left-edge and right-edge arguments specify the values to use
;;; as the predecessor of the first element of the list and the
;;; successor of the last.
;;;
;;; If the list is empty, returns init.
;;;
(define (windowed-traversal fn left-end right-end init list)
  (if (null? list)
      init
      (windowed-traversal fn
                          (car list)
                          right-end
                          (fn left-end
                              (car list)
                              (if (null? (cdr list))
                                  right-end
                                  (second list))
                              init)
                          (cdr list))))

(define (moving-average list)
  (reverse!
   (windowed-traversal (lambda (prev cur next list-accum)
                         (cons (avg (filter true? (list prev cur next)))
                               list-accum))
                       #f
                       #f
                       '()
                       list)))