공통 하위 표현식을 식별하기 위해 as-patterns을 사용해야하는시기는 언제입니까?

Question

하스켈에서 (GHC 사용) 특히 데이터 파괴와 관련하여 마이크로 하위 최적화를 어느 정도 최적화해야하는지 궁금합니다.

예를 들어, 두 개의 정렬 된 목록을 병합이 코드를 고려하십시오

merge :: Ord a => [a] -> [a] -> [a] 
merge [] bs = bs 
merge as [] = as 
merge (a:as) (b:bs) = 
    case compare a b of 
    LT -> a : merge as (b:bs) -- (1) 
    EQ -> a : merge as bs 
    GT -> b : merge (a:as) bs -- (2) 

GHC (1)에서 (2)에서 (a:as) 및 (b:bs)는 입력 매개 변수로 동일하다는 것을 인식 할 것인가? 또는, 나는

merge a'@(a:as) b'@(b:bs) = 
    ... 
    LT -> a : merge as b' 
    ... 
    GT -> b : merge a' bs 

그리고 일반적으로

때 GHC 데이터 구조에서의 공통 서브 표현식을 인식 할 수있는 패턴, 예컨대 : "로"를 사용한다 때 내가 도움이 필요합니까?

Answer 1

당신은 최적화없이 컴파일하는 경우가 확실히 페널티 킥대로의 패턴을 사용하지 않는 것입니다,하지만 당신은 다음 코드

module Test where 


merge1 :: Ord a => [a] -> [a] -> [a] 
merge1 [] bs = bs 
merge1 as [] = as 
merge1 (a:as) (b:bs) = case compare a b of 
    LT -> a : merge1 as (b:bs) 
    EQ -> a : merge1 as bs 
    GT -> b : merge1 (a:as) bs 


merge2 :: Ord a => [a] -> [a] -> [a] 
merge2 [] bs = bs 
merge2 as [] = as 
merge2 xs@(a:as) ys@(b:bs) = case compare a b of 
    LT -> a : merge2 as ys 
    EQ -> a : merge2 as bs 
    GT -> b : merge2 xs bs 

-O2 및 -ddump-simpl와

, 이후 현명한 편집이 많이,의 이름 바꾸기를 컴파일하는 경우 변수는 메타 데이터 및 주석, 및 기타 다양한 트릭의 제거 당신은 diffing의 도구를 비교 한 후,이 두 정의 사이의 유일한 차이가 끝에 숫자임을 알려줍니다,

merge2_2 :: Ord a => a -> [a] -> [a] -> [a] 
merge2_2 = \ ordInst x y z -> case z of _ { 
     [] -> (x:y); 
     (w:v) -> case compare ordInst x w of _ { 
      LT -> x : merge2_1 ordInst y w v; 
      EQ -> x : merge2 ordInst y v; 
      GT -> w : merge2_2 ordInst x y v 
     } 
    } 

merge2_1 :: Ord a => [a] -> a -> [a] -> [a] 
merge2_1 = \ ordInst x y z -> case x of _ { 
     [] -> (y:z); 
     (w:v) -> case compare ordInst w y of _ { 
      LT -> w : merge2_1 ordInst v y z; 
      EQ -> w : merge2 ordInst v z; 
      GT -> y : merge2_2 ordInst w v z 
     } 
    } 

merge2 :: Ord a => [a] -> [a] -> [a] 
merge2 = \ ordInst x y -> case x of wild { 
     [] -> y; 
     (w:v) -> case y of _ { 
      [] -> wild; 
      (z:zs) -> case compare ordInst w z of _ { 
       LT -> w : merge2_1 ordInst v z zs; 
       EQ -> w : merge2 ordInst v zs; 
       GT -> z : merge2_2 ordInst w v zs 
      } 
     } 
    } 


merge1_2 :: Ord a => a -> [a] -> [a] -> [a] 
merge1_2 = \ ordInst x y z -> case z of _ { 
     [] -> (x:y); 
     (w:v) -> case compare ordInst x w of _ { 
      LT -> x : merge1_1 ordInst y w v; 
      EQ -> x : merge1 ordInst y v; 
      GT -> w : merge1_2 ordInst x y v 
     } 
    } 

merge1_1 :: Ord a => [a] -> a -> [a] -> [a] 
merge1_1 = \ ordInst x y z -> case x of _ { 
     [] -> (y:z); 
     (w:v) -> case compare ordInst w y of _ { 
      LT -> w : merge1_1 ordInst v y z; 
      EQ -> w : merge1 ordInst v z; 
      GT -> y : merge1_2 ordInst w v z 
     } 
    } 

merge1 :: Ord a => [a] -> [a] -> [a] 
merge1 = \ ordInst x y -> case x of wild { 
     [] -> y; 
     (w:v) -> case y of _ { 
      [] -> wild; 
      (z:zs) -> case compare ordInst w z of _ { 
       LT -> w : merge1_1 ordInst v z zs; 
       EQ -> w : merge1 ordInst v zs; 
       GT -> z : merge1_2 ordInst w v zs 
      } 
     } 
    } 

어떤 식으로 뭔가에 도달 할 수 merge 함수 이름. 따라서 네, 최적화를 적용한 후 GHC는 적어도 목록의 경우 이러한 패턴을 알아낼 수 있습니다. 그러나, 나는 항상 가장자리 사례가 있기 때문에 여전히 그들을 사용하는 것이 좋습니다, 그리고 만약 당신이 그들을 사용하는 다음 컴파일러는 뭔가 복잡한 일을 신뢰하지 않아도됩니다. 또한 최적화가 활성화되지 않은 경우에도 코드에 여전히 최적화가 적용됨을 의미합니다. 작은 변화처럼 보일지 모르지만이 함수가 내부 루프에서 끝나거나 작업중인 구조가 매우 클 경우 성능에 큰 영향을 줄 수 있습니다. 또한 많은 수의 필드가있는 생성자의 경우 "생성 된"형식을 참조하는 이름을 사용하는 것이 더 편리하다는 것을 알았습니다.

Here's the full core dump if you're interested. 기본적으로, 나는 더 적은 공간을 차지하기 위해 함께 라인을 결합한 다음 형식 서명에서 불필요한 노이즈를 제거하고, 정규화 된 모듈 이름을 제거하고, merge2_$smerge2에서 merge2_2과 같은 이름을 바꾼 모든 로컬 형식 시그니처를 제거한 다음 이름 바꾸기를 시작했습니다. Sublime Text의 훌륭한 다중 커서 기능을 사용합니다. 그때, 단지 a에 모두 이름을 변경, 유형 이름으로 시작 x, y, z, w, v에 변수 이름을 이름을 변경하고, zs는 (내가하지?, 창조적 해요)에 :의 모든 응용 프로그램을 만든 연산자 중위, Rec 영역을 제거하고 나중에 몇 가지 스타일링을 추가하여 위에 나온 결과를 얻었습니다.