хвостато-рекурсивные функции в монадах

Jan 24, 2007 19:54

Когда мы пишем монадическую функцию с хвостовой рекурсией, то явно эта функция не хвостато-рекурсивная:

loop = do
cmd <- getLine
if (cmd == ":q")
then return ()
else loop


Например, эта функция выглядит как

loop = getLine >>= \cmd ->
if (cmd == ":q")
then return ()
else loop

Я здесь хвостатости не вижу. Я предполагаю, что реализация (>>=) такова, что bind переводит запись c foo = m >>= foo в хвостовую рекурсию.

Чтобы было ясно, что я имею в виду:

instance Monad Identity where
return a = Identity a
m >>= k = k (runIdentity m)

Откуда следует, что f = m >>= f преобразуется в f = f (runIndentity m). Но, с другой стороны, это только в случае инлайна будет возможна такая оптимизация. И фиг знает, что там с другими монадами. Полагаю, что их тоже можно развернуть в хвостатую запись. Может быть кто нибудь поможет с объяснением или ссылкой - почему так? Может быть на это влияет семантика монад, в частности то, что в m >>= f f не будет выполнено до тех пор, пока не будет выполнен m.

Кто подскажет?

монады, haskell, программирование

Previous post Next post
Up