Haskell: GHC optimisera-t-il cela?

Question

Est-ce que GHC peut simplifier id = (\(a, b) -> (a, b)).(\(a, b) -> (a, b)) en id = \(a, b) -> (a, b)?

Qu'en est-cas plus compliqué:

id (Just x) = Just x 
id Nothing = Nothing 

map f (Just x) = Just (f x) 
map _ Nothing = Nothing 

va simplifier GHC id . map en map?

J'ai essayé d'utiliser la réduction bêta simple, mais il semble que ces termes soient irréductibles en raison de l'appariement de modèle méchant. Par conséquent, je suis curieux de savoir comment les techniques d'optimisation de GHC traitent cela.

Answer 1

Vous pouvez poser ces questions de ghc en l'exécutant avec -ddump-simpl. Cela entraînera ghc à vider le code "noyau" dans lequel il compile les programmes. Core est un langage intermédiaire entre la partie du compilateur qui raisonne sur le code Haskell et la partie du compilateur qui transforme ce code en code machine.

Lorsque j'ai compilé ce qui suit avec -O2 -ddump-simpl les résultats m'ont surpris.

tupid1 :: (a, b) -> (a, b) 
tupid1 = (\(a, b) -> (a, b)) 

tupid2 :: (a, b) -> (a, b) 
tupid2 = (\(a, b) -> (a, b)) . (\(a, b) -> (a, b)) 

Le cœur résultant pour tupid1 crée une nouvelle fonction d'identité spécialisée. Dans le noyau, les arguments de type polymorphes aux fonctions sont représentés comme des arguments explicites. tupid1 prend deux de ces arguments de type, nommés a_ayd et b_aye, pour les deux variables de type a et b dans sa signature. Il faut aussi un terme ds_dIl qui a le type d'un tuple de ces deux types (ds_dIl :: (a_ayd, b_aye)) et le retourne non modifié.

Le résultat surprenant est tupid2 ...

-- RHS size: {terms: 1, types: 0, coercions: 0} 
tupid2 :: forall a_aqm b_aqn. (a_aqm, b_aqn) -> (a_aqm, b_aqn) 
[GblId, 
Arity=1, 
Caf=NoCafRefs, 
Str=DmdType <S,1*U(U,U)>m, 
Unf=Unf{Src=InlineStable, TopLvl=True, Value=True, ConLike=True, 
     WorkFree=True, Expandable=True, 
     Guidance=ALWAYS_IF(arity=1,unsat_ok=True,boring_ok=True) 
     Tmpl= \ (@ a_axZ) (@ b_ay0) (x_aIw [Occ=Once] :: (a_axZ, b_ay0)) -> 
       x_aIw}] 
tupid2 = tupid1 

... ce qui simplifie GHC à tupid1! Comment il déduit cela est au-delà de ma connaissance immédiate ou de ma capacité à découvrir.

---

L'exemple d'identité pour Maybe

maybeid :: Maybe a -> Maybe a 
maybeid (Just x) = Just x 
maybeid Nothing = Nothing 

est également simplifiée à une fonction d'identité sans motif assortit

-- RHS size: {terms: 3, types: 4, coercions: 0} 
maybeid :: forall a_aqn. Maybe a_aqn -> Maybe a_aqn 
[GblId, 
Arity=1, 
Caf=NoCafRefs, 
Str=DmdType <S,1*U>, 
Unf=Unf{Src=InlineStable, TopLvl=True, Value=True, ConLike=True, 
     WorkFree=True, Expandable=True, 
     Guidance=ALWAYS_IF(arity=1,unsat_ok=True,boring_ok=True) 
     Tmpl= \ (@ a_aqI) (ds_dIq [Occ=Once] :: Maybe a_aqI) -> ds_dIq}] 
maybeid = \ (@ a_aqI) (ds_dIq :: Maybe a_aqI) -> ds_dIq 

Le noyau de map pour Maybe est pas intéressant pour cette question

maybemap :: (a -> b) -> Maybe a -> Maybe b 
maybemap f (Just x) = Just (f x) 
maybemap _ Nothing = Nothing 

Mais si elle est composée de maybeid

maybeidmap :: (a -> b) -> Maybe a -> Maybe b 
maybeidmap f = maybeid . maybemap f 

GHC simplifie à maybemap

-- RHS size: {terms: 1, types: 0, coercions: 0} 
maybeidmap 
    :: forall a_aqp b_aqq. 
    (a_aqp -> b_aqq) -> Maybe a_aqp -> Maybe b_aqq 
[GblId, 
Arity=2, 
Caf=NoCafRefs, 
Str=DmdType <L,1*C1(U)><S,1*U>, 
Unf=Unf{Src=InlineStable, TopLvl=True, Value=True, ConLike=True, 
     WorkFree=True, Expandable=True, 
     Guidance=ALWAYS_IF(arity=0,unsat_ok=True,boring_ok=True) 
     Tmpl= maybemap}] 
maybeidmap = maybemap 

Et il fait la même chose si id est composé de f.

maybemapid :: (a -> b) -> Maybe a -> Maybe b 
maybemapid f = maybemap (id . f) 

La composition de la fonction identité est éliminé et la fonction de l'ensemble simplifie maybemap

-- RHS size: {terms: 1, types: 0, coercions: 0} 
maybemapid 
    :: forall a_aqq b_aqr. 
    (a_aqq -> b_aqr) -> Maybe a_aqq -> Maybe b_aqr 
[GblId, 
Arity=2, 
Caf=NoCafRefs, 
Str=DmdType <L,1*C1(U)><S,1*U>, 
Unf=Unf{Src=InlineStable, TopLvl=True, Value=True, ConLike=True, 
     WorkFree=True, Expandable=True, 
     Guidance=ALWAYS_IF(arity=2,unsat_ok=True,boring_ok=False) 
     Tmpl= \ (@ a_ar2) 
       (@ b_ar3) 
       (f_aqL [Occ=Once!] :: a_ar2 -> b_ar3) 
       (eta_B1 [Occ=Once!] :: Maybe a_ar2) -> 
       case eta_B1 of _ [Occ=Dead] { 
        Nothing -> GHC.Base.Nothing @ b_ar3; 
        Just x_aqJ [Occ=Once] -> GHC.Base.Just @ b_ar3 (f_aqL x_aqJ) 
       }}] 
maybemapid = maybemap