fix package:rio

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.

Check whether one string is a substring of another. isInfixOf p s is equivalent to not (null (findSubstrings p s)).

O(n) The isPrefixOf function takes two ByteStrings and returns True if the first is a prefix of the second.

O(n) The isSuffixOf function takes two ByteStrings and returns True iff the first is a suffix of the second. The following holds:

isSuffixOf x y == reverse x `isPrefixOf` reverse y

However, the real implemenation uses memcmp to compare the end of the string only, with no reverse required..

O(n) The stripPrefix function takes two ByteStrings and returns Just the remainder of the second iff the first is its prefix, and otherwise Nothing.

O(n) The stripSuffix function takes two ByteStrings and returns Just the remainder of the second iff the first is its suffix, and otherwise Nothing.

O(n) The isPrefixOf function takes two ByteStrings and returns True iff the first is a prefix of the second.

O(n) The isSuffixOf function takes two ByteStrings and returns True iff the first is a suffix of the second. The following holds:

isSuffixOf x y == reverse x `isPrefixOf` reverse y

Drop prefix if present, otherwise return original list.

Drop prefix if present, otherwise return original list.

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

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

Remove the suffix from the given list, if present

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

O(n) Find the longest non-empty common prefix of two strings and return it, along with the suffixes of each string at which they no longer match. If the strings do not have a common prefix or either one is empty, this function returns Nothing. Examples:

>>> commonPrefixes "foobar" "fooquux"
Just ("foo","bar","quux")

>>> commonPrefixes "veeble" "fetzer"
Nothing

>>> commonPrefixes "" "baz"
Nothing

Drop prefix if present, otherwise return original Text.

Drop prefix if present, otherwise return original Text.

O(n+m) The isInfixOf function takes two Texts and returns True iff the first is contained, wholly and intact, anywhere within the second. In (unlikely) bad cases, this function's time complexity degrades towards O(n*m).

O(n) The isPrefixOf function takes two Texts and returns True iff the first is a prefix of the second. Subject to fusion.

O(n) The isSuffixOf function takes two Texts and returns True iff the first is a suffix of the second.

O(n) Return the suffix of the second string if its prefix matches the entire first string. Examples:

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

>>> stripPrefix ""    "baz"
Just "baz"

>>> stripPrefix "foo" "quux"
Nothing

This is particularly useful with the ViewPatterns extension to GHC, as follows:

{-# LANGUAGE ViewPatterns #-}
import Data.Text as T

fnordLength :: Text -> Int
fnordLength (stripPrefix "fnord" -> Just suf) = T.length suf
fnordLength _                                 = -1

O(n) Return the prefix of the second string if its suffix matches the entire first string. Examples:

>>> stripSuffix "bar" "foobar"
Just "foo"

>>> stripSuffix ""    "baz"
Just "baz"

>>> stripSuffix "foo" "quux"
Nothing

This is particularly useful with the ViewPatterns extension to GHC, as follows:

{-# LANGUAGE ViewPatterns #-}
import Data.Text as T

quuxLength :: Text -> Int
quuxLength (stripSuffix "quux" -> Just pre) = T.length pre
quuxLength _                                = -1

O(n) Find the longest non-empty common prefix of two strings and return it, along with the suffixes of each string at which they no longer match. If the strings do not have a common prefix or either one is empty, this function returns Nothing. Examples:

commonPrefixes "foobar" "fooquux" == Just ("foo","bar","quux")
commonPrefixes "veeble" "fetzer"  == Nothing
commonPrefixes "" "baz"           == Nothing