Как узнать, какие параметры должна выполнять функция объединения foldr?

Question

Для встроенной функции foldr, я знаю, функция план заключается в следующем:

(foldr combine base alist) 

combine должен принимать два параметра:

1. элемент, который foldr потребляет

2. результат применения foldr для остальной части алиста

Я, похоже, не понимаю, как поставить точку №2 в форме параметра когда-либо. Как ты сделал это?

combine не является встроенной функцией. Я должен был бы сам кодировать его на основе требований.

Answer 1

Подумайте о втором параметре как накопленном значении. Например, если мы добавляем элементы, то acc является суммой всех предыдущих ele х, и мы должны добавить текущий элемент:

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

Другой пример - если вы копируете список, затем acc содержит предыдущие ele сек в списке (начиная с последнего и возвращаясь оттуда), и мы должны 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 зависит от задачи, чтобы быть решено, но вы должны иметь возможность a из предыдущих примеров.

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)