Используйте две монады без трансформатора

Question

Чтобы понять, как использовать монадные преобразователи, я написал следующий код без такового. Он читает стандартный ввод строка за строкой и отображает каждую строку в обратном порядке, пока не встретится пустая строка. Он также считает строки, используя State и в конце отображается общее количество.

import Control.Monad.State

main = print =<< fmap (`evalState` 0) go where
    go :: IO (State Int Int)
    go = do
        l <- getLine
        if null l
        then return get
        else do
            putStrLn (reverse l)
            -- another possibility: fmap (modify (+1) >>) go
            rest <- go
            return $ do
                modify (+1)
                rest

Я хотел добавить номер текущей строки перед каждой строкой. Я смог сделать это с StateT:

import Control.Monad.State

main = print =<< evalStateT go 0 where
    go :: StateT Int IO Int
    go = do
        l <- lift getLine
        if null l
        then get
        else do
            n <- get
            lift (putStrLn (show n ++ ' ' : reverse l))
            modify (+1)
            go

У меня вопрос: как сделать то же самое в версии без монадных трансформаторов?

Answer 1

Проблема в том, что вы раскручиваете StateT s IO a является s -> IO (s, a)не IO (s -> (s, a))! Как только вы это поймете, довольно легко увидеть, как это сделать:

go :: Int -> IO (Int, Int)
go s = do
    l <- getLine
    if null l
    then return (s, s)
    else do
        putStrLn (show s ++ ' ' : reverse l)
        go (s+1)

Answer 2

Вам просто нужно запустить вычисление накопленного состояния в каждой строке. Это время O(n²), но так как ваша первая программа уже использует пространство O(n), это не так уж страшно. Конечно, StateT подход превосходит почти во всех отношениях! Если вы действительно хотите сделать это "вручную" и не платить цену эффективности, просто управляйте государством вручную, а не строите трансформатор состояния вообще. Вы действительно не получаете никакой выгоды, используя State вместо Int в первой программе.

Answer 3

Может быть, это то, что вы ищете?

main = print =<< fmap (`evalState` 0) (go get) where
  go :: State Int Int -> IO (State Int Int)
  go st = do
     l <- getLine 
     if null l
     then return (st >>= \_ -> get)
     else do
          let ln = evalState st 0
          putStrLn(show ln ++ ' ' : reverse l)
          go (st >>= \_ -> modify (+1) >>= \_ ->  get) 

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

РЕДАКТИРОВАТЬ

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

main = print =<< fmap (`evalState` 0) (go get) where
  go :: State Int Int -> IO (State Int Int)
  go st = do
     l <- getLine 
     if null l
     then return st
     else do
          let ln = evalState st 0
          putStrLn(show ln ++ ' ' : reverse l)
          go (modify (\s -> s+ln+1) >>= \_ ->  get)