Prelude.Linear

otherwise is defined as the value True. It helps to make guards more readable. eg.

 f x | x < 0     = ...
     | otherwise = ...

until p f yields the result of applying f until p holds.

The find function takes a predicate and a structure and returns the leftmost element of the structure matching the predicate, or Nothing if there is no such element.

Examples

Basic usage:

>>> find (> 42) [0, 5..]Just 45

>>> find (> 12) [1..7]Nothing

\mathcal{O}(n). The insert function takes an element and a list and inserts the element into the list at the first position where it is less than or equal to the next element. In particular, if the list is sorted before the call, the result will also be sorted. It is a special case of insertBy, which allows the programmer to supply their own comparison function.

Examples

>>> insert (-1) [1, 2, 3][-1,1,2,3]

>>> insert 'd' "abcefg""abcdefg"

>>> insert 4 [1, 2, 3, 5, 6, 7][1,2,3,4,5,6,7]

Splits the argument into a list of lines stripped of their terminating \n characters. The \n terminator is optional in a final non-empty line of the argument string.

When the argument string is empty, or ends in a \n character, it can be recovered by passing the result of lines to the unlines function. Otherwise, unlines appends the missing terminating \n. This makes unlines . lines idempotent:

(unlines . lines) . (unlines . lines) = (unlines . lines)

Examples

>>> lines ""           -- empty input contains no lines[]

>>> lines "\n"         -- single empty line[""]

>>> lines "one"        -- single unterminated line["one"]

>>> lines "one\n"      -- single non-empty line["one"]

>>> lines "one\n\n"    -- second line is empty["one",""]

>>> lines "one\ntwo"   -- second line is unterminated["one","two"]

>>> lines "one\ntwo\n" -- two non-empty lines["one","two"]

The sort function implements a stable sorting algorithm. It is a special case of sortBy, which allows the programmer to supply their own comparison function.

Elements are arranged from lowest to highest, keeping duplicates in the order they appeared in the input.

The argument must be finite.

Examples

>>> sort [1,6,4,3,2,5][1,2,3,4,5,6]

>>> sort "haskell""aehklls"

>>> import Data.Semigroup(Arg(..))>>> sort [Arg ":)" 0, Arg ":D" 0, Arg ":)" 1, Arg ":3" 0, Arg ":D" 1][Arg ":)" 0,Arg ":)" 1,Arg ":3" 0,Arg ":D" 0,Arg ":D" 1]

Sort a list by comparing the results of a key function applied to each element. sortOn f is equivalent to sortBy (comparing f), but has the performance advantage of only evaluating f once for each element in the input list. This is called the decorate-sort-undecorate paradigm, or Schwartzian transform.

Elements are arranged from lowest to highest, keeping duplicates in the order they appeared in the input.

The argument must be finite.

Examples

>>> sortOn fst [(2, "world"), (4, "!"), (1, "Hello")][(1,"Hello"),(2,"world"),(4,"!")]

>>> sortOn length ["jim", "creed", "pam", "michael", "dwight", "kevin"]["jim","pam","creed","kevin","dwight","michael"]

Performance notes

This function minimises the projections performed, by materialising the projections in an intermediate list.

For trivial projections, you should prefer using sortBy with comparing, for example:

>>> sortBy (comparing fst) [(3, 1), (2, 2), (1, 3)][(1,3),(2,2),(3,1)]

Or, for the exact same API as sortOn, you can use `sortBy . comparing`:

>>> (sortBy . comparing) fst [(3, 1), (2, 2), (1, 3)][(1,3),(2,2),(3,1)]

However, sortOn may still be faster for instances with a more efficient implementation of (>) than compare.

Appends a \n character to each input string, then concatenates the results. Equivalent to foldMap (s -> s ++ "\n").

Examples

>>> unlines ["Hello", "World", "!"]"Hello\nWorld\n!\n"

Note that unlines . lines /= id when the input is not \n-terminated:

>>> unlines . lines $ "foo\nbar""foo\nbar\n"

