fix package:protolude

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)

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

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 fixity of the constructor

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 *