唔!一些考古学!
大约从 2004 年开始我就开始使用go
作为尾递归工作循环的通用名称,在对递归函数进行工作/包装转换时。我开始广泛使用它bytestring
, e.g.
foldr :: (Word8 -> a -> a) -> a -> ByteString -> a
foldr k v (PS x s l) = inlinePerformIO $ withForeignPtr x $ \ptr ->
go v (ptr `plusPtr` (s+l-1)) (ptr `plusPtr` (s-1))
where
STRICT3(go)
go z p q | p == q = return z
| otherwise = do c <- peek p
go (c `k` z) (p `plusPtr` (-1)) q -- tail recursive
{-# INLINE foldr #-}
来自bytestring
2005年8月。
这个写下来了in RWH http://book.realworldhaskell.org/read/profiling-and-optimization.html#id678845,并且可能是从那里开始流行的。还,在流融合中 http://hackage.haskell.org/packages/archive/stream-fusion/0.1.2.2/doc/html/src/Data-List-Stream.html#foldl1图书馆、邓肯·库茨和我开始经常这样做。
来自 GHC 来源
这个习语的历史可以追溯到更远的时候。foldr在 GHC.Base 中 http://www.haskell.org/ghc/docs/7.0.3/html/libraries/base-4.3.1.0/src/GHC-Base.html#foldr给出为:
foldr k z = go
where
go [] = z
go (y:ys) = y `k` go ys
这可能就是我学到这个技巧的地方(我以为这是来自安迪·吉尔的论文,但找不到任何用途go
那里)。它isn'tGofer 中以这种形式给出,所以我认为这首先出现在 GHC 代码库中。
到 2001 年,西蒙·马洛 (Simon Marlow) 使用go
在一些系统级代码中,所以我们可能将责任归咎于 GHC 中的某个地方,这条线索引导我们GHC 来源 http://www.haskell.org/ghc/docs/6.12.2/html/libraries/ghc-6.12.2/src/CoreToStg.html#myCollectBinders, where go
广泛应用于工作者函数:
myCollectBinders expr
= go [] expr
where
go bs (Lam b e) = go (b:bs) e
go bs e@(Note (SCC _) _) = (reverse bs, e)
go bs (Cast e _) = go bs e
go bs (Note _ e) = go bs e
go bs e = (reverse bs, e)
GHC 3.02 和格拉斯哥
挖掘GHC的旧版本,我们发现在GHC 0.29中这个习惯用法没有出现,但是到了GHC 3.02系列(1998),go
成语随处出现。一个例子,在Numeric.lhs
,在定义中showInt
,日期为 1996 年至 1997 年:
showInt n r
| n < 0 = error "Numeric.showInt: can't show negative numbers"
| otherwise = go n r
where
go n r =
case quotRem n 10 of { (n', d) ->
case chr (ord_0 + fromIntegral d) of { C# c# -> -- stricter than necessary
let
r' = C# c# : r
in
if n' == 0 then r' else go n' r'
}}
这是与之前不同的实现H98报告中给出 http://www.haskell.org/onlinereport/numeric.html。深入贯彻落实“数字.lhs” https://github.com/ghc/ghc/commits/master/ghc/lib/std/Numeric.lhs然而,我们发现它与 1997 年添加到 GHC 2.06 的版本并不相同,并且在 1998 年 4 月出现了来自 Sigbjorne Finne 的一个非常有趣的补丁,添加一个go循环到 Numeric.lhs。 https://github.com/ghc/ghc/commit/009527af27c8ee36a59db4d451e7c7a9896cb1da#ghc/lib/std/Numeric.lhs
这表明至少到 1998 年,Sigbjorne 才添加了go
循环到 GHC“std”库,同时,许多GHC 编译器核心中的模块 https://github.com/ghc/ghc/blob/0065d5ab628975892cea1ec7303f968c3338cbe1/compiler/coreSyn/CoreSyn.lhs had go
循环。进一步挖掘,这Will Parttain 在 1996 年 7 月的非常有趣的提交在 GHC 中添加了一个“go”循环 https://github.com/ghc/ghc/commit/12899612693163154531da3285ec99c1c8ca2226#L6R413