패턴 매칭의 퍼포먼스

Question

나는 Learn you a Haskell을 읽고 있는데, 특히 패턴 매칭에 관한 장이다.

length' :: (Num b) => [a] -> b 
length' [] = 0 
length' (_:xs) = 1 + length' xs 

내 질문은 재귀의 순서를 반전 것입니다 상당한 성능 향상을 보여 (기본 케이스를 넣고 배치하여) : 다음은리스트의 길이를 계산하기위한 튜토리얼에 제시된 코드는?

length' :: (Num b) => [a] -> b 
length' (_:xs) = 1 + length' xs 
length' [] = 0 

Answer 1

아니요, 성능 향상은 전혀 없습니다. 두 경우 모두 컴파일러는 WHNF에 대한 인수를 평가하여 빈 목록인지 여부를 확인해야합니다.

사실,이 함수는 컴파일하는 동안 완전히 작성한 코드와 완전히 다른 가능성이 있습니다 (최적화로 컴파일했다고 가정 할 때).

( 최적화없이 를 컴파일) 생성 된 핵심 상대 :

(letrec { 
    f1_aLn [Occ=LoopBreaker] :: [Integer] -> Integer 
    [LclId, Arity=1, Str=DmdType] 
    f1_aLn = 
    \ (ds_d1gX :: [Integer]) -> 
     case ds_d1gX of _ [Occ=Dead] { 
     [] -> fromInteger @ Integer GHC.Num.$fNumInteger 0; 
     : ds1_d1h4 xs_at0 -> 
      + @ Integer 
      GHC.Num.$fNumInteger 
      (fromInteger @ Integer GHC.Num.$fNumInteger 1) 
      (f1_aLn xs_at0) 
     }; } in 
f1_aLn (enumFromTo @ Integer GHC.Enum.$fEnumInteger 1 100)) 

(letrec { 
    f2_aBk [Occ=LoopBreaker] :: [Integer] -> Integer 
    [LclId, Arity=1, Str=DmdType] 
    f2_aBk = 
    \ (ds_d1gP :: [Integer]) -> 
     case ds_d1gP of _ [Occ=Dead] { 
     [] -> fromInteger @ Integer GHC.Num.$fNumInteger 0; 
     : ds1_d1gW xs_aBh -> 
      + @ Integer 
      GHC.Num.$fNumInteger 
      (fromInteger @ Integer GHC.Num.$fNumInteger 1) 
      (f2_aBk xs_aBh) 
     }; } in 
f2_aBk (enumFromTo @ Integer GHC.Enum.$fEnumInteger 1 100)) 

우리는 컴파일러가 해당 문장을 생성하고 있음을 알 수 있습니다. 순서가 문제가 모두하지 않습니다,

main = do 
     print $ f1 [1..100] 
     print $ f2 [1..100] 

f1 [] = 0 
f1 (_:xs) = 1 + f1 xs 
f2 (_:xs) = 1 + f2 xs 
f2 [] = 0 

는 두 건으로 ghc -ddump-simpl file.hs

Answer 2

컴파일 : 그냥 참고로,이 코드이었다. 세 개의 사례의 경우 주문은 성능에 영향을 미치지 않지만 코드를 단순화 할 수 있습니다. 예를 들어 비어 있거나 싱글 톤 목록과 거의 같은 기능을하지만 두 개 이상의 항목이있는 목록에서 되풀이되는 함수가 있다고 가정 해보십시오. 먼저 더 복잡한 일을 처리하여 두 건으로이를 줄일 수,

foo [] = [] 
foo [x] = [x] 
foo (x:y:rest) = x+y : foo (y:rest) 

또는 : 당신은 간단한 가장 복잡한에 패턴을 쓸 수

foo (x:y:rest) = x+y : foo (y:rest) 
foo short = short 

짧은 경우 모두에 대한 foo = id입니다.