В Haskell Wiki'sРекурсия в монаде есть пример, который, как утверждается,хвостовая рекурсия:

f 0 acc = return (reverse acc)
f n acc = do
    v  <- getLine
    f (n-1) (v : acc)

В то время как императивная нотация заставляет нас верить, что она хвостовая рекурсия, она не так очевидна (по крайней мере, для меня). Если мы удаляем сахарdo мы получили

f 0 acc = return (reverse acc)
f n acc = getLine >>= \v -> f (n-1) (v : acc)

и переписывание второй строки приводит к

f n acc = (>>=) getLine (\v -> f (n-1) (v : acc))

Итак, мы видим, чтоf происходит внутри второго аргумента>>=, не в хвостовой рекурсивной позиции. Нам нужно изучитьIO«s>>= чтобы получить ответ. очевидноимея рекурсивный вызов в качестве последней строки вdo блок не является достаточным условием, чтобы функция была хвостовой рекурсивной.

Допустим, чтомонада хвостово-рекурсивная если каждая рекурсивная функция в этой монаде определяется как

f = do
    ...
    f ...

или эквивалентно

f ...  =  (...) >>= \x -> f ...

хвост рекурсивный. Мой вопрос:

Какие монады хвостовой рекурсии?Есть ли какое-то общее правило, которое мы можем использовать для немедленного различения хвостово-рекурсивных монад?

Обновить: Позвольте мне привести конкретный контрпример:[] монада не является хвостовой рекурсивной согласно приведенному выше определению. Если бы это было, то

f 0 acc = acc
f n acc = do
    r <- acc
    f (n - 1) (map (r +) acc)

должно быть хвостовой рекурсии. Однако обескураживание второй строки приводит к

f n acc = acc >>= \r -> f (n - 1) (map (r +) acc)
        = (flip concatMap) acc (\r -> f (n - 1) (map (r +) acc))

Понятно, что это не хвостовая рекурсия, и ИМХО сделать нельзя. Причина в том, что рекурсивный вызов не является концом вычисления. Это выполняется несколько раз, и результаты объединяются, чтобы сделать окончательный результат.