Control.Monad.Trans.Fix

Monad transformer for evaluating to a fixpoint.

The idea is that some transforms need to be run multiple times. Deciding whether to run a transform again can be somewhat tedious though, as you cannot necessarily just run some transform f on x until f x == x.

This might not be ideal for a few reasons:

• x might not implement Eq;
• x might implement Eq, but could contain floats of NaN, in which case NaN /= NaN; or
• checking equality can be expensive.

Instead, this provides a function called progress, with the same type as return, that marks the current transform as having "made progress": that is, it should be re-run again. Then you can call fixpoint with a function of type a -> FixT m a, which will be re-run until no progress is made.

Documentation

newtype FixT m a

Fixpoint monad transformer.

Constructors

FixT

Fields

• runFixT :: m (a, Progress)

Instances

MonadTrans FixT

Methods

lift :: Monad m => m a -> FixT m a

Monad m => Monad (FixT m)

Methods

(>>=) :: FixT m a -> (a -> FixT m b) -> FixT m b

(>>) :: FixT m a -> FixT m b -> FixT m b

return :: a -> FixT m a

fail :: String -> FixT m a

Monad m => Functor (FixT m)

Methods

fmap :: (a -> b) -> FixT m a -> FixT m b

(<$) :: a -> FixT m b -> FixT m a

Monad m => Applicative (FixT m)

Methods

pure :: a -> FixT m a

(<*>) :: FixT m (a -> b) -> FixT m a -> FixT m b

(*>) :: FixT m a -> FixT m b -> FixT m b

(<*) :: FixT m a -> FixT m b -> FixT m a

data Progress

Have we made progress?

Constructors

RunAgain

NoProgress

Instances

Eq Progress

Methods

(==) :: Progress -> Progress -> Bool

(/=) :: Progress -> Progress -> Bool

Ord Progress

Methods

compare :: Progress -> Progress -> Ordering

(<) :: Progress -> Progress -> Bool

(<=) :: Progress -> Progress -> Bool

(>) :: Progress -> Progress -> Bool

(>=) :: Progress -> Progress -> Bool

max :: Progress -> Progress -> Progress

min :: Progress -> Progress -> Progress

Show Progress

Methods

showsPrec :: Int -> Progress -> ShowS

show :: Progress -> String

showList :: [Progress] -> ShowS

fixpoint :: Monad m => (a -> FixT m a) -> a -> m a

Apply the transform until it no longer makes progress

once :: Monad m => FixT m a -> m a

Run a FixT once, regardless of whether it believes it makes progress or not

fixOfMaybe :: Monad m => (a -> m (Maybe a)) -> a -> FixT m a

Take a function that returns Just on progress and Nothing on completion.

progress :: Monad m => a -> FixT m a

Return a value and proclaim: "it might be worth running again"