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?

Never seen go in any Haskell material that I read. Can you give an example/reference? — Ionuț G. Stan
@Ionuț For example, the Yesod book's explanation of the Enumerator package. (Why the Yesod book dedicates so much material to the topic I don't know, but that's beside the point) — Dan Burton
For what it's worth, I've seen many C/C++ programmers who also name their helper functions "go" when they can't think of a better name. — ShreevatsaR
FWIW, explicit tail recursion is the functional version of goto in a lot of ways, including the potential for obfuscation. Static typing and scoping rules help keep the confusion to a minimum, though. And as for choice of the name, I like @Michael Snoyman's answer below about length and suitability. Also, when there's just one helper function its name seems largely irrelevant, so I generally just pick either 'go' or 'loop' because I have to pick something and those both make sense. I tend to prefer 'go' for lazy loops and "loop" for strict ones. — mokus

Don Stewart Don Stewart · Accepted Answer · 2011-04-30T21:52:29

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.

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

3 Answers