Рекомендуется ли использовать рекурсивные действия ввода-вывода в хвостовой рекурсивной форме?

Рассмотрим два следующих варианта:

myReadListTailRecursive :: IO [String]
myReadListTailRecursive = go []
    where 
    go :: [String] -> IO [String]   
    go l = do {
                 inp <- getLine;
                 if (inp == "") then 
                     return l;
                 else go (inp:l);
                }

myReadListOrdinary :: IO [String]
myReadListOrdinary = do
        inp <- getLine
        if inp == "" then
            return []
        else
            do
                moreInps <- myReadListOrdinary
                return (inp:moreInps)

В обычных языках программирования можно было бы знать, что рекурсивный вариант хвоста является лучшим выбором.

Однако, пройдя этот ответ, очевидно, что реализация рекурсии haskell не похожа на реализацию повторного стека рекурсии.

Но поскольку в этом случае рассматриваемая программа включает в себя действия и строгую монаду, я не уверен, что применяются те же рассуждения. На самом деле, я думаю, что в случае IO хвостовая рекурсивная форма действительно лучше. Я не уверен, как правильно рассуждать об этом.

EDIT: Дэвид Янг отметил, что самый внешний вызов здесь - (>>=). Даже в этом случае один из этих стилей имеет преимущество перед другим?

Ответ 1

Это действительно не так, как я бы написал это, но его достаточно ясно, что вы делаете. (Кстати, если вы хотите иметь возможность эффективно вставлять произвольный вывод из любой функции в цепочке, не используя монады, вы можете попробовать Data.ByteString.Builder.)

Ваша первая реализация очень похожа на левую складку, а ваша вторая очень похожа на правую складку или карту. (Вы можете попробовать написать их как таковые!) Второй имеет несколько преимуществ для ввода-вывода. Одним из наиболее важных для обработки ввода и вывода является то, что он может быть интерактивным.

Вы заметите, что первый строит весь список извне: чтобы определить, что такое первый элемент списка, программе необходимо вычислить всю структуру, чтобы добраться до самого внутреннего thunk, который равен return l, Сначала программа генерирует всю структуру данных, а затем начинает ее обрабатывать. Это полезно, когда вы сокращаете список, потому что функции хвоста-рекурсии и строгие левые складки эффективны.

Во втором, самый внешний thunk содержит голову и хвост списка, поэтому вы можете схватить хвост, а затем вызвать thunk для создания второго списка. Это может работать с бесконечными списками, и оно может создавать и возвращать частичные результаты.

Вот пример: программа, которая читает по одному целю на строку и печатает суммы до сих пор.

main :: IO ()
main = interact( display . compute 0 . parse . lines )
  where parse :: [String] -> [Int]
        parse [] = []
        parse (x:xs) = (read x):(parse xs)

        compute :: Int -> [Int] -> [Int]
        compute _ [] = []
        compute accum (x:xs) = let accum' = accum + x
                               in accum':(compute accum' xs)

        display = unlines . map show

Если вы запустите это в интерактивном режиме, вы получите что-то вроде:

Но вы также можете написать compute tail-recursively, с накопительным параметром:

main :: IO ()
main = interact( display . compute [] . parse . lines )
  where parse :: [String] -> [Int]
        parse = map read

        compute :: [Int] -> [Int] -> [Int]
        compute xs [] = reverse xs
        compute [] (y:ys) = compute [y] ys
        compute (x:xs) (y:ys) = compute (x+y:x:xs) ys

        display = unlines . map show

Это искусственный пример, но строгие левые складки - общий шаблон. Если, однако, вы пишете compute или parse с накопительным параметром, это то, что вы получаете, когда пытаетесь запустить интерактивно, и нажмите EOF (control-D в Unix, control-Z в Windows) после номера 4:

Эта левая версия должна вычислять всю структуру данных, прежде чем она сможет ее прочитать. Это не работает в бесконечном списке (когда вы достигнете базового случая? Как бы вы даже отменили бесконечный список, если бы вы это сделали?) И приложение, которое не может отвечать на ввод пользователя, пока оно не завершится, является нарушителем сделки.

С другой стороны, хвосто-рекурсивная версия может быть строгой в своем накопительном параметре и будет работать более эффективно, особенно когда ее не потребляют немедленно. Он не должен содержать любые трюки или контекст, отличные от его параметров, и он может даже повторно использовать один и тот же стек стека. Строгая функция накопления, такая как Data.List.foldl', является отличным выбором, когда вы уменьшаете список до значения, а не стройте список результатов с высокой степенью точности. Такие функции, как sum, product или any, не могут возвращать какое-либо полезное промежуточное значение. Сначала они должны закончить вычисление, а затем вернуть окончательный результат.

Ответ 2

FWIW, я бы пошел на существующие монадические комбинаторы и сосредоточился на удобочитаемости/необходимости. Используя unfoldM :: Monad m => m (Maybe a) -> m [a]:

import Control.Monad (liftM, mfilter)
import Control.Monad.Loops (unfoldM)

myReadListTailRecursive :: IO [String]
myReadListTailRecursive = unfoldM go
  where
    go :: IO (Maybe String)
    go = do
        line <- getLine
        return $ case line of
            "" -> Nothing
            s -> Just s

Или используя MonadPlus экземпляр Maybe, mfilter :: MonadPlus m => (a -> Bool) -> m a -> m a:

myReadListTailRecursive :: IO [String]
myReadListTailRecursive = unfoldM (liftM (mfilter (/= "") . Just) getLine)

Другим, более универсальным вариантом может быть использование LoopT.