폴드가있는 최적화

Question

폴드가있는 (일차 다형성 만있는) 최적화가 있는지 궁금합니다.

지도의 경우 산림 벌채가 있습니다 : map g (map f ls) => map (g . f) ls 및 rev (map f ls) => rev_map f ls (Ocaml이 빠름).

하지만 폴드가 너무 강력합니다. 최적화를 거스르는 것처럼 보입니다.

Answer 1

명백한 것들 :

fold_left f acc (List.map g li) => fold_left (fun acc x -> f acc (g x)) acc li 
fold_right f li acc => fold_left f acc li (* if (f,acc) is a monoid *) 

당신은 주제, "바나나, 렌즈, 봉투 및 철조망과 기능 프로그래밍"에 대한 고전적인 종이에 관심이있을 수 있습니다. 그러나 기술적이며 꿰 뚫을 수없는 표기법을주의하십시오.

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.41.125

편집 : 첫 번째 규칙의 첫 버전은 빈센트 - hugot에 편집 덕분에 잘못이었다.

Answer 2

폴드시 산림 벌채를 사용할 수 있습니다. 실제로 fusion은 특별한 경우입니다.

foldr c n (build g) == g c n 

: 우리는 다음과 같은 등가가 foldr

foldr :: (a -> b -> b) -> b -> [a] -> b 
foldr c n []  = n 
foldr c n (x:xs) = c x (foldr c n xs) 

의 표준 정의를 사용하여, 지금

build :: (forall b. (a -> b -> b) -> b -> b) -> [a] 
build g = g (:) [] 

:

비결은 특별한 build 기능에 의해 목록 건설을 대체하는 것입니다

(실제로 이는 특정 경우에만 해당됩니다. , 그러나 일반적인 상황. 자세한 내용은 "Correctness of short-cut fusion"을 참조하십시오.

당신이 (map 포함) foldr를 사용 build하고 소비자를 사용하여 목록을 생성하는 함수를 작성하는 경우, 위의 평등은 대부분 중간 목록을 제거 할 수 있습니다. 하스켈의 목록 내포는 build과 foldr의 조합으로 번역됩니다.

이 접근법의 단점은 왼쪽 접기를 처리 할 수 ​​없다는 점입니다. 그래도 Stream Fusion이 처리됩니다. 그것은리스트 프로듀서와 트랜스 포머를 스트림 (coinductive datatypes, iterators와 같은 종류)으로 표현합니다. 위의 논문은 매우 읽기 쉽기 때문에 한번 보시기 바랍니다.

gasche가 언급 한 "바나나"논문은 접힌 종이와 그 등가물의 종류에 대해 자세히 설명합니다.

마지막으로 Bird and Moor 's "Algebra of Programming"이 있으며 여기에는 combining two folds into one과 같은 변형이 포함됩니다.

Answer 3

이론에 대해 좀 더 자세히 알고 싶다면 catamorphisms, anamorphisms 및 hylomorphisms에 대해 읽어 보시기 바랍니다. 그것을 둘러싼 범주 이론이 다소 무서운 것처럼 보일 수 있지만 개념은 그리 어렵지 않습니다.

catamorphisms는 을 사용하여 재귀적인 데이터 구조를 사용하고 어떤 종류의 값을 생성합니다.아나모 피어 즈 (Anamorphisms)는 어떤 값 (시드의 일종) 이 주어진 경우에 재귀 데이터 구조 인을 생성하는 함수입니다. 특히, 다른 anwers에서 언급 된 foldr과 build은 목록에 변형과 anamorphism을 구축하는 기능입니다. 그러나이 개념은 기본적으로 다른 종류의 나무와 같은 반복적 인 데이터 구조에 적용될 수 있습니다.

이제 anamorphism을 가진 재귀 적 데이터 구조를 만들고 catamorphism으로 소비하면, hylomorphism. 이 경우 실제로는 중간 구조가 필요하지 않습니다. 당신은 그것을 창조하고 그것을 파괴하는 것을 건너 뛸 수 있습니다. 이를 종종 deforestation이라고합니다. map에 관한

---

:이 기능은 그것이 catamorphism 및 모두 있다는 흥미있는 anamorphism :

• map이 목록을 소비하고 무언가를 생산; 또한
• map은 뭔가를 소비하면서 목록을 생성합니다.

그래서 당신은 hylomorphism를 형성하는 두 개의 맵합니다 catamorphism (map f)과 anamorphism (map g)의 조성 map f . map g의 구성을 볼 수 있습니다. 따라서 중간 목록을 만들지 않아도 최적화 할 수 있습니다 (deforest).

은 구체적으로 : 당신은 map 두 가지의 방법, 하나 foldr를 사용 build을 사용하여 다른 작성할 수

mapAna :: (a -> b) -> [a] -> [b] 
mapAna f xs = build (mapAna' f xs) 

mapAna' :: (a -> b) -> [a] -> (b -> c -> c) -> c -> c 
mapAna' f []  cons nil = nil 
mapAna' f (x : xs) cons nil = (f x) `cons` (mapAna' f xs cons nil) 


mapCata :: (a -> b) -> [a] -> [b] 
mapCata f xs = foldr (\x ys -> f x : ys) [] xs 

및 mapCata f (mapAna g zs)로 구성 map f (map g zs)을하는 일부 단순화 후 map (f . g)에 foldr c n (build g) == g c n 결과를 적용.