같은 목록에서 두 개의 맵을 어떻게 융합시킬 수 있습니까?

우리는 자동으로 융합 이런 종류의 수행에 어떤 reasearch이 거기에 너무같은 목록에서 두 개의 맵을 어떻게 융합시킬 수 있습니까?

unzip (map (\x -> (f x, g x)) xs)

처럼 표현

(map f xs, map g xs)

의 목록 xs 이상이 순회를 융합 수 있을까?

는 (반환 된 목록 중 하나가 다른 전에 섭취하면 여기에 공간의 누출을 만들 위험이있다 나는 공간을 절약보다 xs을 통해 여분의 통과를 방지에 더 관심이 있어요..)

편집 : unzip이 소비자와 융합 될 수 있는지에 따라이 변환이 의미가 없을 수도있는 실제 메모리 내 하스켈 목록에 융합을 실제로 적용하려고하지 않습니다. 나는 unzip이 융합 할 수있는 환경을 가지고 있습니다 ("FlumeJava : 쉽고 효율적인 데이터 병렬 파이프 라인"참조).

출처

2012-09-03 tibbe

어쨌든 자동은 아니지만 꽤 좋음 : http://squing.blogspot.com/2008/11/beautiful-folding.html –

이 결과가 다른 것으로 융합되지 않는 한 쌍을 만들고 압축을 풀 때 발생하는 오버 헤드가 여분의 순회 비용보다 크다. – augustss

@augustss 탐색이 거대한 파일을 넘지 않는다면! 나는 이것을 실제 목록에 적용 할 계획이 아닙니다. – tibbe

또한 완전 자동이 아니지만 GHC에 이와 같은 다시 쓰기 규칙 목록을 제공 할 수 있습니다. 7.14 Rewrite rules 및 Using rules을 참조하십시오. 그런 다음 컴파일러는 이러한 규칙을 사용하여 컴파일 할 때 프로그램을 최적화합니다. (결코 검사에서 컴파일러 규칙은 어떤 의미가있는 경우 있습니다.)

편집 :이 특정 문제에 대한 예를 제공하기 위해, 우리는 쓸 수 있습니다 :

{-# OPTIONS_GHC -fenable-rewrite-rules -ddump-rule-firings -ddump-rule-rewrites #-} 

import Data.Char 

{-# RULES 
"map/zip" forall f g xs. (,) (map f xs) (map g xs) = unzip (map (\x -> (f x, g x)) xs) 
    #-} 

main :: IO() 
main = let x = "abCD" in 
     print $ (,) (map toUpper x) (map toLower x)

(최상위을 규칙의 함수 이름은 (,) :: a -> b -> (a, b)입니다. 컴파일 할 때 규칙이 적용되는 방법을 알 수 있습니다. 옵션 dump-rule-firings은 규칙이 적용될 때 메시지를 표시하고 -ddump-rule-rewrites은 각 규칙 응용 프로그램을 자세히 표시합니다 (7.14.6. Controlling what's going on in rewrite rules 참조).

요제프 Svenningsson :

출처

2012-09-03 07:35:00

이러한 종류의 표현에 일치하는 규칙을 작성할 수 있다고 생각하지 않습니다. GHC 규칙은 함수 이름으로 시작해야합니다. – tibbe

나는 적어도 잠시 융합 (명사에 붙여서의 뜻을 나타냄)를 언급 기능처럼 압축이 자원을 찾기 위해 관리했습니다. "매개 변수 & 우편과 같은 기능을 축적하기위한 바로 가기 퓨전" http://www.cse.chalmers.se/~josefs/publications/fusion.pdf

던컨 쿠츠. "스트림 융합 : 유도 성 서열 유형에 대한 실용적인 지름길 융합" https://community.haskell.org/~duncan/thesis.pdf

아무도이 유형의 "형제 융합"을 명시 적으로 언급하지 않습니다.

출처

2012-09-03 17:10:34 tibbe

나는이 프리젠 테이션을 보지 못했지만 [TupleFusion] (http://wiki.portal.chalmers.se/cse/uploads/FP/Josef_TupleFusion.pdf)에 대한 Josef의 슬라이드가 있습니다. – danr

[자동화 된 튜플 전략으로] (http://dl.acm.org/citation.cfm?id=154643)이 흥미로울 수 있습니다. –

같은 목록에서 두 개의 맵을 어떻게 융합시킬 수 있습니까?

답변

관련 문제