함수 프로그래밍 - 접기를 사용하여 스캔 (접두사 합계) 구현

Question

저는 함수 프로그래밍을 가르쳐 왔으며 현재 접기를 사용하여 다른 고차 함수를 작성하고 있습니다. 나는 (또한 접두사 합계로 알려진) 스캔을 구현하는 붙어있어.

이

(define (map op sequence) 
    (fold-right (lambda (x l) (cons (op x) l)) nil sequence)) 

그리고 검사에서 내 샷은 다음과 같습니다 :

이

(define (scan sequence) 
    (fold-left (lambda (x y) (append x (list (+ y (car (reverse x)))))) (list 0) sequence)) 

나의 관찰은 "x"는 "Y"지금까지 결과 배열되고 해당되는이 같은 배를 사용하여 내지도 구현이 보인다 입력리스트의 다음의 요소 이 결과는 다음과 같습니다.

(scan (list 1 4 8 3 7 9)) -> (0 1 5 13 16 23 32) 

그러나이 결과는 람다 내부에서 진행되는 결과 목록의 반전과 함께 꽤보기 흉한 것처럼 보입니다. 나는 다음 결과가 많은 것을 병렬화하려고 시도 할 때부터 결과 목록에서 전역 연산을하지 않는 편이 더 낫다고 생각한다 (이것은 다른 이야기이다. 나는 여러 가지 CUDA 논문을보고있다).

아무에게도 더 세련된 해결책이 있습니까?

BTW 배 왼쪽과 배 오른쪽의 내 구현은 : 나는이 작업을 수행하지 않을

(define (fold-left op initial sequence) 
(define (iter result rest) 
    (if (null? rest) 
    result 
    (iter (op result (car rest)) (cdr rest)))) 
(iter initial sequence)) 

(define (fold-right op initial sequence) 
(if (null? sequence) 
    initial 
    (op (car sequence) (fold-right op initial (cdr sequence))))) 

Answer 1

Imho 스캔은 fold으로 매우 잘 표현됩니다.

하스켈 예 :

scan func list = reverse $ foldl (\l e -> (func e (head l)) : l) [head list] (tail list) 

이 운동 이후 역을 사용하여 속임이

(define scan 
    (lambda (func seq) 
    (reverse 
     (fold-left 
     (lambda (l e) (cons (func e (car l)) l)) 
     (list (car seq)) 
     (cdr seq))))) 

Answer 2

. fold은 실제로 scan (스캔 된 목록의 마지막 요소)의 관점에서 구현 될 수 있습니다. 그러나 scan과 fold은 사실 직교 연산입니다. CUDA 논문을 읽었다면 스캔은 두 단계로 이루어져 있음을 알게 될 것입니다. 첫 번째는 두 번째 결과물을 부산물로 만듭니다. 두 번째 단계는 스캔에만 사용됩니다 (물론 병렬 구현에 대해서만 계산되며 fold의 순차 구현은 scan에 전혀 의존하지 않는 경우 더 효율적입니다).

Answer 3

이럴 다리오 같은 것을로 번역해야 폴드하지 역 배의 관점에서 표현에 대해이었다. 이것은 물론, 스캔을 표현하는 끔찍한 방법이지만 둥근 구멍에 정사각형 못을 끼워 넣는 재미있는 운동입니다. 여기

는 하스켈, 내가 공을 선도 하나가 제거 할 수 다리오으로 TEH 같은 트릭을 사용하여, 물론 혀짤배기

let scan f list = foldl (\ xs next -> xs++[f (last xs) next]) [0] list 
scan (+) [1, 4, 8, 3, 7, 9] 
[0,1,5,13,16,23,32] 

모른다됩니다 : 당신은

let scan f list = foldl (\ xs next -> xs++[f (last xs) next]) [head list] (tail list) 
scan (+) [1, 4, 8, 3, 7, 9] 
[1,5,13,16,23,32]