fix package:base

fix f is the least fixed point of the function f, i.e. the least defined x such that f x = x. When f is strict, this means that because, by the definition of strictness, f ⊥ = ⊥ and such the least defined fixed point of any strict function is ⊥.

Examples

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, 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.

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

Using fix, we can implement versions of repeat as fix . (:) and cycle as fix . (++)

>>> take 10 $ fix (0:)
[0,0,0,0,0,0,0,0,0,0]

>>> map (fix (\rec n -> if n < 2 then n else rec (n - 1) + rec (n - 2))) [1..10]
[1,1,2,3,5,8,13,21,34,55]

Implementation Details

The current implementation of fix uses structural sharing

fix f = let x = f x in x

A more straightforward but non-sharing version would look like

fix f = f (fix f)

Monadic fixpoints. For a detailed discussion, see Levent Erkok's thesis, Value Recursion in Monadic Computations, Oregon Graduate Institute, 2002.

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

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

The implementation of mfix for IO. This operation may fail with:

• FixIOException if the function passed to fixIO inspects its argument.

Examples

the IO-action is only executed once. The recursion is only on the values.

>>> take 3 <$> fixIO (\x -> putStr ":D" >> (:x) <$> readLn @Int)
:D
2
[2,2,2]

If we are strict in the value, just as with fix, we do not get termination:

>>> fixIO (\x -> putStr x >> pure ('x' : x))
* hangs forever *

We can tie the knot of a structure within IO using fixIO:

data Node = MkNode Int (IORef Node)

foo :: IO ()
foo = do
p <- fixIO (p -> newIORef (MkNode 0 p))
q <- output p
r <- output q
_ <- output r
pure ()

output :: IORef Node -> IO (IORef Node)
output ref = do
MkNode x p <- readIORef ref
print x
pure p

>>> foo
0
0
0

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

Fixity of constructors

This module defines a Fixed type for working with fixed-point arithmetic. Fixed-point arithmetic represents fractional numbers with a fixed number of digits for their fractional part. This is different to the behaviour of the floating-point number types Float and Double, because the number of digits of the fractional part of Float and Double numbers depends on the size of the number. Fixed point arithmetic is frequently used in financial mathematics, where they are used for representing decimal currencies. The type Fixed is used for fixed-point fractional numbers, which are internally represented as an Integer. The type Fixed takes one parameter, which should implement the typeclass HasResolution, to specify the number of digits of the fractional part. This module provides instances of the HasResolution typeclass for arbitrary typelevel natural numbers, and for some canonical important fixed-point representations. This module also contains generalisations of div, mod, and divMod to work with any Real instance. Automatic conversion between different Fixed can be performed through realToFrac, bear in mind that converting to a fixed with a smaller resolution will truncate the number, losing information.

>>> realToFrac (0.123456 :: Pico) :: Milli
0.123

The type of fixed-point fractional numbers. The type parameter specifies the number of digits of the fractional part and should be an instance of the HasResolution typeclass.

Examples

MkFixed 12345 :: Fixed E3

Datatype to represent the fixity of a constructor. An infix | declaration directly corresponds to an application of Infix.

This variant of Fixity appears at the type level.

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

Examples

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

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

For the result to be True, the first list must be finite; for the result to be False, the second list must be finite:

>>> [20..50] `isInfixOf` [0..]
True

>>> [0..] `isInfixOf` [20..50]
False

>>> [0..] `isInfixOf` [0..]
* Hangs forever *

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

Examples

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

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

For the result to be True, the first list must be finite; False, however, results from any mismatch:

>>> [0..] `isPrefixOf` [1..]
False

>>> [0..] `isPrefixOf` [0..99]
False

>>> [0..99] `isPrefixOf` [0..]
True

>>> [0..] `isPrefixOf` [0..]
* Hangs forever *

isPrefixOf shortcuts when the first argument is empty:

>>> isPrefixOf [] undefined
True

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

Examples

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

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

The second list must be finite; however the first list may be infinite:

>>> [0..] `isSuffixOf` [0..99]
False

>>> [0..99] `isSuffixOf` [0..]
* Hangs forever *

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.

Examples

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

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

>>> stripPrefix "foo" "barfoo"
Nothing

>>> stripPrefix "foo" "barfoobaz"
Nothing

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.

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.

Gets the fixity of a constructor

The isPrefixOf function returns True if the first argument is a prefix of the second.

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.