Haskell: почему принято называть вспомогательную функцию «go»?

Question

Я вижу go много, когда читаю материал или источник на Haskell, но я никогда не чувствовал себя по-настоящему комфортно - (я думаю, что в моем уме есть отрицательный оттенок "goto")Я начал изучать Haskell с LYAH, и там я обнаружил тенденцию использовать acc и step при написании сгибов.Откуда взято соглашение о написании go?

Самое главное, что именно подразумевается под именем go?

Answer 1

Хм! Немного археологии!

Примерно с 2004 года я использовал go в качестве общего имени для хвостовых рекурсивных рабочих циклов при выполнении преобразования рабочий / упаковщик рекурсивной функции. Я начал широко использовать его в bytestring, например

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 года.

Это было записано в RWH и, вероятно, было популяризировано оттуда. Кроме того, в библиотеке Stream Fusion , Duncan Coutts и я начали это делать.

Из источников GHC

Идиома идет еще дальше. foldr в GHC. База задается как:

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

, вероятно, именно здесь я подхватил трюк (я думал, что это из тезиса Энди Гилла, но не могу найти там никакого смысла go). Это не , данное в этой форме в Gofer, поэтому я думаю, что это впервые появилось в кодовой базе GHC.

К 2001 году Саймон Марлоу использовал go в некоторых кодах системного уровня, поэтому мы могли бы возложить вину где-то в GHC, и эта подсказка приводит нас к источнику GHC , где 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 . Однако, углубившись в реализацию "Numeric.lhs" , мы обнаруживаем, что она отличается от версии, которая была добавлена ​​в GHC 2.06 в 1997 году, и появляется очень интересный патч от Sigbjorne Finne: в апреле 1998 года добавление петли go к Numeric.lhs.

Это говорит о том, что, по крайней мере, к 1998 году Сигбьорн добавил петли go в библиотеку GHC "std", в то время как одновременно многие модули в ядре компилятора GHC имели петли go. Более подробно, этот очень интересный коммит от Will Partain в июле 1996 года добавляет цикл "go" в GHC - хотя код приходит от Simon PJ!

Так что я буду называть это идиомой Глазго , изобретенной людьми из Глазго, работавшими над GHC в середине 90-х годов, такими как Саймон Марлоу , Сигбьёрн Финн , будет разлучен и Саймон Пейтон Джонс .

Answer 2

Очевидно, что ответ Дона правильный.Позвольте мне просто добавить небольшую деталь (поскольку, похоже, это мое письмо, на которое вы непосредственно ссылаетесь): идти хорошо, потому что это только две буквы.Большая часть контента для пакета enumerator связана с тем, что я уже написал трехкомпонентное руководство по enumerator в виде серии постов в блоге, поэтому решил, что я могу также включить его в книгу.Пакет перечислителя используется в нескольких местах по всему Йесоду, поэтому он актуален.

Answer 3

Я ожидаю, что эта идиома будет применима не только к линейным структурам (и, следовательно, к «петлям»), но и к ветвящимся (древовидным) структурам.

Интересно, как часто шаблон go соответствует параметрам накопления и, в более общем плане, стратегиям кодирования с продолжением, которые Митч Ванд исследовал в статье Стратегии трансформации программ на основе продолжения (одна из моих самых любимых работ). В этих случаях функция go имеет особое значение, которое затем можно использовать для получения эффективного кода из элегантной спецификации.