Haskell, Monads, Stack Space, Laziness - как структурировать код, чтобы быть ленивым?

Question

Придуманный пример, но приведенный ниже код демонстрирует класс проблем, с которыми я сталкиваюсь, изучая Haskell.

import Control.Monad.Error
import Data.Char (isDigit)

countDigitsForList [] = return []
countDigitsForList (x:xs) = do
    q  <- countDigits x
    qs <- countDigitsForList xs
    return (q:qs)

countDigits x = do
    if all isDigit x
        then return $ length x
        else throwError $ "Bad number: " ++ x

t1 = countDigitsForList ["1", "23", "456", "7890"] :: Either String [Int]
t2 = countDigitsForList ["1", "23", "4S6", "7890"] :: Either String [Int]

t1 дает мне правильный ответ, а t2 правильно определяет ошибку.

Мне кажется, что для достаточно длинного списка этот код будет исчерпывать пространство стека, потому что он выполняется внутри монады, и на каждом шаге он пытается обработать остальную часть списка перед возвратомрезультат.

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

Как структурировать код такого типа втот, который не будет иметь проблемы с пространством стека и / или будет ленивым?

Answer 1

Как мне структурировать такой код в код, который не будет иметь проблем с пространством стека и / или будет ленивым?

Вы не можете заставить эту функцию обрабатывать списоклениво, монады или нет.Вот прямой перевод countDigitsForList для использования сопоставления с шаблоном вместо do обозначения:

countDigitsForList [] = return []
countDigitsForList (x:xs) = case countDigits x of
    Left e  -> Left e
    Right q -> case countDigitsForList xs of
                   Left e   -> Left e
                   Right qs -> Right (q:qs)

Здесь должно быть легче увидеть это, потому что Left в любой точке списка делаетвсе это возвращает значение, чтобы определить самый внешний конструктор результата, весь список должен быть пройден и обработан;аналогично для обработки каждого элемента.Поскольку окончательный результат потенциально зависит от последнего символа в последней строке, эта записанная функция является строго присущей , очень похоже на суммирование списка чисел.

Учитывая, что нужно сделатьУбедитесь, что функция строгая достаточно , чтобы избежать создания огромного неоцененного выражения.Хорошее место, чтобы начать для информации об этом - обсуждения разницы между foldr, foldl и foldl'.

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

И то и другое не нужно, если вместо этого вы можете лениво генерировать, обрабатывать и использовать список;самый простой пример здесь map.Для функции, где это невозможно, строго определенная хвостовая рекурсия - именно то, что вам нужно.

Answer 2

Camccann прав, что эта функция по своей сути строгая. Но это не значит, что он не может работать в постоянном стеке!

countDigitsForList xss = go xss []
    where go (x:xs) acc = case countDigits x of
                             Left e -> Left e
                             Right q -> go xs (q:acc)
          go [] acc = reverse acc

Эта версия накопительного параметра является частичным преобразованием в cps кода camccann, и я уверен, что вы можете получить тот же результат, работая над любой монадой, преобразованной в cps.

Отредактировано , чтобы учесть поправки jwodder относительно реверса. упс. Как отмечает Джон Л, неявный или явный список различий также будет работать ...