Scheme - 对列表中偶数元素的平方求和
Scheme - sum the squares of even-valued elements in a list
我希望能够对列表中偶数元素的平方求和，但是我当前的代码只对元素求和，而不是平方。有谁知道可以进行任何修改以使其对列表中偶数元素的平方求和吗？
(define (sum elemList)
(if
(null? elemList)
0
(+ (car elemList) (sum (cdr elemList)))
)
)
我的输入是：
(sum-evens (list 1 2 3 4))
输出将是：
20
也就是(2*2) + (4*4).
如果可能的话，最好能同时看到递归和迭代的解决方案。
有什么想法吗？
(define (sum ls)
(if (null? ls)
0
(if (even? (car ls))
(+ (square (car ls)) (sum (cdr ls)))
(sum (cdr ls)))))
哪里
(define (square x)
(* x x))
对偶数元素的平方求和。如果你不做任何事情就对列表的元素求和，当然答案不可能是你问题的答案。
另外，这个程序可以这样实现：
(define (sum ls)
(reduce +
0
(map square
(filter even?
ls))))
其中map、filter和reduce是常用的意思（你可以在mit-scheme中试试）。这做同样的事情，但是这更具可读性，并且优化了 cdr 递归之类的东西。 SICP第二章(Structure and Interpretation
计算机程序）介绍了这种编程方法。
有两种可能，要么我们从头开始实现递归：
(define (sum elemList)
(cond ((null? elemList) 0)
((even? (car elemList))
(+ (* (car elemList) (car elemList))
(sum (cdr elemList))))
(else (sum (cdr elemList)))))
或者我们使用内置过程，根据需要定义助手。这种策略被称为使用 "sequences as conventional interfaces":
(define (square x)
(* x x))
(define (sum elemList)
(apply +
(map square
(filter even? elemList))))
在Scheme中，首选方法是第二种，因为当我们有已经为我们完成工作的程序时，我们不能重新发明轮子。无论哪种方式，它都按预期工作：
(sum '(1 2 3 4 5 6 7 8 9 10))
=> 220
使用Racket的左折叠功能，
(define (foldl cons z ls)
(if (null? ls)
z
(foldl cons (cons (car ls) z) ; NB! args order
(cdr ls))))
我们可以很容易地实现列表的求和（(foldl + 0 xs)），或平方的获取，或单独过滤。
嵌套它们也很容易，这样一个就可以处理另一个的结果（如其他答案所示），但这意味着 三个 单独的列表遍历执行，
(define (sqr x) (* x x))
(define (foo-3 xs)
(foldl <b>+ 0</b>
(foldl (lambda (x acc) (<b>cons</b> (sqr x) acc)) <b>'()</b>
(foldl (lambda (x acc) (if (even? x) (cons x acc) acc)) '()
xs))))
但实际上，折叠（或者，"reducing"）一个带有 reducer 函数的列表（比如 +) 用那个函数的应用程序替换了列表的 cons，所以为什么不继续 使用那个reducer 排在首位？这意味着嵌套折叠可以融合在一起
(define (foo-2 xs)
(foldl <b>(lambda (x acc) (+ (sqr x) acc)) 0</b>
(foldl (lambda (x acc) (if (even? x) (<b>cons</b> x acc) acc)) <b>'()</b>
xs)))
并且，进一步，作为
(define (foo-1 xs) ; one traversal, tail-recursive, iterative!
(foldl (lambda (x acc) (if (even? x) <b>(+ (sqr x) acc)</b> acc)) <b>0</b>
xs))
因此推导迭代一次遍历函数，否则可以相对容易地手动编码，但作为递归变体（见其他答案）。
我们看到这里需要对cons进行抽象，这样就可以方便的操作，替换。也就是说，我们要
(lambda (x acc) (<b>cons</b> (<b>sqr</b> x) acc)) ==: ((<i>mapping</i> <b>sqr</b>) <b>cons</b>)
(lambda (x acc) (if (<b>even?</b> x) (<b>cons</b> x acc) acc)) ==: ((<i>filtering</i> <b>even?</b>) <b>cons</b>)
从而得到所谓的 "transducers"，即 reducer 函数的修饰符：
(define (((mapping <b>f</b>) <b>kons</b>) x acc) (<b>kons</b> (<b>f</b> x) acc)) ; "mapping" transducer
(define (((filtering <b>p</b>) <b>kons</b>) x acc) (if (<b>p</b> x) (<b>kons</b> x acc) acc)) ; "filtering" one
(define (foo xs)
(foldl <b>+ 0</b>
(foldl ((mapping sqr) <b>cons</b>) <b>'()</b>
(foldl ((filtering even?) cons) '()
xs)))
=
(foldl <b>((mapping sqr) +) 0</b> ; replace the constructor!
(foldl ((filtering even?) <b>cons</b>) <b>'()</b> ; and the sentinel value
xs))
=
(foldl ((filtering even?) <b>((mapping sqr) +)</b>) <b>0</b> ; and again!
; (lambda (x acc) (if (<b>even?</b> x) (<b>+</b> (<b>sqr</b> x) acc) acc)) ; look, ma, <b>no cons!</b>
xs)
)
(f (g x))模式被抽象为功能组合,
(define ((compose1 f g) x)
(f (g x)))
所以 (f (g x)) 是 ((compose1 f g) x)。更一般的 compose 接受 任意 数量的函数来组合，
(define ((compose . fs) x)
(if (null? fs)
x
((car fs) ((apply compose (cdr fs)) x))))
我们可以以更通用的方式对其进行编码，将我们可能需要的许多转换器组合成一个组合转换器，为它输入的每个参数执行组合操作（取自输入序列；这里是一个列表）：
(define (transduce-list tducr op z xs)
(foldl ; lists are reduced with foldl
(tducr op) ; the full reducer is created by applying
z xs)) ; the transducer to the final reducer
(define (foo xs) ; sum the squares of evens in a list
(transduce-list ; by transducing the list
(compose ; with the transducer composed from
(filtering even?) ; a filtering step and
(mapping sqr)) ; a mapping step
+ 0 xs)) ; with + as the final reducer
就是这样！
所以我们有
(define (sqr1 x) (+ 1 (* x x))) ; for clearer testing results
> (foldl ((mapping sqr1) cons) '() '(1 2 3 4))
'(17 10 5 2)
> (foldl ((mapping sqr1) +) 0 '(1 2 3 4))
> 34
((mapping sqr1) cons)，就像 cons 本身一样，是两个参数的函数，因此可以用作 reducer 函数 的参数 foldl.
(define g ((mapping sqr1) cons)) 等同于
(define (g x acc)
(cons (sqr1 x) acc))
而 filtering 我们有
> (foldl ((filtering even?) +) 0 '(1 2 3 4))
> 6
> (foldl ((mapping sqr1) ((filtering even?) cons)) '() '(1 2 3 4))
> '(10 2)
> (foldl ((filtering even?) ((mapping sqr1) cons)) 0 '(1 2 3 4))
> '(17 5 . 0)
因此，((mapping sqr1) ((filtering even?) cons)) 是一个减速器，其中 (mapping sqr1) 使用 ((filtering even?) cons) 作为 its 减速器。 that is (filtering even?) using cons as its – final in the chain – reducer function:
(define g
((mapping sqr1) ((filtering even?) cons)))
=
(define (g x acc)
(let ((f ((filtering even?) cons)))
(f (sqr1 x) acc))) ; by definition of mapping
=
(define (g x acc)
(define (f y acc)
(if (even? y) (cons y acc) acc)) ; by definition of filtering
(f (sqr1 x) acc))
=
(define (g x acc)
(let ((y (sqr1 x)))
(if (even? y) (cons y acc) acc))) ; by application rule
嗯，映射、过滤和 consing 都自动 汇总到 one reducer 函数中，就好像我们已经编写了一样我们自己！更好的是，foldl 是尾递归的，整个函数是迭代的并且只执行一次列表遍历——因为三个 reducer 函数合并为一个。
更多测试：
(define (bar xs)
(foldl ((compose
(filtering even?) ; filtering is done first
(mapping sqr1))
cons)
0 xs))
(define (baz xs)
(foldl ((compose
(mapping sqr1) ; mapping is done first
(filtering even?))
cons)
'() xs))
所以
> (bar '(1 2 3 4 5))
'(17 5 . 0)
> (baz '(1 2 3 4 5))
'(26 10 2)
或使用 SICP 样式流 !
如果您对此感兴趣，请参阅 计算机程序的结构和解释（Sussman、Abelson）
的 3.5 部分
此处的流函数的工作方式与@WillNess 的回答中描述的转换器非常相似——即，流不需要通过数据进行多次迭代
这里的所有流过程都是递归的，但进化为线性迭代过程
值得注意的是 cons-stream 是一种特殊形式，不会立即计算它的第二个参数
#lang sicp
(define (square x)
(* x x))
(define stream-car car)
(define (stream-cdr s)
(force (cdr s)))
(define (integers x)
(cons-stream x (integers (inc x))))
(define (stream-filter f s)
(cond ((stream-null? s) the-empty-stream)
((f (stream-car s)) (cons-stream (stream-car s) (stream-filter f (stream-cdr s))))
(else (stream-filter f (stream-cdr s)))))
(define (stream-map f s)
(if (stream-null? s)
the-empty-stream
(cons-stream (f (stream-car s)) (stream-map f (stream-cdr s)))))
(define (stream-take n s)
(cond ((stream-null? s) the-empty-stream)
((> n 0) (cons-stream (stream-car s) (stream-take (dec n) (stream-cdr s))))
(else the-empty-stream)))
(define (stream-reduce f acc s)
(if (stream-null? s)
acc
(stream-reduce f (f acc (stream-car s)) (stream-cdr s))))
(stream-reduce + 0
(stream-map square
(stream-filter even?
(stream-take 10
(integers 1)))))
;; => 220
换能器
我怀着深情向@WillNess 提出这部分答案
我是 introduced to transducers 通过一个人，他有能力将极其复杂的事情提炼成奇迹般的简单 – 作为一种爱的劳动，我已经改编了一些 code/ideas 呈现的（最初在javascript) 到方案
每个;; [section]定义了一个抽象障碍
编辑： 删除了 cons-cont 和 cons-trans 的特殊形式——宏并没有显着提高代码的可读性
#lang sicp
;; [procedure]
(define (compose f g)
(lambda (x) (f (g x))))
;; [list]
(define (foldl f acc xs)
(if (null? xs)
acc
(foldl f (f acc (car xs)) (cdr xs))))
;; [continuation]
(define cons-cont
identity)
(define the-empty-cont
identity)
(define cont-concat
compose)
(define (cont-concat-all cs)
(foldl cont-concat the-empty-cont cs))
;; [trans]
(define (cons-trans f)
(cons-cont (lambda (cont) (lambda (acc x) (f cont acc x)))))
(define the-empty-trans
the-empty-cont) ;; unused in this program, but completes implementation
(define trans-concat
cont-concat) ;; unused in this program, but completes implementation
(define trans-concat-all
cont-concat-all)
;; [transducer]
(define (cons-transducer . ts)
(lambda (f acc xs)
(foldl ((trans-concat-all ts) f) acc xs)))
(define (mapper f)
(cons-trans (lambda (next acc x) (next acc (f x)))))
(define (filterer f)
(cons-trans (lambda (next acc x) (if (f x) (next acc x) acc))))
(define (effector f)
(cons-trans (lambda (next acc x) (f x) (next acc x))))
(define (logger s)
(effector (lambda (x) (display s) (display " ") (display x) (display "\n"))))
;; [main]
(define (square x)
(* x x))
(define (main xs)
((cons-transducer (logger "input")
(filterer even?)
(logger "filtered")
(mapper square)
(logger "squared"))
+ 0 xs))
(main '(1 2 3 4 5 6 7 8 9 10))
输出
input 1
input 2
filtered 2
squared 4
input 3
input 4
filtered 4
squared 16
input 5
input 6
filtered 6
squared 36
input 7
input 8
filtered 8
squared 64
input 9
input 10
filtered 10
squared 100
=> 220
我希望能够对列表中偶数元素的平方求和，但是我当前的代码只对元素求和，而不是平方。有谁知道可以进行任何修改以使其对列表中偶数元素的平方求和吗？
(define (sum elemList)
(if
(null? elemList)
0
(+ (car elemList) (sum (cdr elemList)))
)
)
我的输入是：
(sum-evens (list 1 2 3 4))
输出将是：
20
也就是(2*2) + (4*4).
如果可能的话，最好能同时看到递归和迭代的解决方案。 有什么想法吗？
(define (sum ls)
(if (null? ls)
0
(if (even? (car ls))
(+ (square (car ls)) (sum (cdr ls)))
(sum (cdr ls)))))
哪里
(define (square x)
(* x x))
对偶数元素的平方求和。如果你不做任何事情就对列表的元素求和，当然答案不可能是你问题的答案。
另外，这个程序可以这样实现：
(define (sum ls)
(reduce +
0
(map square
(filter even?
ls))))
其中map、filter和reduce是常用的意思（你可以在mit-scheme中试试）。这做同样的事情，但是这更具可读性，并且优化了 cdr 递归之类的东西。 SICP第二章(Structure and Interpretation
计算机程序）介绍了这种编程方法。
有两种可能，要么我们从头开始实现递归：
(define (sum elemList)
(cond ((null? elemList) 0)
((even? (car elemList))
(+ (* (car elemList) (car elemList))
(sum (cdr elemList))))
(else (sum (cdr elemList)))))
或者我们使用内置过程，根据需要定义助手。这种策略被称为使用 "sequences as conventional interfaces":
(define (square x)
(* x x))
(define (sum elemList)
(apply +
(map square
(filter even? elemList))))
在Scheme中，首选方法是第二种，因为当我们有已经为我们完成工作的程序时，我们不能重新发明轮子。无论哪种方式，它都按预期工作：
(sum '(1 2 3 4 5 6 7 8 9 10))
=> 220
使用Racket的左折叠功能，
(define (foldl cons z ls)
(if (null? ls)
z
(foldl cons (cons (car ls) z) ; NB! args order
(cdr ls))))
我们可以很容易地实现列表的求和（(foldl + 0 xs)），或平方的获取，或单独过滤。
嵌套它们也很容易，这样一个就可以处理另一个的结果（如其他答案所示），但这意味着 三个 单独的列表遍历执行，
(define (sqr x) (* x x))
(define (foo-3 xs)
(foldl <b>+ 0</b>
(foldl (lambda (x acc) (<b>cons</b> (sqr x) acc)) <b>'()</b>
(foldl (lambda (x acc) (if (even? x) (cons x acc) acc)) '()
xs))))
但实际上，折叠（或者，"reducing"）一个带有 reducer 函数的列表（比如 +) 用那个函数的应用程序替换了列表的 cons，所以为什么不继续 使用那个reducer 排在首位？这意味着嵌套折叠可以融合在一起
(define (foo-2 xs)
(foldl <b>(lambda (x acc) (+ (sqr x) acc)) 0</b>
(foldl (lambda (x acc) (if (even? x) (<b>cons</b> x acc) acc)) <b>'()</b>
xs)))
并且，进一步，作为
(define (foo-1 xs) ; one traversal, tail-recursive, iterative!
(foldl (lambda (x acc) (if (even? x) <b>(+ (sqr x) acc)</b> acc)) <b>0</b>
xs))
因此推导迭代一次遍历函数，否则可以相对容易地手动编码，但作为递归变体（见其他答案）。
我们看到这里需要对cons进行抽象，这样就可以方便的操作，替换。也就是说，我们要
(lambda (x acc) (<b>cons</b> (<b>sqr</b> x) acc)) ==: ((<i>mapping</i> <b>sqr</b>) <b>cons</b>)
(lambda (x acc) (if (<b>even?</b> x) (<b>cons</b> x acc) acc)) ==: ((<i>filtering</i> <b>even?</b>) <b>cons</b>)
从而得到所谓的 "transducers"，即 reducer 函数的修饰符：
(define (((mapping <b>f</b>) <b>kons</b>) x acc) (<b>kons</b> (<b>f</b> x) acc)) ; "mapping" transducer
(define (((filtering <b>p</b>) <b>kons</b>) x acc) (if (<b>p</b> x) (<b>kons</b> x acc) acc)) ; "filtering" one
(define (foo xs)
(foldl <b>+ 0</b>
(foldl ((mapping sqr) <b>cons</b>) <b>'()</b>
(foldl ((filtering even?) cons) '()
xs)))
=
(foldl <b>((mapping sqr) +) 0</b> ; replace the constructor!
(foldl ((filtering even?) <b>cons</b>) <b>'()</b> ; and the sentinel value
xs))
=
(foldl ((filtering even?) <b>((mapping sqr) +)</b>) <b>0</b> ; and again!
; (lambda (x acc) (if (<b>even?</b> x) (<b>+</b> (<b>sqr</b> x) acc) acc)) ; look, ma, <b>no cons!</b>
xs)
)
(f (g x))模式被抽象为功能组合,
(define ((compose1 f g) x)
(f (g x)))
所以 (f (g x)) 是 ((compose1 f g) x)。更一般的 compose 接受 任意 数量的函数来组合，
(define ((compose . fs) x)
(if (null? fs)
x
((car fs) ((apply compose (cdr fs)) x))))
我们可以以更通用的方式对其进行编码，将我们可能需要的许多转换器组合成一个组合转换器，为它输入的每个参数执行组合操作（取自输入序列；这里是一个列表）：
(define (transduce-list tducr op z xs)
(foldl ; lists are reduced with foldl
(tducr op) ; the full reducer is created by applying
z xs)) ; the transducer to the final reducer
(define (foo xs) ; sum the squares of evens in a list
(transduce-list ; by transducing the list
(compose ; with the transducer composed from
(filtering even?) ; a filtering step and
(mapping sqr)) ; a mapping step
+ 0 xs)) ; with + as the final reducer
就是这样！
所以我们有
(define (sqr1 x) (+ 1 (* x x))) ; for clearer testing results
> (foldl ((mapping sqr1) cons) '() '(1 2 3 4))
'(17 10 5 2)
> (foldl ((mapping sqr1) +) 0 '(1 2 3 4))
> 34
((mapping sqr1) cons)，就像 cons 本身一样，是两个参数的函数，因此可以用作 reducer 函数 的参数 foldl.
(define g ((mapping sqr1) cons)) 等同于
(define (g x acc)
(cons (sqr1 x) acc))
而 filtering 我们有
> (foldl ((filtering even?) +) 0 '(1 2 3 4))
> 6
> (foldl ((mapping sqr1) ((filtering even?) cons)) '() '(1 2 3 4))
> '(10 2)
> (foldl ((filtering even?) ((mapping sqr1) cons)) 0 '(1 2 3 4))
> '(17 5 . 0)
因此，((mapping sqr1) ((filtering even?) cons)) 是一个减速器，其中 (mapping sqr1) 使用 ((filtering even?) cons) 作为 its 减速器。 that is (filtering even?) using cons as its – final in the chain – reducer function:
(define g
((mapping sqr1) ((filtering even?) cons)))
=
(define (g x acc)
(let ((f ((filtering even?) cons)))
(f (sqr1 x) acc))) ; by definition of mapping
=
(define (g x acc)
(define (f y acc)
(if (even? y) (cons y acc) acc)) ; by definition of filtering
(f (sqr1 x) acc))
=
(define (g x acc)
(let ((y (sqr1 x)))
(if (even? y) (cons y acc) acc))) ; by application rule
嗯，映射、过滤和 consing 都自动 汇总到 one reducer 函数中，就好像我们已经编写了一样我们自己！更好的是，foldl 是尾递归的，整个函数是迭代的并且只执行一次列表遍历——因为三个 reducer 函数合并为一个。
更多测试：
(define (bar xs)
(foldl ((compose
(filtering even?) ; filtering is done first
(mapping sqr1))
cons)
0 xs))
(define (baz xs)
(foldl ((compose
(mapping sqr1) ; mapping is done first
(filtering even?))
cons)
'() xs))
所以
> (bar '(1 2 3 4 5))
'(17 5 . 0)
> (baz '(1 2 3 4 5))
'(26 10 2)
或使用 SICP 样式流 !
如果您对此感兴趣，请参阅 计算机程序的结构和解释（Sussman、Abelson）
的 3.5 部分此处的流函数的工作方式与@WillNess 的回答中描述的转换器非常相似——即，流不需要通过数据进行多次迭代
这里的所有流过程都是递归的，但进化为线性迭代过程
值得注意的是 cons-stream 是一种特殊形式，不会立即计算它的第二个参数
#lang sicp
(define (square x)
(* x x))
(define stream-car car)
(define (stream-cdr s)
(force (cdr s)))
(define (integers x)
(cons-stream x (integers (inc x))))
(define (stream-filter f s)
(cond ((stream-null? s) the-empty-stream)
((f (stream-car s)) (cons-stream (stream-car s) (stream-filter f (stream-cdr s))))
(else (stream-filter f (stream-cdr s)))))
(define (stream-map f s)
(if (stream-null? s)
the-empty-stream
(cons-stream (f (stream-car s)) (stream-map f (stream-cdr s)))))
(define (stream-take n s)
(cond ((stream-null? s) the-empty-stream)
((> n 0) (cons-stream (stream-car s) (stream-take (dec n) (stream-cdr s))))
(else the-empty-stream)))
(define (stream-reduce f acc s)
(if (stream-null? s)
acc
(stream-reduce f (f acc (stream-car s)) (stream-cdr s))))
(stream-reduce + 0
(stream-map square
(stream-filter even?
(stream-take 10
(integers 1)))))
;; => 220
换能器
我怀着深情向@WillNess 提出这部分答案
我是 introduced to transducers 通过一个人，他有能力将极其复杂的事情提炼成奇迹般的简单 – 作为一种爱的劳动，我已经改编了一些 code/ideas 呈现的（最初在javascript) 到方案
每个;; [section]定义了一个抽象障碍
编辑： 删除了 cons-cont 和 cons-trans 的特殊形式——宏并没有显着提高代码的可读性
#lang sicp
;; [procedure]
(define (compose f g)
(lambda (x) (f (g x))))
;; [list]
(define (foldl f acc xs)
(if (null? xs)
acc
(foldl f (f acc (car xs)) (cdr xs))))
;; [continuation]
(define cons-cont
identity)
(define the-empty-cont
identity)
(define cont-concat
compose)
(define (cont-concat-all cs)
(foldl cont-concat the-empty-cont cs))
;; [trans]
(define (cons-trans f)
(cons-cont (lambda (cont) (lambda (acc x) (f cont acc x)))))
(define the-empty-trans
the-empty-cont) ;; unused in this program, but completes implementation
(define trans-concat
cont-concat) ;; unused in this program, but completes implementation
(define trans-concat-all
cont-concat-all)
;; [transducer]
(define (cons-transducer . ts)
(lambda (f acc xs)
(foldl ((trans-concat-all ts) f) acc xs)))
(define (mapper f)
(cons-trans (lambda (next acc x) (next acc (f x)))))
(define (filterer f)
(cons-trans (lambda (next acc x) (if (f x) (next acc x) acc))))
(define (effector f)
(cons-trans (lambda (next acc x) (f x) (next acc x))))
(define (logger s)
(effector (lambda (x) (display s) (display " ") (display x) (display "\n"))))
;; [main]
(define (square x)
(* x x))
(define (main xs)
((cons-transducer (logger "input")
(filterer even?)
(logger "filtered")
(mapper square)
(logger "squared"))
+ 0 xs))
(main '(1 2 3 4 5 6 7 8 9 10))
输出
input 1
input 2
filtered 2
squared 4
input 3
input 4
filtered 4
squared 16
input 5
input 6
filtered 6
squared 36
input 7
input 8
filtered 8
squared 64
input 9
input 10
filtered 10
squared 100
=> 220