链接Haskell函数的数据类型

Question

可以说我有以下内容:

data FuncAndValue v res = FuncAndValue (v -> res) v

chain :: (res -> new_res) -> FuncAndValue v res -> FuncAndValue v new_res
chain new_f (FuncAndValue old_f v) = FuncAndValue (new_f . old_f) v  

被GHC可能能够结合功能new_f并old_f通过内联成一个单一的功能？

基本上,以数据类型存储函数无论如何都会抑制优化.

我希望GHC能够轻松地将函数链组合成一个(即所以我的结构上的"总和"不涉及重复调用代表的thunk,(+)而只是内联,(+)因此它像for循环一样运行.我希望将函数存储在数据类型中,然后稍后访问它们不会抑制它.

Answer 1

GHC 是否能够通过内联将函数组合new_f成old_f单个函数？

是的，如果它能在没有干预的情况下做同样的事情的话FuncAndValue。当然，函数的展开必须可用，否则就没有任何内联的机会。但如果有机会的话，将函数包装在 a 中FuncAndValue几乎没有什么区别（如果有的话）。

但让我们问问 GHC 本身。首先是类型和一个非常简单的chaining：

module FuncAndValue where

data FuncAndValue v res = FuncAndValue (v -> res) v

infixr 7 `chain`

chain :: (res -> new_res) -> FuncAndValue v res -> FuncAndValue v new_res
chain new_f (FuncAndValue old_f v) = FuncAndValue (new_f . old_f) v

apply :: FuncAndValue v res -> res
apply (FuncAndValue f x) = f x

trivia :: FuncAndValue Int (Int,Int)
trivia = FuncAndValue (\x -> (2*x - 1, 3*x + 2)) 1

composed :: FuncAndValue Int Int
composed = chain (uncurry (+)) trivia

和（有趣的部分）我们得到的核心是trivia和composed：

FuncAndValue.trivia1 =
  \ (x_af2 :: GHC.Types.Int) ->
    (case x_af2 of _ { GHC.Types.I# y_agp ->
     GHC.Types.I# (GHC.Prim.-# (GHC.Prim.*# 2 y_agp) 1)
     },
     case x_af2 of _ { GHC.Types.I# y_agp ->
     GHC.Types.I# (GHC.Prim.+# (GHC.Prim.*# 3 y_agp) 2)
     })

FuncAndValue.composed2 =
  \ (x_agg :: GHC.Types.Int) ->
    case x_agg of _ { GHC.Types.I# y_agp ->
    GHC.Types.I#
      (GHC.Prim.+#
         (GHC.Prim.-# (GHC.Prim.*# 2 y_agp) 1)
         (GHC.Prim.+# (GHC.Prim.*# 3 y_agp) 2))
    }

内联足够公平，(.)看不到。来自 的两个casestrivia已连接在一起，因此我们只有一个composed。除非有人教 GHC 足够的代数来简化\x -> (2*x-1) + (3*x+2)为\x -> 5*x + 1，否则就如您所希望的那样好。即使在单独的模块中，也apply composed可以减少到编译时。6

但这很简单，让我们来解决一个更难的问题。

的可内联版本until（当前的定义until是递归的，因此 GHC 不会内联它），

module WWUntil where

wwUntil :: (a -> Bool) -> (a -> a) -> a -> a
wwUntil p f = recur
  where
    recur x
        | p x       = x
        | otherwise = recur (f x)

另一个简单的功能是它自己的模块，

collatzStep :: Int -> Int
collatzStep n
    | n .&. 1 == 0  = n `unsafeShiftR` 1
    | otherwise     = 3*n + 1

最后是坚果

module Hailstone (collatzLength, hailstone) where

import FuncAndValue
import CollatzStep
import WWUntil

data P = P {-# UNPACK #-} !Int {-# UNPACK #-} !Int

fstP :: P -> Int
fstP (P x _) = x

sndP :: P -> Int
sndP (P _ y) = y

hailstone :: Int -> FuncAndValue Int Int
hailstone n = sndP `chain` wwUntil ((== 1) . fstP) (\(P n k) -> P (collatzStep n) (k+1))
                   `chain` FuncAndValue (\x -> P x 0) n

collatzLength :: Int -> Int
collatzLength = apply . hailstone

我通过使用严格对对严格分析器有所帮助。对于香草，(,)第二个组件将在每个步骤中添加 1 后被拆箱并重新装箱，我只是无法忍受这种浪费；）但除此之外没有相关的区别。

并且（有趣的部分）核心 GHC 生成：

Rec {
Hailstone.$wrecur [Occ=LoopBreaker]
  :: GHC.Prim.Int#
     -> GHC.Prim.Int# -> (# GHC.Prim.Int#, GHC.Prim.Int# #)
[GblId, Arity=2, Caf=NoCafRefs, Str=DmdType LL]
Hailstone.$wrecur =
  \ (ww_sqq :: GHC.Prim.Int#) (ww1_sqr :: GHC.Prim.Int#) ->
    case ww_sqq of wild_Xm {
      __DEFAULT ->
        case GHC.Prim.word2Int#
               (GHC.Prim.and# (GHC.Prim.int2Word# wild_Xm) (__word 1))
        of _ {
          __DEFAULT ->
            Hailstone.$wrecur
              (GHC.Prim.+# (GHC.Prim.*# 3 wild_Xm) 1) (GHC.Prim.+# ww1_sqr 1);
          0 ->
            Hailstone.$wrecur
              (GHC.Prim.uncheckedIShiftRA# wild_Xm 1) (GHC.Prim.+# ww1_sqr 1)
        };
      1 -> (# 1, ww1_sqr #)
    }
end Rec }

lvl_rsz :: GHC.Types.Int -> GHC.Types.Int
[GblId, Arity=1, Caf=NoCafRefs]
lvl_rsz =
  \ (x_iog :: GHC.Types.Int) ->
    case x_iog of _ { GHC.Types.I# tpl1_B4 ->
    case Hailstone.$wrecur tpl1_B4 0 of _ { (# _, ww2_sqH #) ->
    GHC.Types.I# ww2_sqH
    }
    }

而这正是你没有得到的FuncAndValue。一切都很好地内嵌，一个美丽的紧密循环。

基本上，在数据类型中存储函数是否会抑制优化。

如果将函数包装在足够多的层下，是的。但对于其他值来说也是一样的。