Haskell:GHC会优化这一点吗?

Question

GHC可以将id = ((a, b) -> (a, b)).((a, b) -> (a, b))简化为id = (a, b) -> (a, b)吗？

更复杂的情况呢：

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

全康会把id . map简化为map吗？

我尝试使用普通的 beta 缩减，但由于令人讨厌的模式匹配，这些术语似乎是不可简化的。

因此，我很好奇GHC的优化技术如何处理这个问题。

Answer 1

您可以通过使用-ddump-simpl运行 ghc 来询问这些问题。这将导致 ghc 转储它编译程序的"核心"代码。核心是编译器中解释Haskell代码的部分和编译器中将该代码转换为机器代码的部分之间的中间语言。

当我用-O2 -ddump-simpl编译以下内容时，结果让我感到惊讶。

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

生成的tupid1核心构成了一个新的专用标识函数。

-- RHS size: {terms: 4, types: 7, coercions: 0}
tupid1 :: forall a_aqo b_aqp. (a_aqo, b_aqp) -> (a_aqo, b_aqp)
[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_ayd)
(@ b_aye)
(ds_dIl [Occ=Once] :: (a_ayd, b_aye)) ->
ds_dIl}]
tupid1 =  (@ a_ayd) (@ b_aye) (ds_dIl :: (a_ayd, b_aye)) -> ds_dIl

在核心中，函数的多态类型参数表示为显式参数。tupid1接受其中两个类型参数，分别名为a_ayd和b_aye，用于签名中a和b的两个类型变量。它还需要一个具有这两种类型元组类型的项ds_dIl(ds_dIl :: (a_ayd, b_aye))并返回它而不修改。

令人惊讶的结果是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

。哪个GHC简化为tupid1！它如何推断这一点超出了我的直接知识或发现能力。

---

Maybe的标识示例

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

也简化为没有模式匹配的恒等函数

-- 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

mapMaybe的核心对这个问题并不有趣

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

但如果它是由maybeid组成的

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

GHC将其简化为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

如果id由f组成，它会做同样的事情。

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

删除了带有恒等函数的组合，整个函数简化为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