Agda.Utils.Function

Documentation

iterate' :: Integral i => i -> (a -> a) -> a -> a

iterate' n f x applies f to x n times and returns the result.

The applications are calculated strictly.

applyWhen :: IsBool b => b -> (a -> a) -> a -> a

applyWhen b f a applies f to a when b.

iterateUntilM :: Monad m => (a -> a -> Bool) -> (a -> m a) -> a -> m a

Monadic version of iterateUntil.

applyWhenM :: (IsBool b, Monad m) => m b -> (m a -> m a) -> m a -> m a

Monadic version of applyWhen

applyUnless :: IsBool b => b -> (a -> a) -> a -> a

applyUnless b f a applies f to a unless b.

iterWhile :: (b -> Bool) -> (a -> (b, a)) -> a -> [(b, a)]

Repeat a state transition f :: a -> (b, a) with output b while condition cond on the output is true. Return all intermediate results and the final result where cond is False.

Postconditions (when it terminates): fst (last (iterWhile cond f a)) == False. all fst (init (interWhile cond f a)).

repeatWhile :: (a -> (Bool, a)) -> a -> a

Repeat something while a condition on some state is true. Return the last state (including the changes of the last transition, even if the condition became false then).

repeatWhileM :: Monad m => (a -> m (Bool, a)) -> a -> m a

Monadic version of repeatWhile.

trampolineWhile :: (a -> (Bool, a)) -> a -> a

A version of the trampoline function.

The usual function iterates f :: a -> Maybe a as long as Just{} is returned, and returns the last value of a upon Nothing.

usualTrampoline f = trampolineWhile $ a -> maybe (False,a) (True,) (f a).

trampolineWhile is very similar to repeatWhile, only that it discards the state on which the condition went False, and returns the last state on which the condition was True.

trampolineWhileM :: Monad m => (a -> m (Bool, a)) -> a -> m a

Monadic version of trampolineWhile.

trampoline :: (a -> Either b a) -> a -> b

More general trampoline, which allows some final computation from iteration state a into result type b.

trampolineM :: Monad m => (a -> m (Either b a)) -> a -> m b

Monadic version of trampoline.

iterateUntil :: (a -> a -> Bool) -> (a -> a) -> a -> a

Iteration to fixed-point.

iterateUntil r f a0 iterates endofunction f, starting with a0, until r relates its result to its input, i.e., f a r a.

This is the generic pattern behind saturation algorithms.

If f is monotone with regard to r, meaning a r b implies f a r f b, and f-chains starting with a0 are finite then iteration is guaranteed to terminate.

A typical instance will work on sets, and r could be set inclusion, and a0 the empty set, and f the step function of a saturation algorithm.

applyUnlessM :: (IsBool b, Monad m) => m b -> (m a -> m a) -> m a -> m a

Monadic version of applyUnless

applyWhenJust :: Maybe b -> (b -> a -> a) -> a -> a

Maybe version of applyWhen.

applyWhenNothing :: Maybe b -> (a -> a) -> a -> a

Maybe version of applyUnless.

on :: (b -> b -> c) -> (a -> b) -> a -> a -> c infixl 0

on b u x y runs the binary function b on the results of applying unary function u to two arguments x and y. From the opposite perspective, it transforms two inputs and combines the outputs.

((+) `on` f) x y = f x + f y

Typical usage: sortBy (compare `on` fst).

Algebraic properties:

• (*) `on` id = (*) -- (if (*) ∉ {⊥, const ⊥})

• ((*) `on` f) `on` g = (*) `on` (f . g)

• flip on f . flip on g = flip on (g . f)