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

Question

I see go a lot when reading Haskell material or source, but I've never been really comfortable about it - (I guess it has the negative connotation of "goto" in my mind). I started learning Haskell with LYAH, and that's where I picked up the tendency to use acc and step when writing folds. Where does the convention for writing go come from?

Most importantly, what exactly is the name go supposed to imply?

Answer 1

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