fix package:rebase

fix f is the least fixed point of the function f, i.e. the least defined x such that f x = x. For example, we can write the factorial function using direct recursion as

>>> let fac n = if n <= 1 then 1 else n * fac (n-1) in fac 5
120

This uses the fact that Haskell’s let introduces recursive bindings. We can rewrite this definition using fix,

>>> fix (\rec n -> if n <= 1 then 1 else n * rec (n-1)) 5
120

Instead of making a recursive call, we introduce a dummy parameter rec; when used within fix, this parameter then refers to fix’s argument, hence the recursion is reintroduced.

Allow the result of an ST computation to be used (lazily) inside the computation. Note that if f is strict, fixST f = _|_.

The exception thrown when an infinite cycle is detected in fixIO.

The type parameter should be an instance of HasResolution.

Fixity of constructors

Monads having fixed points with a 'knot-tying' semantics. Instances of MonadFix should satisfy the following laws:

• Purity mfix (return . h) = return (fix h)
• Left shrinking (or Tightening) mfix (\x -> a >>= \y -> f x y) = a >>= \y -> mfix (\x -> f x y)
• Sliding mfix (liftM h . f) = liftM h (mfix (f . h)), for strict h.
• Nesting mfix (\x -> mfix (\y -> f x y)) = mfix (\x -> f x x)

This class is used in the translation of the recursive do notation supported by GHC and Hugs.

Comonadic fixed point à la Dominic Orchard

Gets the fixity of a constructor

The isInfixOf function takes two lists and returns True iff the first list is contained, wholly and intact, anywhere within the second.

>>> isInfixOf "Haskell" "I really like Haskell."
True

>>> isInfixOf "Ial" "I really like Haskell."
False

The isPrefixOf function takes two lists and returns True iff the first list is a prefix of the second.

>>> "Hello" `isPrefixOf` "Hello World!"
True

>>> "Hello" `isPrefixOf` "Wello Horld!"
False

The isSuffixOf function takes two lists and returns True iff the first list is a suffix of the second. The second list must be finite.

>>> "ld!" `isSuffixOf` "Hello World!"
True

>>> "World" `isSuffixOf` "Hello World!"
False

Comonadic fixed point à la Kenneth Foner: This is the evaluate function from his "Getting a Quick Fix on Comonads" talk.

The fixed point of a monadic computation. mfix f executes the action f only once, with the eventual output fed back as the input. Hence f should not be strict, for then mfix f would diverge.

The stripPrefix function drops the given prefix from a list. It returns Nothing if the list did not start with the prefix given, or Just the list after the prefix, if it does.

>>> stripPrefix "foo" "foobar"
Just "bar"

>>> stripPrefix "foo" "foo"
Just ""

>>> stripPrefix "foo" "barfoo"
Nothing

>>> stripPrefix "foo" "barfoobaz"
Nothing

A slightly faster version of fixIO that may not be safe to use with multiple threads. The unsafety arises when used like this:

unsafeFixIO $ \r -> do
forkIO (print r)
return (...)

In this case, the child thread will receive a NonTermination exception instead of waiting for the value of r to be computed.

Comonadic fixed point à la David Menendez