在 Scheme 中实现 "Accumulate" 函数

Question

几周来我一直在尝试实现一个 Accumulate 函数。我已经正确地实现了一个 "Map" 函数，它遍历一个列表并对每个元素运行一个函数。

我正在使用这个函数来实现"Accumulate"

   (define accumulate
  (lambda (op base func ls)
    (if(null? ls)
       ls
   (cond (not (null? (cdr ls)) (op base (map func ls) (accumulate op base func (cdr ls))))
       (op base (map func ls) (op base (func(car ls))))
   )
     )))
    ;It gets to a point (the last element) after applying the map function to each element,
    ;where it is '(number) instead of an expected "number" (outside of () ). I cannot figure out
    ;how to circumvent this.

我一直在思考如何正确处理这个问题。正确的做法是什么？

预期结果是：

; accumulate: combines using OP the values of a list LS after mapping a function FUNC on it
;    (accumulate + 0 sqr '(1 2 3)) => 14
;    (accumulate * 1 sqr '(1 2 3)) => 36
;

Answer 1

您想实现一个适用于列表的折叠过程，您不需要使用map，只需依次处理每个元素即可。这更像是：

(define accumulate
  (lambda (op base func ls)
    (if (null? ls)
        base
        (op (func (car ls))
            (accumulate op base func (cdr ls))))))

例如：

(accumulate + 0 sqr '(1 2 3))
=> 14

(accumulate * 1 sqr '(1 2 3))
=> 36

Answer 2

您可以以 map、⁽¹⁾ 实现您的 accumulate 以获取乐趣且无利润：

(define (accumulate op base func ls)
  (define (butlast xs) 
      (reverse (cdr (reverse xs))))
  (let ((xs (map list ls)))       ; box'em up
    (for-each
       (lambda (a1 x)
         (let ((a2  (op (car a1) (func (car x))) ))
            (set-car! x a2)))
       (butlast (cons (list base) xs))
       xs)
    (caar (reverse xs))))         ; last

(display (accumulate + 0 (lambda (x) (* x x)) (list 1 2 3 4)))

;   0 1 5 14
;   1 2 3 4   => 30
; 0 1 5 14

^{⁽¹⁾（好吧，for-each，这在很大程度上类似于 map，但确保参数列表中函数应用的从左到右的顺序，这在这里是必不可少的......或者我们可以使用 SRFI-1 中的 map-in-order，它具有额外的优势，即调用 butlast 变得不必要）。}

这模拟了（有明显的扭曲），在 R5RS 方案中，

的旧式惰性流编程定义

accumulate op base ls  =  last xs
  where
      xs = [base, ...map op xs ls]

~> accumulate (+) 0 (map (^2) [1,2,3,4])
30
  
;;   0 a b c d   +
;;   1 4 9 16    =    d
;; 0 a b c d

（在伪代码中）当它沿着列表移动时，它也将累积结果“写入”在过去的当前列表节点处。这是 actually known as scanl 例如Haskell，并从该列表中取出最后一个结果使其成为 foldl（左侧折叠）。

在 Scheme 中实现 "Accumulate" 函数

Implementing "Accumulate" Function in Scheme

list

scheme

map-function

accumulate