如何知道foldr的組合函數應該採用哪些參數？

Question

對於內置功能foldr，我知道該函數的藍圖是：

(foldr combine base alist) 

combine應該採取兩個參數：

1. 是foldr相似消耗項目

2. 對alist的其餘部分應用foldr的結果

我似乎無法理解如何將點＃2以參數形式存在。你是怎麼做到的？

combine不是內置函數。我必須根據需求自行編寫代碼。

Answer 1

將第二個參數看作迄今爲止的累計值。舉例來說，如果我們添加的元素，然後acc是以前所有的ele S的總和，我們需要添加當前元素：

(foldr (lambda (ele acc) (+ ele acc)) 
     0 ; we're adding numbers, so the base is 0 
     '(1 2 3 4 5)) 
=> 15 

另一個例子 - 如果我們複製列表，然後acc包含以前ele S IN列表（從最後一個開始，打算從那裏回來），我們必須cons當先當前元素：

(foldr (lambda (ele acc) (cons ele acc)) 
     '() ; we're creating a list, so the base is an empty list 
     '(1 2 3 4 5)) 
=> '(1 2 3 4 5) 

的acc的確切性質取決於問題是解決了，但你應該能夠得到ide一個來自前面的例子。

Answer 2

把它看作迄今爲止計算的結果，並且foldr從頭到尾迭代，而foldl從頭到尾迭代。它很容易看到，如果你看一個簡單的實現它：

(define (foldr1 f init lst) 
    (let r ((lst lst)) 
    (if (null? lst) 
     init 
     (cons (f (car lst)) (r (cdr lst))))))   

(foldr1 combine base '(1 2 3))   ; == 
(combine 1 (combine 2 (combine 3 base))) 

(define (foldl1 f init lst) 
    (let r ((lst lst) (acc init)) 
    (if (null? lst) 
     acc 
     (r (cdr lst) (f (car lst)))))) 

(foldl1 combine base '(1 2 3))   ; == 
(combine 3 (combine 2 (combine 1 base))) 

還要注意，命令或參數在一些實現改變。球拍和SRFI-1總是有蓄電池作爲最後一個參數，但在R6RS參數順序fold-left（但不是fold-right）的變化：

#!r6rs 
(import (rnrs)) 

;; swap argument order 
(fold-left (lambda (acc e) (cons e acc)) '() '(1 2 3)) 
; ==> (3 2 1)