unwords joins words with separating spaces (U+0020 SPACE).

unwords is neither left nor right inverse of words:

>>> words (unwords [" "])[]>>> unwords (words "foo\nbar")"foo bar"

Examples

>>> unwords ["Lorem", "ipsum", "dolor"]"Lorem ipsum dolor"

>>> unwords ["foo", "bar", "", "baz"]"foo bar  baz"

words breaks a string up into a list of words, which were delimited by white space (as defined by isSpace). This function trims any white spaces at the beginning and at the end.

Examples

>>> words "Lorem ipsum\ndolor"["Lorem","ipsum","dolor"]

>>> words " foo bar "["foo","bar"]

Extract the first component of a pair.

Extract the second component of a pair.

error stops execution and displays an error message.

A variant of error that does not produce a stack trace.

A special case of error. It is expected that compilers will recognize this and insert error messages which are more appropriate to the context in which undefined appears.

\mathcal{O}(1). Extract the first element of a list, which must be non-empty.

To disable the warning about partiality put {-# OPTIONS_GHC -Wno-x-partial -Wno-unrecognised-warning-flags #-} at the top of the file. To disable it throughout a package put the same options into ghc-options section of Cabal file. To disable it in GHCi put :set -Wno-x-partial -Wno-unrecognised-warning-flags into ~/.ghci config file. See also the migration guide.

Examples

>>> head [1, 2, 3]1

>>> head [1..]1

>>> head []*** Exception: Prelude.head: empty list

\mathcal{O}(n). Return all the elements of a list except the last one. The list must be non-empty.

To disable the warning about partiality put {-# OPTIONS_GHC -Wno-x-partial -Wno-unrecognised-warning-flags #-} at the top of the file. To disable it throughout a package put the same options into ghc-options section of Cabal file. To disable it in GHCi put :set -Wno-x-partial -Wno-unrecognised-warning-flags into ~/.ghci config file. See also the migration guide.

Examples

>>> init [1, 2, 3][1,2]

>>> init [1][]

>>> init []*** Exception: Prelude.init: empty list

\mathcal{O}(n). Extract the last element of a list, which must be finite and non-empty.

To disable the warning about partiality put {-# OPTIONS_GHC -Wno-x-partial -Wno-unrecognised-warning-flags #-} at the top of the file. To disable it throughout a package put the same options into ghc-options section of Cabal file. To disable it in GHCi put :set -Wno-x-partial -Wno-unrecognised-warning-flags into ~/.ghci config file. See also the migration guide.

Examples

>>> last [1, 2, 3]3

>>> last [1..]* Hangs forever *

>>> last []*** Exception: Prelude.last: empty list

\mathcal{O}(n). lookup key assocs looks up a key in an association list. For the result to be Nothing, the list must be finite.

Examples

>>> lookup 2 []Nothing

>>> lookup 2 [(1, "first")]Nothing

>>> lookup 2 [(1, "first"), (2, "second"), (3, "third")]Just "second"

\mathcal{O}(1). Extract the elements after the head of a list, which must be non-empty.

To disable the warning about partiality put {-# OPTIONS_GHC -Wno-x-partial -Wno-unrecognised-warning-flags #-} at the top of the file. To disable it throughout a package put the same options into ghc-options section of Cabal file. To disable it in GHCi put :set -Wno-x-partial -Wno-unrecognised-warning-flags into ~/.ghci config file. See also the migration guide.

Examples

>>> tail [1, 2, 3][2,3]

>>> tail [1][]

>>> tail []*** Exception: Prelude.tail: empty list

the same as flip (-).

Because - is treated specially in the Haskell grammar, (- e) is not a section, but an application of prefix negation. However, (subtract exp) is equivalent to the disallowed section.

The lex function reads a single lexeme from the input, discarding initial white space, and returning the characters that constitute the lexeme. If the input string contains only white space, lex returns a single successful `lexeme' consisting of the empty string. (Thus lex "" = [("","")].) If there is no legal lexeme at the beginning of the input string, lex fails (i.e. returns []).

This lexer is not completely faithful to the Haskell lexical syntax in the following respects:

• Qualified names are not handled properly

• Octal and hexadecimal numerics are not recognized as a single token

• Comments are not treated properly

readParen True p parses what p parses, but surrounded with parentheses.

readParen False p parses what p parses, but optionally surrounded with parentheses.

raise a number to a non-negative integral power

raise a number to an integral power

General coercion from Integral types.

WARNING: This function performs silent truncation if the result type is not at least as big as the argument's type.

gcd x y is the non-negative factor of both x and y of which every common factor of x and y is also a factor; for example gcd 4 2 = 2, gcd (-4) 6 = 2, gcd 0 4 = 4. gcd 0 0 = 0. (That is, the common divisor that is "greatest" in the divisibility preordering.)

Note: Since for signed fixed-width integer types, abs minBound < 0, the result may be negative if one of the arguments is minBound (and necessarily is if the other is 0 or minBound) for such types.

lcm x y is the smallest positive integer that both x and y divide.

General coercion to Fractional types.

utility function converting a Char to a show function that simply prepends the character unchanged.

utility function that surrounds the inner show function with parentheses when the Bool parameter is True.

utility function converting a String to a show function that simply prepends the string unchanged.

equivalent to showsPrec with a precedence of 0.

The computation appendFile file str function appends the string str, to the file file.

Note that writeFile and appendFile write a literal string to a file. To write a value of any printable type, as with print, use the show function to convert the value to a string first.

This operation may fail with the same errors as hPutStr and withFile.

Examples

The following example could be more efficently written by acquiring a handle instead with openFile and using the computations capable of writing to handles such as hPutStr.

>>> let fn = "hello_world">>> in writeFile fn "hello" >> appendFile fn " world!" >> (readFile fn >>= putStrLn)"hello world!"

>>> let fn = "foo"; output = readFile' fn >>= putStrLn>>> in output >> appendFile fn (show [1,2,3]) >> outputthis is what's in the filethis is what's in the file[1,2,3]

Read a single character from the standard input device.

getChar is implemented as hGetChar stdin.

This operation may fail with the same errors as hGetChar.

Examples

>>> getChara'a'

>>> getChar>'\n'

The getContents operation returns all user input as a single string, which is read lazily as it is needed.

getContents is implemented as hGetContents stdin.

This operation may fail with the same errors as hGetContents.

Examples

>>> getContents >>= putStr> aaabbbccc :Daaabbbccc :D> I hope you have a great dayI hope you have a great day> ^D

>>> getContents >>= print . length> abc> <3> def ^D11

Read a line from the standard input device.

getLine is implemented as hGetLine stdin.

This operation may fail with the same errors as hGetLine.

Examples

>>> getLine> Hello World!"Hello World!"

>>> getLine>""

interact f takes the entire input from stdin and applies f to it. The resulting string is written to the stdout device.

Note that this operation is lazy, which allows to produce output even before all input has been consumed.

This operation may fail with the same errors as getContents and putStr.

If it doesn't produce output the buffering settings may not be correct, use ^D (ctrl+D) to close stdin which forces the buffer to be consumed.

You may wish to set the buffering style appropriate to your program's needs before using this function, for example:

main :: IO ()
main = do
  hSetBuffering stdin LineBuffering
  hSetBuffering stdout NoBuffering
  interact (concatMap (str -> str ++ str) . L.lines)

Examples

>>> interact (\str -> str ++ str)> hi :)hi :)> ^Dhi :)

>>> interact (const ":D"):D

>>> interact (show . words)> hello world!> I hope you have a great day> ^D["hello","world!","I","hope","you","have","a","great","day"]

The print function outputs a value of any printable type to the standard output device. Printable types are those that are instances of class Show; print converts values to strings for output using the show operation and adds a newline.

print is implemented as putStrLn . show

This operation may fail with the same errors, and has the same issues with concurrency, as hPutStr!

Examples

>>> print [1, 2, 3][1,2,3]

Be careful when using print for outputting strings, as this will invoke show and cause strings to be printed with quotation marks and non-ascii symbols escaped.

>>> print "λ :D""\995 :D"

A program to print the first 8 integers and their powers of 2 could be written as:

>>> print [(n, 2^n) | n <- [0..8]][(0,1),(1,2),(2,4),(3,8),(4,16),(5,32),(6,64),(7,128),(8,256)]

Write a character to the standard output device

putChar is implemented as hPutChar stdout.

This operation may fail with the same errors as hPutChar.

Examples

Note that the following do not put a newline.

>>> putChar 'x'x

>>> putChar '\0042'*

Write a string to the standard output device

putStr is implemented as hPutStr stdout.

This operation may fail with the same errors, and has the same issues with concurrency, as hPutStr!

Examples

Note that the following do not put a newline.

>>> putStr "Hello, World!"Hello, World!

>>> putStr "\0052\0042\0050"4*2

The same as putStr, but adds a newline character.

This operation may fail with the same errors, and has the same issues with concurrency, as hPutStr!

The readFile function reads a file and returns the contents of the file as a string.

The file is read lazily, on demand, as with getContents.

This operation may fail with the same errors as hGetContents and openFile.

Examples

>>> readFile "~/hello_world""Greetings!"

>>> take 5 <$> readFile "/dev/zero""\NUL\NUL\NUL\NUL\NUL"

The readIO function is similar to read except that it signals parse failure to the IO monad instead of terminating the program.

This operation may fail with:

• isUserError if there is no unambiguous parse.

Examples

>>> fmap (+ 1) (readIO "1")2

>>> readIO "not quite ()" :: IO ()*** Exception: user error (Prelude.readIO: no parse)

The readLn function combines getLine and readIO.

This operation may fail with the same errors as getLine and readIO.

Examples

>>> fmap (+ 5) readLn> 2530

>>> readLn :: IO String> this is not a string literal*** Exception: user error (Prelude.readIO: no parse)

The computation writeFile file str function writes the string str, to the file file.

This operation may fail with the same errors as hPutStr and withFile.

Examples

>>> writeFile "hello" "world" >> readFile "hello""world"

>>> writeFile "~/" "D:"*** Exception: ~/: withFile: inappropriate type (Is a directory)

The read function reads input from a string, which must be completely consumed by the input process. read fails with an error if the parse is unsuccessful, and it is therefore discouraged from being used in real applications. Use readMaybe or readEither for safe alternatives.

>>> read "123" :: Int123

>>> read "hello" :: Int*** Exception: Prelude.read: no parse

equivalent to readsPrec with a precedence of 0.

Beware that Data.Semigroup.First is different from Data.Monoid.First. The former simply returns the first value, so Data.Semigroup.First Nothing <> x = Data.Semigroup.First Nothing. The latter returns the first non-Nothing, thus Data.Monoid.First Nothing <> x = x.

Examples

>>> First 0 <> First 10First {getFirst = 0}

>>> sconcat $ First 1 :| [ First n | n <- [2 ..] ]First {getFirst = 1}

Beware that Data.Semigroup.Last is different from Data.Monoid.Last. The former simply returns the last value, so x <> Data.Semigroup.Last Nothing = Data.Semigroup.Last Nothing. The latter returns the last non-Nothing, thus x <> Data.Monoid.Last Nothing = x.

Examples

>>> Last 0 <> Last 10Last {getLast = 10}

>>> sconcat $ Last 1 :| [ Last n | n <- [2..]]* Hangs forever *

The Either type represents values with two possibilities: a value of type Either a b is either Left a or Right b.

The Either type is sometimes used to represent a value which is either correct or an error; by convention, the Left constructor is used to hold an error value and the Right constructor is used to hold a correct value (mnemonic: "right" also means "correct").

Examples

The type Either String Int is the type of values which can be either a String or an Int. The Left constructor can be used only on Strings, and the Right constructor can be used only on Ints:

>>> let s = Left "foo" :: Either String Int>>> sLeft "foo">>> let n = Right 3 :: Either String Int>>> nRight 3>>> :type ss :: Either String Int>>> :type nn :: Either String Int

The fmap from our Functor instance will ignore Left values, but will apply the supplied function to values contained in a Right:

>>> let s = Left "foo" :: Either String Int>>> let n = Right 3 :: Either String Int>>> fmap (*2) sLeft "foo">>> fmap (*2) nRight 6

The Monad instance for Either allows us to chain together multiple actions which may fail, and fail overall if any of the individual steps failed. First we'll write a function that can either parse an Int from a Char, or fail.

>>> import Data.Char ( digitToInt, isDigit )>>> :{    let parseEither :: Char -> Either String Int        parseEither c          | isDigit c = Right (digitToInt c)          | otherwise = Left "parse error">>> :}

The following should work, since both '1' and '2' can be parsed as Ints.

>>> :{    let parseMultiple :: Either String Int        parseMultiple = do          x <- parseEither '1'          y <- parseEither '2'          return (x + y)>>> :}

>>> parseMultipleRight 3

But the following should fail overall, since the first operation where we attempt to parse 'm' as an Int will fail:

>>> :{    let parseMultiple :: Either String Int        parseMultiple = do          x <- parseEither 'm'          y <- parseEither '2'          return (x + y)>>> :}

>>> parseMultipleLeft "parse error"

Test whether the structure is empty. The default implementation is Left-associative and lazy in both the initial element and the accumulator. Thus optimised for structures where the first element can be accessed in constant time. Structures where this is not the case should have a non-default implementation.

Examples

Basic usage:

>>> null []True

>>> null [1]False

null is expected to terminate even for infinite structures. The default implementation terminates provided the structure is bounded on the left (there is a leftmost element).

>>> null [1..]False

Boolean monoid under conjunction (&&).

All x <> All y = All (x && y)

Examples

>>> All True <> mempty <> All False)All {getAll = False}

>>> mconcat (map (\x -> All (even x)) [2,4,6,7,8])All {getAll = False}

>>> All True <> memptyAll {getAll = True}

Boolean monoid under disjunction (||).

Any x <> Any y = Any (x || y)

Examples

>>> Any True <> mempty <> Any FalseAny {getAny = True}

>>> mconcat (map (\x -> Any (even x)) [2,4,6,7,8])Any {getAny = True}

>>> Any False <> memptyAny {getAny = False}

The dual of a Monoid, obtained by swapping the arguments of (<>).

Dual a <> Dual b == Dual (b <> a)

Examples

>>> Dual "Hello" <> Dual "World"Dual {getDual = "WorldHello"}

>>> Dual (Dual "Hello") <> Dual (Dual "World")Dual {getDual = Dual {getDual = "HelloWorld"}}

Monoid under multiplication.

Product x <> Product y == Product (x * y)

Examples

>>> Product 3 <> Product 4 <> memptyProduct {getProduct = 12}

>>> mconcat [ Product n | n <- [2 .. 10]]Product {getProduct = 3628800}

Monoid under addition.

Sum a <> Sum b = Sum (a + b)

Examples

>>> Sum 1 <> Sum 2 <> memptySum {getSum = 3}

>>> mconcat [ Sum n | n <- [3 .. 9]]Sum {getSum = 42}

IsString is used in combination with the -XOverloadedStrings language extension to convert the literals to different string types.

For example, if you use the text package, you can say

{-# LANGUAGE OverloadedStrings  #-}

myText = "hello world" :: Text

Internally, the extension will convert this to the equivalent of

myText = fromString @Text ("hello world" :: String)

Note: You can use fromString in normal code as well, but the usual performance/memory efficiency problems with String apply.

The Bounded class is used to name the upper and lower limits of a type. Ord is not a superclass of Bounded since types that are not totally ordered may also have upper and lower bounds.

The Bounded class may be derived for any enumeration type; minBound is the first constructor listed in the data declaration and maxBound is the last. Bounded may also be derived for single-constructor datatypes whose constituent types are in Bounded.