хвостато-рекурсивные функции в монадах
Jan. 24th, 2007 07:54 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png)
Когда мы пишем монадическую функцию с хвостовой рекурсией, то явно эта функция не хвостато-рекурсивная:
Например, эта функция выглядит как
Я здесь хвостатости не вижу. Я предполагаю, что реализация
Чтобы было ясно, что я имею в виду:
Откуда следует, что
Кто подскажет?
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
.Кто подскажет?