i noticed a common pattern of executing an action until it stops having certain effects, when one knows that this signifies a fixed point (ie, there can be no future effects). is there a typeclass for this?
is this covered by MonadFix? looking at the code, it seems it would be, but i was scared off by the wiki page "It is tempting to see “recursion” and guess it means performing actions recursively or repeatedly. No."
it also seems to me that fixed points are something like the dual of identities. that is, an identity disappears when combined with a non-identity (0 for (+), 1 for (*), [] for append, etc). whereas a fixed point causes any non-fixed point to disappear under the 'relax' operation below. is there a way to formalize this duality, and is it useful to do so? ie, is there a relationship between MonadPlus and/or Monoid and MonadRelax?
lastly, i notice relax is almost an unfold/anamorphism. would it be better to express it as such?
{-# 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
What you are asking for, is actually a plain 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))
This will repeat the computation, until i becomes 0. (I added c to have a meaningful computation; but you could assume s=(Int,Int) with one of them being a rolling sum and the other the counter)
> cd 0 4 :: [Int]
[10]
This is the same as:
relax = fix (\f s -> if isFix s then return s else f (step s))
I believe, this is the definition of iterateUntilM.