Класс типов для повторяющихся действий до фиксированной точки

Question

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

это покрывается MonadFix? Глядя на код, кажется, что это так, но я был напуган вики-страницей: "Заманчиво увидеть" рекурсию "и предположить, что это означает выполнение действий рекурсивно или многократно. Нет".

мне также кажется, что фиксированные точки являются чем-то вроде двойственности тождеств. то есть идентичность исчезает при объединении с неидентификацией (0 для (+), 1 для (*), [] для добавления и т. д.). в то время как фиксированная точка приводит к исчезновению любой нефиксированной точки при операции "расслабления" ниже. Есть ли способ формализовать эту двойственность, и это полезно? т.е. есть ли связь между MonadPlus и / или Monoid и MonadRelax?

наконец, я замечаю, что расслабление - это почти развернутый анаморфизм. было бы лучше выразить это как таковой?

{-# LANGUAGE MultiParamTypeClasses, FunctionalDependencies #-}

import Control.Monad.Loops (iterateUntilM) -- cabal install monad-loops

-- states that relax to a fixed point under step
class Monad m => MonadRelax m s | s -> m where
isFixed :: s -> Bool
step :: s -> m s -- often (not always): step s = return s iff isFixed s

relax :: MonadRelax m s => s -> m s
relax = iterateUntilM isFixed step

Answer 1

То, что вы просите, на самом деле просто fix:

cd :: (Monad m) => Int -> Int -> m Int
cd = fix (\f c i -> if i == 0 then return c else f (c+i) (i-1))

Это будет повторять вычисления, пока i становится 0. (Я добавил c иметь значимые вычисления; но вы могли бы предположить s=(Int,Int) одна из которых является скользящей суммой, а другая - счетчиком)

> cd 0 4 :: [Int]
[10]

Это так же, как:

relax = fix (\f s -> if isFix s then return s else f (step s))

Я считаю, что это определение iterateUntilM,