Использование Foldr и Bind, чтобы завершить ничто

Question

Итак, по сути, у меня есть некоторая монадическая функция, завернутая в MaybeT Я хочу использовать Nothing в качестве завершающего случая для рекурсии

Мое понимание foldr является то, что, если он может произвести результат, не занимая весь список, он может безопасно использоваться в бесконечном списке, т.е. foldr (&&) True $ repeat False все еще может вернуться False,

На данный момент у меня есть:

repeaterM a f = foldr (=<<) (return a) $ repeat f

Этот тип проверяет, но на самом деле не работает. Может ли кто-нибудь объяснить мне, почему я не могу использовать эту функцию, чтобы неоднократно применять функцию к ее собственному результату, пока она не вернется Nothing?

Answer 1

foldr            :: (a -> b -> b) -> b -> [a] -> b
foldr k z = go
          where
            go []     = z
            go (y:ys) = y `k` go ys

Так

foldr (&&) True $ repeat False
   = go (repeat False) where go [] = True ; go (y:ys) = y && go ys
   = False && go (repeat False) where go [] = True ; go (y:ys) = y && go ys
   = False

как вы ожидаете.

Но

foldr (=<<) (return a) $ repeat f
   = go (repeat f) where go [] = return a ; go (y:ys) = y =<< ys
   = f =<< go (repeat f) where go [] = return a ; go (y:ys) = y =<< ys
   = f =<< f =<< go (repeat f) where go [] = return a ; go (y:ys) = y =<< ys
   = f =<< f =<< f =<< go (repeat f) where go [] = return a ; go (y:ys) = y =<< ys
   ...

То, что вы делаете здесь, не повторяет применение функции к ее собственному результату, пока она не вернется Nothing,

Вы строите вычисления с его конца: RHS каждого =<< должен быть рассчитан до того, как LHS может быть выполнен. Но у вас есть бесконечный список, поэтому вы никогда не доберетесь до начала вычислений.

Вы можете попытаться определить

repeaterM a f = foldl (>>=) (return a) $ repeat f

вместо. Это тоже не сработает (спасибо is7s).