Haskell: why the convention to name a helper function "go"?

haskell, naming-conventions

Solution

Hmm! Some archaeology!

Since around 2004 I've used `go` as the generic name for tail-recursive worker loops, when doing a worker/wrapper transformation of a recursive function. I started using it widely in `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 #-}

was from `bytestring` in August 2005.

This got written up in RWH, and probably was popularized from there. Also, in the stream fusion library, Duncan Coutts and I started doing it a lot.

From the GHC sources

The idiom goes back further though. `foldr` in GHC.Base is given as:

foldr k z = go
      where
         go []     = z
         go (y:ys) = y `k` go ys

which is probably where I picked up the trick (I'd thought this was from Andy Gill's thesis, but can't find any use of `go` there). It isn't given in this form in Gofer, so I think this first appeared in the GHC code base.

By 2001, Simon Marlow was using `go` in some of the systems-level code, so we might place the blame somewhere in GHC, and this clue leads us to the GHC source, where `go` is widely used in worker functions:

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

Digging up old versions of GHC, we see that in GHC 0.29 this idiom does not appear, but by GHC 3.02 series (1998), the `go` idiom appears everywhere. An example, in `Numeric.lhs`, in the definition of `showInt`, dated to 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'
      }}

this is a different implementation to the one given in the H98 report. Digging into the implementation of "Numeric.lhs", however, we find that it isn't the same as the version that was added to GHC 2.06 in 1997, and a very interesting patch from Sigbjorne Finne appears, in April 1998, adding a `go` loop to Numeric.lhs.

This says that at least by 1998, Sigbjorne was adding `go` loops to the GHC "std" library, while simultaneously, many modules in the GHC compiler core had `go` loops. Digging further, this very interesting commit from Will Partain in July 1996 adds a "go" loop into GHC -- the code comes from Simon PJ though!

So I'm going to call this as a Glasgow idiom invented by people at Glasgow who worked on GHC in the mid 90s, such as Simon Marlow, Sigbjorn Finne, Will Partain and Simon Peyton Jones.

Problem

Original source

Related problems

• Performance problem with Euler problem and recursion on Int64 types