Haskell features

Examples

Factorial

A simple example that is often used to demonstrate the syntax of functional languages is the factorial function for non-negative integers, shown in Haskell:

<span id="mwEQ"></span><span class="nf" id="mwEg">factorial</span><span class="w" id="mwEw"> </span><span class="ow" id="mwFA">::</span><span class="w" id="mwFQ"> </span><span class="kt" id="mwFg">Integer</span><span class="w" id="mwFw"> </span><span class="ow" id="mwGA">-></span><span class="w" id="mwGQ"> </span><span class="kt" id="mwGg">Integer</span> <span class="nf" id="mwGw">factorial</span><span class="w" id="mwHA"> </span><span class="mi" id="mwHQ">0</span><span class="w" id="mwHg"> </span><span class="ow" id="mwHw">=</span><span class="w" id="mwIA"> </span><span class="mi" id="mwIQ">1</span> <span class="nf" id="mwIg">factorial</span><span class="w" id="mwIw"> </span><span class="n" id="mwJA">n</span><span class="w" id="mwJQ"> </span><span class="ow" id="mwJg">=</span><span class="w" id="mwJw"> </span><span class="n" id="mwKA">n</span><span class="w" id="mwKQ"> </span><span class="o" id="mwKg">*</span><span class="w" id="mwKw"> </span><span class="n" id="mwLA">factorial</span><span class="w" id="mwLQ"> </span><span class="p" id="mwLg">(</span><span class="n" id="mwLw">n</span><span class="o" id="mwMA">-</span><span class="mi" id="mwMQ">1</span><span class="p" id="mwMg">)</span>

Or in one line:

<span id="mwNg"></span><span class="nf" id="mwNw">factorial</span><span class="w" id="mwOA"> </span><span class="n" id="mwOQ">n</span><span class="w" id="mwOg"> </span><span class="ow" id="mwOw">=</span><span class="w" id="mwPA"> </span><span class="kr" id="mwPQ">if</span><span class="w" id="mwPg"> </span><span class="n" id="mwPw">n</span><span class="w" id="mwQA"> </span><span class="o" id="mwQQ">></span><span class="w" id="mwQg"> </span><span class="mi" id="mwQw">1</span><span class="w" id="mwRA"> </span><span class="kr" id="mwRQ">then</span><span class="w" id="mwRg"> </span><span class="n" id="mwRw">n</span><span class="w" id="mwSA"> </span><span class="o" id="mwSQ">*</span><span class="w" id="mwSg"> </span><span class="n" id="mwSw">factorial</span><span class="w" id="mwTA"> </span><span class="p" id="mwTQ">(</span><span class="n" id="mwTg">n</span><span class="o" id="mwTw">-</span><span class="mi" id="mwUA">1</span><span class="p" id="mwUQ">)</span><span class="w" id="mwUg"> </span><span class="kr" id="mwUw">else</span><span class="w" id="mwVA"> </span><span class="mi" id="mwVQ">1</span>

This describes the factorial as a recursive function, with one terminating base case. It is similar to the descriptions of factorials found in mathematics textbooks. Much of Haskell code is similar to standard mathematical notation in facility and syntax.

The first line of the factorial function describes the type of this function; while it is optional, it is considered to be good style to include it. It can be read as the function factorial (factorial) has type (::) from integer to integer (Integer -> Integer). That is, it takes an integer as an argument, and returns another integer. The type of a definition is inferred automatically if no type annotation is given.

The second line relies on pattern matching, an important feature of Haskell. Note that parameters of a function are not in parentheses but separated by spaces. When the function's argument is 0 (zero) it will return the integer 1 (one). For all other cases the third line is tried. This is the recursion, and executes the function again until the base case is reached.

Using the product function from the Prelude, a number of small functions analogous to C's standard library, and using the Haskell syntax for arithmetic sequences, the factorial function can be expressed in Haskell as follows:

<span id="mwbg"></span><span class="nf" id="mwbw">factorial</span><span class="w" id="mwcA"> </span><span class="n" id="mwcQ">n</span><span class="w" id="mwcg"> </span><span class="ow" id="mwcw">=</span><span class="w" id="mwdA"> </span><span class="n" id="mwdQ">product</span><span class="w" id="mwdg"> </span><span class="p" id="mwdw">[</span><span class="mi" id="mweA">1</span><span class="o" id="mweQ">..</span><span class="n" id="mweg">n</span><span class="p" id="mwew">]</span>

Here [1..n] denotes the arithmetic sequence 1, 2, …, n in list form. Using the Prelude function enumFromTo, the expression [1..n] can be written as enumFromTo 1 n, allowing the factorial function to be expressed as

<span id="mwhg"></span><span class="nf" id="mwhw">factorial</span><span class="w" id="mwiA"> </span><span class="n" id="mwiQ">n</span><span class="w" id="mwig"> </span><span class="ow" id="mwiw">=</span><span class="w" id="mwjA"> </span><span class="n" id="mwjQ">product</span><span class="w" id="mwjg"> </span><span class="p" id="mwjw">(</span><span class="n" id="mwkA">enumFromTo</span><span class="w" id="mwkQ"> </span><span class="mi" id="mwkg">1</span><span class="w" id="mwkw"> </span><span class="n" id="mwlA">n</span><span class="p" id="mwlQ">)</span>

which, using the function composition operator (expressed as a dot in Haskell) to compose the product function with the curried enumeration function can be rewritten in point-free style:

<span id="mwoA"></span><span class="nf" id="mwoQ">factorial</span><span class="w" id="mwog"> </span><span class="ow" id="mwow">=</span><span class="w" id="mwpA"> </span><span class="n" id="mwpQ">product</span><span class="w" id="mwpg"> </span><span class="o" id="mwpw">.</span><span class="w" id="mwqA"> </span><span class="n" id="mwqQ">enumFromTo</span><span class="w" id="mwqg"> </span><span class="mi" id="mwqw">1</span>

In the Hugs interpreter, one often needs to define the function and use it on the same line separated by a where or let..in. For example, to test the above examples and see the output 120:

<span id="mwsw"></span><span class="kr" id="mwtA">let</span><span class="w" id="mwtQ"> </span><span class="p" id="mwtg">{</span><span class="w" id="mwtw"> </span><span class="n" id="mwuA">factorial</span><span class="w" id="mwuQ"> </span><span class="n" id="mwug">n</span><span class="w" id="mwuw"> </span><span class="o" id="mwvA">|</span><span class="w" id="mwvQ"> </span><span class="n" id="mwvg">n</span><span class="w" id="mwvw"> </span><span class="o" id="mwwA">></span><span class="w" id="mwwQ"> </span><span class="mi" id="mwwg">0</span><span class="w" id="mwww"> </span><span class="ow" id="mwxA">=</span><span class="w" id="mwxQ"> </span><span class="n" id="mwxg">n</span><span class="w" id="mwxw"> </span><span class="o" id="mwyA">*</span><span class="w" id="mwyQ"> </span><span class="n" id="mwyg">factorial</span><span class="w" id="mwyw"> </span><span class="p" id="mwzA">(</span><span class="n" id="mwzQ">n</span><span class="o" id="mwzg">-</span><span class="mi" id="mwzw">1</span><span class="p" id="mw0A">);</span><span class="w" id="mw0Q"> </span><span class="n" id="mw0g">factorial</span><span class="w" id="mw0w"> </span><span class="kr" id="mw1A">_</span><span class="w" id="mw1Q"> </span><span class="ow" id="mw1g">=</span><span class="w" id="mw1w"> </span><span class="mi" id="mw2A">1</span><span class="w" id="mw2Q"> </span><span class="p" id="mw2g">}</span><span class="w" id="mw2w"> </span><span class="kr" id="mw3A">in</span><span class="w" id="mw3Q"> </span><span class="n" id="mw3g">factorial</span><span class="w" id="mw3w"> </span><span class="mi" id="mw4A">5</span>

or

<span id="mw5A"></span><span class="nf" id="mw5Q">factorial</span><span class="w" id="mw5g"> </span><span class="mi" id="mw5w">5</span><span class="w" id="mw6A"> </span><span class="kr" id="mw6Q">where</span><span class="w" id="mw6g"> </span><span class="n" id="mw6w">factorial</span><span class="w" id="mw7A"> </span><span class="ow" id="mw7Q">=</span><span class="w" id="mw7g"> </span><span class="n" id="mw7w">product</span><span class="w" id="mw8A"> </span><span class="o" id="mw8Q">.</span><span class="w" id="mw8g"> </span><span class="n" id="mw8w">enumFromTo</span><span class="w" id="mw9A"> </span><span class="mi" id="mw9Q">1</span>

The GHCi interpreter doesn't have this restriction and function definitions can be entered on one line (with the let syntax without the in part), and referenced later.

More complex examples

Calculator

In the Haskell source immediately below, :: can be read as "has type"; a -> b can be read as "is a function from a to b". (Thus the Haskell calc :: String -> [Float] can be read as "calc has type of a function from Strings to lists of Floats".) In the second line calc = ... the equals sign can be read as "can be"; thus multiple lines with calc = ... can be read as multiple possible values for calc, depending on the circumstance detailed in each line.

A simple Reverse Polish notation calculator expressed with the higher-order function foldl whose argument f is defined in a where clause using pattern matching and the type class Read:

<span id="mwARM"></span><span class="nf" id="mwARQ">calc</span><span class="w" id="mwARU"> </span><span class="ow" id="mwARY">::</span><span class="w" id="mwARc"> </span><span class="kt" id="mwARg">String</span><span class="w" id="mwARk"> </span><span class="ow" id="mwARo">-></span><span class="w" id="mwARs"> </span><span class="p" id="mwARw">[</span><span class="kt" id="mwAR0">Float</span><span class="p" id="mwAR4">]</span> <span class="nf" id="mwAR8">calc</span><span class="w" id="mwASA"> </span><span class="ow" id="mwASE">=</span><span class="w" id="mwASI"> </span><span class="n" id="mwASM">foldl</span><span class="w" id="mwASQ"> </span><span class="n" id="mwASU">f</span><span class="w" id="mwASY"> </span><span class="kt" id="mwASc">[]</span><span class="w" id="mwASg"> </span><span class="o" id="mwASk">.</span><span class="w" id="mwASo"> </span><span class="n" id="mwASs">words</span> <span class="w" id="mwASw"> </span><span class="kr" id="mwAS0">where</span><span class="w" id="mwAS4"> </span> <span class="w" id="mwAS8"> </span><span class="n" id="mwATA">f</span><span class="w" id="mwATE"> </span><span class="p" id="mwATI">(</span><span class="n" id="mwATM">x</span><span class="kt" id="mwATQ">:</span><span class="n" id="mwATU">y</span><span class="kt" id="mwATY">:</span><span class="n" id="mwATc">zs</span><span class="p" id="mwATg">)</span><span class="w" id="mwATk"> </span><span class="s" id="mwATo">"+"</span><span class="w" id="mwATs"> </span><span class="ow" id="mwATw">=</span><span class="w" id="mwAT0"> </span><span class="p" id="mwAT4">(</span><span class="n" id="mwAT8">y</span><span class="w" id="mwAUA"> </span><span class="o" id="mwAUE">+</span><span class="w" id="mwAUI"> </span><span class="n" id="mwAUM">x</span><span class="p" id="mwAUQ">)</span><span class="kt" id="mwAUU">:</span><span class="n" id="mwAUY">zs</span> <span class="w" id="mwAUc"> </span><span class="n" id="mwAUg">f</span><span class="w" id="mwAUk"> </span><span class="p" id="mwAUo">(</span><span class="n" id="mwAUs">x</span><span class="kt" id="mwAUw">:</span><span class="n" id="mwAU0">y</span><span class="kt" id="mwAU4">:</span><span class="n" id="mwAU8">zs</span><span class="p" id="mwAVA">)</span><span class="w" id="mwAVE"> </span><span class="s" id="mwAVI">"-"</span><span class="w" id="mwAVM"> </span><span class="ow" id="mwAVQ">=</span><span class="w" id="mwAVU"> </span><span class="p" id="mwAVY">(</span><span class="n" id="mwAVc">y</span><span class="w" id="mwAVg"> </span><span class="o" id="mwAVk">-</span><span class="w" id="mwAVo"> </span><span class="n" id="mwAVs">x</span><span class="p" id="mwAVw">)</span><span class="kt" id="mwAV0">:</span><span class="n" id="mwAV4">zs</span> <span class="w" id="mwAV8"> </span><span class="n" id="mwAWA">f</span><span class="w" id="mwAWE"> </span><span class="p" id="mwAWI">(</span><span class="n" id="mwAWM">x</span><span class="kt" id="mwAWQ">:</span><span class="n" id="mwAWU">y</span><span class="kt" id="mwAWY">:</span><span class="n" id="mwAWc">zs</span><span class="p" id="mwAWg">)</span><span class="w" id="mwAWk"> </span><span class="s" id="mwAWo">"*"</span><span class="w" id="mwAWs"> </span><span class="ow" id="mwAWw">=</span><span class="w" id="mwAW0"> </span><span class="p" id="mwAW4">(</span><span class="n" id="mwAW8">y</span><span class="w" id="mwAXA"> </span><span class="o" id="mwAXE">*</span><span class="w" id="mwAXI"> </span><span class="n" id="mwAXM">x</span><span class="p" id="mwAXQ">)</span><span class="kt" id="mwAXU">:</span><span class="n" id="mwAXY">zs</span> <span class="w" id="mwAXc"> </span><span class="n" id="mwAXg">f</span><span class="w" id="mwAXk"> </span><span class="p" id="mwAXo">(</span><span class="n" id="mwAXs">x</span><span class="kt" id="mwAXw">:</span><span class="n" id="mwAX0">y</span><span class="kt" id="mwAX4">:</span><span class="n" id="mwAX8">zs</span><span class="p" id="mwAYA">)</span><span class="w" id="mwAYE"> </span><span class="s" id="mwAYI">"/"</span><span class="w" id="mwAYM"> </span><span class="ow" id="mwAYQ">=</span><span class="w" id="mwAYU"> </span><span class="p" id="mwAYY">(</span><span class="n" id="mwAYc">y</span><span class="w" id="mwAYg"> </span><span class="o" id="mwAYk">/</span><span class="w" id="mwAYo"> </span><span class="n" id="mwAYs">x</span><span class="p" id="mwAYw">)</span><span class="kt" id="mwAY0">:</span><span class="n" id="mwAY4">zs</span> <span class="w" id="mwAY8"> </span><span class="n" id="mwAZA">f</span><span class="w" id="mwAZE"> </span><span class="p" id="mwAZI">(</span><span class="n" id="mwAZM">x</span><span class="kt" id="mwAZQ">:</span><span class="n" id="mwAZU">y</span><span class="kt" id="mwAZY">:</span><span class="n" id="mwAZc">zs</span><span class="p" id="mwAZg">)</span><span class="w" id="mwAZk"> </span><span class="s" id="mwAZo">"FLIP"</span><span class="w" id="mwAZs"> </span><span class="ow" id="mwAZw">=</span><span class="w" id="mwAZ0"> </span><span class="n" id="mwAZ4">y</span><span class="kt" id="mwAZ8">:</span><span class="n" id="mwAaA">x</span><span class="kt" id="mwAaE">:</span><span class="n" id="mwAaI">zs</span> <span class="w" id="mwAaM"> </span><span class="n" id="mwAaQ">f</span><span class="w" id="mwAaU"> </span><span class="n" id="mwAaY">zs</span><span class="w" id="mwAac"> </span><span class="n" id="mwAag">w</span><span class="w" id="mwAak"> </span><span class="ow" id="mwAao">=</span><span class="w" id="mwAas"> </span><span class="n" id="mwAaw">read</span><span class="w" id="mwAa0"> </span><span class="n" id="mwAa4">w</span><span class="w" id="mwAa8"> </span><span class="kt" id="mwAbA">:</span><span class="w" id="mwAbE"> </span><span class="n" id="mwAbI">zs</span>

The empty list is the initial state, and f interprets one word at a time, either as a function name, taking two numbers from the head of the list and pushing the result back in, or parsing the word as a floating-point number and prepending it to the list.

Fibonacci sequence

The following definition produces the list of Fibonacci numbers in linear time:

<span id="mwAbw"></span><span class="nf" id="mwAb0">fibs</span><span class="w" id="mwAb4"> </span><span class="ow" id="mwAb8">=</span><span class="w" id="mwAcA"> </span><span class="mi" id="mwAcE">0</span><span class="w" id="mwAcI"> </span><span class="kt" id="mwAcM">:</span><span class="w" id="mwAcQ"> </span><span class="mi" id="mwAcU">1</span><span class="w" id="mwAcY"> </span><span class="kt" id="mwAcc">:</span><span class="w" id="mwAcg"> </span><span class="n" id="mwAck">zipWith</span><span class="w" id="mwAco"> </span><span class="p" id="mwAcs">(</span><span class="o" id="mwAcw">+</span><span class="p" id="mwAc0">)</span><span class="w" id="mwAc4"> </span><span class="n" id="mwAc8">fibs</span><span class="w" id="mwAdA"> </span><span class="p" id="mwAdE">(</span><span class="n" id="mwAdI">tail</span><span class="w" id="mwAdM"> </span><span class="n" id="mwAdQ">fibs</span><span class="p" id="mwAdU">)</span>

The infinite list is produced by corecursion — the latter values of the list are computed on demand starting from the initial two items 0 and 1. This kind of a definition relies on lazy evaluation, an important feature of Haskell programming. For an example of how the evaluation evolves, the following illustrates the values of fibs and tail fibs after the computation of six items and shows how zipWith (+) has produced four items and proceeds to produce the next item:

fibs = 0 : 1 : 1 : 2 : 3 : 5 : ... <span typeof="mw:Entity" id="mwAd0"> </span> + + + + + + tail fibs = 1 : 1 : 2 : 3 : 5 : ... <span typeof="mw:Entity" id="mwAd4"> </span> = = = = = = zipWith ... = 1 : 2 : 3 : 5 : <i id="mwAd8"><b id="mwAeA">8</b></i> : ... fibs = 0 : 1 : 1 : 2 : 3 : 5 : <i id="mwAeE"><b id="mwAeI">8</b></i> : ...

The same function, written using Glasgow Haskell Compiler's parallel list comprehension syntax (GHC extensions must be enabled using a special command-line flag, here -XParallelListComp, or by starting the source file with {-# LANGUAGE ParallelListComp #-}):

<span id="mwAew"></span><span class="nf" id="mwAe0">fibs</span><span class="w" id="mwAe4"> </span><span class="ow" id="mwAe8">=</span><span class="w" id="mwAfA"> </span><span class="mi" id="mwAfE">0</span><span class="w" id="mwAfI"> </span><span class="kt" id="mwAfM">:</span><span class="w" id="mwAfQ"> </span><span class="mi" id="mwAfU">1</span><span class="w" id="mwAfY"> </span><span class="kt" id="mwAfc">:</span><span class="w" id="mwAfg"> </span><span class="p" id="mwAfk">[</span><span class="w" id="mwAfo"> </span><span class="n" id="mwAfs">a</span><span class="o" id="mwAfw">+</span><span class="n" id="mwAf0">b</span><span class="w" id="mwAf4"> </span><span class="o" id="mwAf8">|</span><span class="w" id="mwAgA"> </span><span class="n" id="mwAgE">a</span><span class="w" id="mwAgI"> </span><span class="ow" id="mwAgM"><-</span><span class="w" id="mwAgQ"> </span><span class="n" id="mwAgU">fibs</span><span class="w" id="mwAgY"> </span><span class="o" id="mwAgc">|</span><span class="w" id="mwAgg"> </span><span class="n" id="mwAgk">b</span><span class="w" id="mwAgo"> </span><span class="ow" id="mwAgs"><-</span><span class="w" id="mwAgw"> </span><span class="n" id="mwAg0">tail</span><span class="w" id="mwAg4"> </span><span class="n" id="mwAg8">fibs</span><span class="w" id="mwAhA"> </span><span class="p" id="mwAhE">]</span>

or with regular list comprehensions:

<span id="mwAhY"></span><span class="nf" id="mwAhc">fibs</span><span class="w" id="mwAhg"> </span><span class="ow" id="mwAhk">=</span><span class="w" id="mwAho"> </span><span class="mi" id="mwAhs">0</span><span class="w" id="mwAhw"> </span><span class="kt" id="mwAh0">:</span><span class="w" id="mwAh4"> </span><span class="mi" id="mwAh8">1</span><span class="w" id="mwAiA"> </span><span class="kt" id="mwAiE">:</span><span class="w" id="mwAiI"> </span><span class="p" id="mwAiM">[</span><span class="w" id="mwAiQ"> </span><span class="n" id="mwAiU">a</span><span class="o" id="mwAiY">+</span><span class="n" id="mwAic">b</span><span class="w" id="mwAig"> </span><span class="o" id="mwAik">|</span><span class="w" id="mwAio"> </span><span class="p" id="mwAis">(</span><span class="n" id="mwAiw">a</span><span class="p" id="mwAi0">,</span><span class="n" id="mwAi4">b</span><span class="p" id="mwAi8">)</span><span class="w" id="mwAjA"> </span><span class="ow" id="mwAjE"><-</span><span class="w" id="mwAjI"> </span><span class="n" id="mwAjM">zip</span><span class="w" id="mwAjQ"> </span><span class="n" id="mwAjU">fibs</span><span class="w" id="mwAjY"> </span><span class="p" id="mwAjc">(</span><span class="n" id="mwAjg">tail</span><span class="w" id="mwAjk"> </span><span class="n" id="mwAjo">fibs</span><span class="p" id="mwAjs">)</span><span class="w" id="mwAjw"> </span><span class="p" id="mwAj0">]</span>

or directly self-referencing:

<span id="mwAkE"></span><span class="nf" id="mwAkI">fibs</span><span class="w" id="mwAkM"> </span><span class="ow" id="mwAkQ">=</span><span class="w" id="mwAkU"> </span><span class="mi" id="mwAkY">0</span><span class="w" id="mwAkc"> </span><span class="kt" id="mwAkg">:</span><span class="w" id="mwAkk"> </span><span class="mi" id="mwAko">1</span><span class="w" id="mwAks"> </span><span class="kt" id="mwAkw">:</span><span class="w" id="mwAk0"> </span><span class="n" id="mwAk4">next</span><span class="w" id="mwAk8"> </span><span class="n" id="mwAlA">fibs</span><span class="w" id="mwAlE"> </span><span class="kr" id="mwAlI">where</span><span class="w" id="mwAlM"> </span><span class="n" id="mwAlQ">next</span><span class="w" id="mwAlU"> </span><span class="p" id="mwAlY">(</span><span class="n" id="mwAlc">a</span><span class="w" id="mwAlg"> </span><span class="kt" id="mwAlk">:</span><span class="w" id="mwAlo"> </span><span class="n" id="mwAls">t</span><span class="o" id="mwAlw">@</span><span class="p" id="mwAl0">(</span><span class="n" id="mwAl4">b</span><span class="kt" id="mwAl8">:</span><span class="kr" id="mwAmA">_</span><span class="p" id="mwAmE">))</span><span class="w" id="mwAmI"> </span><span class="ow" id="mwAmM">=</span><span class="w" id="mwAmQ"> </span><span class="p" id="mwAmU">(</span><span class="n" id="mwAmY">a</span><span class="o" id="mwAmc">+</span><span class="n" id="mwAmg">b</span><span class="p" id="mwAmk">)</span><span class="w" id="mwAmo"> </span><span class="kt" id="mwAms">:</span><span class="w" id="mwAmw"> </span><span class="n" id="mwAm0">next</span><span class="w" id="mwAm4"> </span><span class="n" id="mwAm8">t</span>

With stateful generating function:

<span id="mwAnU"></span><span class="nf" id="mwAnY">fibs</span><span class="w" id="mwAnc"> </span><span class="ow" id="mwAng">=</span><span class="w" id="mwAnk"> </span><span class="n" id="mwAno">next</span><span class="w" id="mwAns"> </span><span class="p" id="mwAnw">(</span><span class="mi" id="mwAn0">0</span><span class="p" id="mwAn4">,</span><span class="mi" id="mwAn8">1</span><span class="p" id="mwAoA">)</span><span class="w" id="mwAoE"> </span><span class="kr" id="mwAoI">where</span><span class="w" id="mwAoM"> </span><span class="n" id="mwAoQ">next</span><span class="w" id="mwAoU"> </span><span class="p" id="mwAoY">(</span><span class="n" id="mwAoc">a</span><span class="p" id="mwAog">,</span><span class="n" id="mwAok">b</span><span class="p" id="mwAoo">)</span><span class="w" id="mwAos"> </span><span class="ow" id="mwAow">=</span><span class="w" id="mwAo0"> </span><span class="n" id="mwAo4">a</span><span class="w" id="mwAo8"> </span><span class="kt" id="mwApA">:</span><span class="w" id="mwApE"> </span><span class="n" id="mwApI">next</span><span class="w" id="mwApM"> </span><span class="p" id="mwApQ">(</span><span class="n" id="mwApU">b</span><span class="p" id="mwApY">,</span><span class="w" id="mwApc"> </span><span class="n" id="mwApg">a</span><span class="o" id="mwApk">+</span><span class="n" id="mwApo">b</span><span class="p" id="mwAps">)</span>

or with unfoldr:

<span id="mwAqA"></span><span class="nf" id="mwAqE">fibs</span><span class="w" id="mwAqI"> </span><span class="ow" id="mwAqM">=</span><span class="w" id="mwAqQ"> </span><span class="n" id="mwAqU">unfoldr</span><span class="w" id="mwAqY"> </span><span class="p" id="mwAqc">(</span><span class="nf" id="mwAqg">\</span><span class="p" id="mwAqk">(</span><span class="n" id="mwAqo">a</span><span class="p" id="mwAqs">,</span><span class="n" id="mwAqw">b</span><span class="p" id="mwAq0">)</span><span class="w" id="mwAq4"> </span><span class="ow" id="mwAq8">-></span><span class="w" id="mwArA"> </span><span class="kt" id="mwArE">Just</span><span class="w" id="mwArI"> </span><span class="p" id="mwArM">(</span><span class="n" id="mwArQ">a</span><span class="p" id="mwArU">,</span><span class="w" id="mwArY"> </span><span class="p" id="mwArc">(</span><span class="n" id="mwArg">b</span><span class="p" id="mwArk">,</span><span class="w" id="mwAro"> </span><span class="n" id="mwArs">a</span><span class="o" id="mwArw">+</span><span class="n" id="mwAr0">b</span><span class="p" id="mwAr4">)))</span><span class="w" id="mwAr8"> </span><span class="p" id="mwAsA">(</span><span class="mi" id="mwAsE">0</span><span class="p" id="mwAsI">,</span><span class="w" id="mwAsM"> </span><span class="mi" id="mwAsQ">1</span><span class="p" id="mwAsU">)</span>

or scanl:

<span id="mwAso"></span><span class="nf" id="mwAss">fibs</span><span class="w" id="mwAsw"> </span><span class="ow" id="mwAs0">=</span><span class="w" id="mwAs4"> </span><span class="mi" id="mwAs8">0</span><span class="w" id="mwAtA"> </span><span class="kt" id="mwAtE">:</span><span class="w" id="mwAtI"> </span><span class="n" id="mwAtM">scanl</span><span class="w" id="mwAtQ"> </span><span class="p" id="mwAtU">(</span><span class="o" id="mwAtY">+</span><span class="p" id="mwAtc">)</span><span class="w" id="mwAtg"> </span><span class="mi" id="mwAtk">1</span><span class="w" id="mwAto"> </span><span class="n" id="mwAts">fibs</span>

Using data recursion with Haskell's predefined fixpoint combinator:

<span id="mwAuA"></span><span class="nf" id="mwAuE">fibs</span><span class="w" id="mwAuI"> </span><span class="ow" id="mwAuM">=</span><span class="w" id="mwAuQ"> </span><span class="n" id="mwAuU">fix</span><span class="w" id="mwAuY"> </span><span class="p" id="mwAuc">(</span><span class="nf" id="mwAug">\</span><span class="n" id="mwAuk">xs</span><span class="w" id="mwAuo"> </span><span class="ow" id="mwAus">-></span><span class="w" id="mwAuw"> </span><span class="mi" id="mwAu0">0</span><span class="w" id="mwAu4"> </span><span class="kt" id="mwAu8">:</span><span class="w" id="mwAvA"> </span><span class="mi" id="mwAvE">1</span><span class="w" id="mwAvI"> </span><span class="kt" id="mwAvM">:</span><span class="w" id="mwAvQ"> </span><span class="n" id="mwAvU">zipWith</span><span class="w" id="mwAvY"> </span><span class="p" id="mwAvc">(</span><span class="o" id="mwAvg">+</span><span class="p" id="mwAvk">)</span><span class="w" id="mwAvo"> </span><span class="n" id="mwAvs">xs</span><span class="w" id="mwAvw"> </span><span class="p" id="mwAv0">(</span><span class="n" id="mwAv4">tail</span><span class="w" id="mwAv8"> </span><span class="n" id="mwAwA">xs</span><span class="p" id="mwAwE">))</span><span class="w" id="mwAwI"> </span><span class="c1" id="mwAwM">-- zipWith version</span> <span class="w" id="mwAwQ"> </span><span class="ow" id="mwAwU">=</span><span class="w" id="mwAwY"> </span><span class="n" id="mwAwc">fix</span><span class="w" id="mwAwg"> </span><span class="p" id="mwAwk">((</span><span class="mi" id="mwAwo">0</span><span class="kt" id="mwAws">:</span><span class="p" id="mwAww">)</span><span class="w" id="mwAw0"> </span><span class="o" id="mwAw4">.</span><span class="w" id="mwAw8"> </span><span class="p" id="mwAxA">(</span><span class="mi" id="mwAxE">1</span><span class="kt" id="mwAxI">:</span><span class="p" id="mwAxM">)</span><span class="w" id="mwAxQ"> </span><span class="o" id="mwAxU">.</span><span class="w" id="mwAxY"> </span><span class="p" id="mwAxc">(</span><span class="n" id="mwAxg">zipWith</span><span class="w" id="mwAxk"> </span><span class="p" id="mwAxo">(</span><span class="o" id="mwAxs">+</span><span class="p" id="mwAxw">)</span><span class="w" id="mwAx0"> </span><span class="o" id="mwAx4"><*></span><span class="w" id="mwAx8"> </span><span class="n" id="mwAyA">tail</span><span class="p" id="mwAyE">))</span><span class="w" id="mwAyI"> </span><span class="c1" id="mwAyM">-- same as above, pointfree</span> <span class="w" id="mwAyQ"> </span><span class="ow" id="mwAyU">=</span><span class="w" id="mwAyY"> </span><span class="n" id="mwAyc">fix</span><span class="w" id="mwAyg"> </span><span class="p" id="mwAyk">((</span><span class="mi" id="mwAyo">0</span><span class="kt" id="mwAys">:</span><span class="p" id="mwAyw">)</span><span class="w" id="mwAy0"> </span><span class="o" id="mwAy4">.</span><span class="w" id="mwAy8"> </span><span class="n" id="mwAzA">scanl</span><span class="w" id="mwAzE"> </span><span class="p" id="mwAzI">(</span><span class="o" id="mwAzM">+</span><span class="p" id="mwAzQ">)</span><span class="w" id="mwAzU"> </span><span class="mi" id="mwAzY">1</span><span class="p" id="mwAzc">)</span><span class="w" id="mwAzg"> </span><span class="c1" id="mwAzk">-- scanl version</span>

Factorial

The factorial we saw previously can be written as a sequence of functions:

<span id="mwAz4"></span><span class="nf" id="mwAz8">factorial</span><span class="w" id="mwA0A"> </span><span class="n" id="mwA0E">n</span><span class="w" id="mwA0I"> </span><span class="ow" id="mwA0M">=</span><span class="w" id="mwA0Q"> </span><span class="n" id="mwA0U">foldr</span><span class="w" id="mwA0Y"> </span><span class="p" id="mwA0c">((</span><span class="o" id="mwA0g">.</span><span class="p" id="mwA0k">)</span><span class="w" id="mwA0o"> </span><span class="o" id="mwA0s">.</span><span class="w" id="mwA0w"> </span><span class="p" id="mwA00">(</span><span class="o" id="mwA04">*</span><span class="p" id="mwA08">))</span><span class="w" id="mwA1A"> </span><span class="n" id="mwA1E">id</span><span class="w" id="mwA1I"> </span><span class="p" id="mwA1M">[</span><span class="mi" id="mwA1Q">1</span><span class="o" id="mwA1U">..</span><span class="n" id="mwA1Y">n</span><span class="p" id="mwA1c">]</span><span class="w" id="mwA1g"> </span><span class="o" id="mwA1k">$</span><span class="w" id="mwA1o"> </span><span class="mi" id="mwA1s">1</span> <span class="c1" id="mwA1w">-- factorial 5 == ((1*) .) ( ((2*) .) ( ((3*) .) ( ((4*) .) ( ((5*) .) id )))) 1</span> <span class="c1" id="mwA10">-- == (1*) . (2*) . (3*) . (4*) . (5*) . id $ 1</span> <span class="c1" id="mwA14">-- == 1* ( 2* ( 3* ( 4* ( 5* ( id 1 )))))</span> <span class="nf" id="mwA18">factorial</span><span class="w" id="mwA2A"> </span><span class="n" id="mwA2E">n</span><span class="w" id="mwA2I"> </span><span class="ow" id="mwA2M">=</span><span class="w" id="mwA2Q"> </span><span class="n" id="mwA2U">foldr</span><span class="w" id="mwA2Y"> </span><span class="p" id="mwA2c">((</span><span class="o" id="mwA2g">.</span><span class="p" id="mwA2k">)</span><span class="w" id="mwA2o"> </span><span class="o" id="mwA2s">.</span><span class="w" id="mwA2w"> </span><span class="p" id="mwA20">(</span><span class="o" id="mwA24">*</span><span class="p" id="mwA28">))</span><span class="w" id="mwA3A"> </span><span class="p" id="mwA3E">(</span><span class="n" id="mwA3I">const</span><span class="w" id="mwA3M"> </span><span class="mi" id="mwA3Q">1</span><span class="p" id="mwA3U">)</span><span class="w" id="mwA3Y"> </span><span class="p" id="mwA3c">[</span><span class="mi" id="mwA3g">1</span><span class="o" id="mwA3k">..</span><span class="n" id="mwA3o">n</span><span class="p" id="mwA3s">]</span><span class="w" id="mwA3w"> </span><span class="o" id="mwA30">$</span><span class="w" id="mwA34"> </span><span class="nb" id="mwA38">()</span> <span class="c1" id="mwA4A">-- factorial 5 == ((1*) .) ( ((2*) .) ( ((3*) .) ( ((4*) .) ( ((5*) .) (const 1) )))) ()</span> <span class="c1" id="mwA4E">-- == (1*) . (2*) . (3*) . (4*) . (5*) . const 1 $ ()</span> <span class="c1" id="mwA4I">-- == 1* ( 2* ( 3* ( 4* ( 5* ( const 1 () )))))</span> <span class="nf" id="mwA4M">factorial</span><span class="w" id="mwA4Q"> </span><span class="n" id="mwA4U">n</span><span class="w" id="mwA4Y"> </span><span class="ow" id="mwA4c">=</span><span class="w" id="mwA4g"> </span><span class="n" id="mwA4k">foldr</span><span class="w" id="mwA4o"> </span><span class="p" id="mwA4s">((</span><span class="o" id="mwA4w">$</span><span class="p" id="mwA40">)</span><span class="w" id="mwA44"> </span><span class="o" id="mwA48">.</span><span class="w" id="mwA5A"> </span><span class="p" id="mwA5E">(</span><span class="o" id="mwA5I">*</span><span class="p" id="mwA5M">))</span><span class="w" id="mwA5Q"> </span><span class="mi" id="mwA5U">1</span><span class="w" id="mwA5Y"> </span><span class="p" id="mwA5c">[</span><span class="mi" id="mwA5g">1</span><span class="o" id="mwA5k">..</span><span class="n" id="mwA5o">n</span><span class="p" id="mwA5s">]</span><span class="w" id="mwA5w"> </span><span class="ow" id="mwA50">=</span><span class="w" id="mwA54"> </span><span class="n" id="mwA58">foldr</span><span class="w" id="mwA6A"> </span><span class="p" id="mwA6E">(</span><span class="o" id="mwA6I">$</span><span class="p" id="mwA6M">)</span><span class="w" id="mwA6Q"> </span><span class="mi" id="mwA6U">1</span><span class="w" id="mwA6Y"> </span><span class="o" id="mwA6c">$</span><span class="w" id="mwA6g"> </span><span class="n" id="mwA6k">map</span><span class="w" id="mwA6o"> </span><span class="p" id="mwA6s">(</span><span class="o" id="mwA6w">*</span><span class="p" id="mwA60">)</span><span class="w" id="mwA64"> </span><span class="p" id="mwA68">[</span><span class="mi" id="mwA7A">1</span><span class="o" id="mwA7E">..</span><span class="n" id="mwA7I">n</span><span class="p" id="mwA7M">]</span> <span class="c1" id="mwA7Q">-- factorial 5 == ((1*) $) ( ((2*) $) ( ((3*) $) ( ((4*) $) ( ((5*) $) 1 ))))</span> <span class="c1" id="mwA7U">-- == (1*) $ (2*) $ (3*) $ (4*) $ (5*) $ 1</span> <span class="c1" id="mwA7Y">-- == 1* ( 2* ( 3* ( 4* ( 5* 1 ))))</span>

More examples

Hamming numbers

A remarkably concise function that returns the list of Hamming numbers in order:

<span id="mwA70"></span><span class="nf" id="mwA74">hamming</span><span class="w" id="mwA78"> </span><span class="ow" id="mwA8A">=</span><span class="w" id="mwA8E"> </span><span class="mi" id="mwA8I">1</span><span class="w" id="mwA8M"> </span><span class="kt" id="mwA8Q">:</span><span class="w" id="mwA8U"> </span><span class="n" id="mwA8Y">map</span><span class="w" id="mwA8c"> </span><span class="p" id="mwA8g">(</span><span class="mi" id="mwA8k">2</span><span class="o" id="mwA8o">*</span><span class="p" id="mwA8s">)</span><span class="w" id="mwA8w"> </span><span class="n" id="mwA80">hamming</span><span class="w" id="mwA84"> </span><span class="p" id="mwA88">`</span><span class="n" id="mwA9A">union</span><span class="p" id="mwA9E">`</span><span class="w" id="mwA9I"> </span><span class="n" id="mwA9M">map</span><span class="w" id="mwA9Q"> </span><span class="p" id="mwA9U">(</span><span class="mi" id="mwA9Y">3</span><span class="o" id="mwA9c">*</span><span class="p" id="mwA9g">)</span><span class="w" id="mwA9k"> </span><span class="n" id="mwA9o">hamming</span><span class="w" id="mwA9s"> </span> <span class="w" id="mwA9w"> </span><span class="p" id="mwA90">`</span><span class="n" id="mwA94">union</span><span class="p" id="mwA98">`</span><span class="w" id="mwA-A"> </span><span class="n" id="mwA-E">map</span><span class="w" id="mwA-I"> </span><span class="p" id="mwA-M">(</span><span class="mi" id="mwA-Q">5</span><span class="o" id="mwA-U">*</span><span class="p" id="mwA-Y">)</span><span class="w" id="mwA-c"> </span><span class="n" id="mwA-g">hamming</span>

Like the various fibs solutions displayed above, this uses corecursion to produce a list of numbers on demand, starting from the base case of 1 and building new items based on the preceding part of the list.

Here the function union is used as an operator by enclosing it in back-quotes. Its case clauses define how it merges two ascending lists into one ascending list without duplicate items, representing sets as ordered lists. Its companion function minus implements set difference:

It is possible to generate only the unique multiples, for more efficient operation. Since there are no duplicates, there's no need to remove them:

<span id="mwBLA"></span><span class="nf" id="mwBLE">smooth235</span><span class="w" id="mwBLI"> </span><span class="ow" id="mwBLM">=</span><span class="w" id="mwBLQ"> </span><span class="mi" id="mwBLU">1</span><span class="w" id="mwBLY"> </span><span class="kt" id="mwBLc">:</span><span class="w" id="mwBLg"> </span><span class="n" id="mwBLk">foldr</span><span class="w" id="mwBLo"> </span><span class="p" id="mwBLs">(</span><span class="nf" id="mwBLw">\</span><span class="n" id="mwBL0">p</span><span class="w" id="mwBL4"> </span><span class="n" id="mwBL8">s</span><span class="w" id="mwBMA"> </span><span class="ow" id="mwBME">-></span><span class="w" id="mwBMI"> </span><span class="n" id="mwBMM">fix</span><span class="w" id="mwBMQ"> </span><span class="o" id="mwBMU">$</span><span class="w" id="mwBMY"> </span><span class="n" id="mwBMc">mergeBy</span><span class="w" id="mwBMg"> </span><span class="p" id="mwBMk">(</span><span class="o" id="mwBMo"><</span><span class="p" id="mwBMs">)</span><span class="w" id="mwBMw"> </span><span class="n" id="mwBM0">s</span><span class="w" id="mwBM4"> </span><span class="o" id="mwBM8">.</span><span class="w" id="mwBNA"> </span><span class="n" id="mwBNE">map</span><span class="w" id="mwBNI"> </span><span class="p" id="mwBNM">(</span><span class="n" id="mwBNQ">p</span><span class="o" id="mwBNU">*</span><span class="p" id="mwBNY">)</span><span class="w" id="mwBNc"> </span><span class="o" id="mwBNg">.</span><span class="w" id="mwBNk"> </span><span class="p" id="mwBNo">(</span><span class="mi" id="mwBNs">1</span><span class="kt" id="mwBNw">:</span><span class="p" id="mwBN0">))</span><span class="w" id="mwBN4"> </span><span class="kt" id="mwBN8">[]</span><span class="w" id="mwBOA"> </span><span class="p" id="mwBOE">[</span><span class="mi" id="mwBOI">2</span><span class="p" id="mwBOM">,</span><span class="mi" id="mwBOQ">3</span><span class="p" id="mwBOU">,</span><span class="mi" id="mwBOY">5</span><span class="p" id="mwBOc">]</span> <span class="w" id="mwBOg"> </span><span class="kr" id="mwBOk">where</span> <span class="w" id="mwBOo"> </span><span class="n" id="mwBOs">fix</span><span class="w" id="mwBOw"> </span><span class="n" id="mwBO0">f</span><span class="w" id="mwBO4"> </span><span class="ow" id="mwBO8">=</span><span class="w" id="mwBPA"> </span><span class="n" id="mwBPE">x</span><span class="w" id="mwBPI"> </span><span class="kr" id="mwBPM">where</span><span class="w" id="mwBPQ"> </span><span class="n" id="mwBPU">x</span><span class="w" id="mwBPY"> </span><span class="ow" id="mwBPc">=</span><span class="w" id="mwBPg"> </span><span class="n" id="mwBPk">f</span><span class="w" id="mwBPo"> </span><span class="n" id="mwBPs">x</span><span class="w" id="mwBPw"> </span><span class="c1" id="mwBP0">-- fixpoint combinator, with sharing</span>

This uses the more efficient function merge which doesn't concern itself with the duplicates (also used in the following next function, mergesort ):

<span id="mwBQM"></span><span class="nf" id="mwBQQ">mergeBy</span><span class="w" id="mwBQU"> </span><span class="n" id="mwBQY">less</span><span class="w" id="mwBQc"> </span><span class="n" id="mwBQg">xs</span><span class="w" id="mwBQk"> </span><span class="n" id="mwBQo">ys</span><span class="w" id="mwBQs"> </span><span class="ow" id="mwBQw">=</span><span class="w" id="mwBQ0"> </span><span class="n" id="mwBQ4">merge</span><span class="w" id="mwBQ8"> </span><span class="n" id="mwBRA">xs</span><span class="w" id="mwBRE"> </span><span class="n" id="mwBRI">ys</span><span class="w" id="mwBRM"> </span><span class="kr" id="mwBRQ">where</span> <span class="w" id="mwBRU"> </span><span class="n" id="mwBRY">merge</span><span class="w" id="mwBRc"> </span><span class="n" id="mwBRg">xs</span><span class="w" id="mwBRk"> </span><span class="kt" id="mwBRo">[]</span><span class="w" id="mwBRs"> </span><span class="ow" id="mwBRw">=</span><span class="w" id="mwBR0"> </span><span class="n" id="mwBR4">xs</span><span class="w" id="mwBR8"> </span> <span class="w" id="mwBSA"> </span><span class="n" id="mwBSE">merge</span><span class="w" id="mwBSI"> </span><span class="kt" id="mwBSM">[]</span><span class="w" id="mwBSQ"> </span><span class="n" id="mwBSU">ys</span><span class="w" id="mwBSY"> </span><span class="ow" id="mwBSc">=</span><span class="w" id="mwBSg"> </span><span class="n" id="mwBSk">ys</span> <span class="w" id="mwBSo"> </span><span class="n" id="mwBSs">merge</span><span class="w" id="mwBSw"> </span><span class="p" id="mwBS0">(</span><span class="n" id="mwBS4">x</span><span class="kt" id="mwBS8">:</span><span class="n" id="mwBTA">xs</span><span class="p" id="mwBTE">)</span><span class="w" id="mwBTI"> </span><span class="p" id="mwBTM">(</span><span class="n" id="mwBTQ">y</span><span class="kt" id="mwBTU">:</span><span class="n" id="mwBTY">ys</span><span class="p" id="mwBTc">)</span><span class="w" id="mwBTg"> </span><span class="o" id="mwBTk">|</span><span class="w" id="mwBTo"> </span><span class="n" id="mwBTs">less</span><span class="w" id="mwBTw"> </span><span class="n" id="mwBT0">y</span><span class="w" id="mwBT4"> </span><span class="n" id="mwBT8">x</span><span class="w" id="mwBUA"> </span><span class="ow" id="mwBUE">=</span><span class="w" id="mwBUI"> </span><span class="n" id="mwBUM">y</span><span class="w" id="mwBUQ"> </span><span class="kt" id="mwBUU">:</span><span class="w" id="mwBUY"> </span><span class="n" id="mwBUc">merge</span><span class="w" id="mwBUg"> </span><span class="p" id="mwBUk">(</span><span class="n" id="mwBUo">x</span><span class="kt" id="mwBUs">:</span><span class="n" id="mwBUw">xs</span><span class="p" id="mwBU0">)</span><span class="w" id="mwBU4"> </span><span class="n" id="mwBU8">ys</span> <span class="w" id="mwBVA"> </span><span class="o" id="mwBVE">|</span><span class="w" id="mwBVI"> </span><span class="n" id="mwBVM">otherwise</span><span class="w" id="mwBVQ"> </span><span class="ow" id="mwBVU">=</span><span class="w" id="mwBVY"> </span><span class="n" id="mwBVc">x</span><span class="w" id="mwBVg"> </span><span class="kt" id="mwBVk">:</span><span class="w" id="mwBVo"> </span><span class="n" id="mwBVs">merge</span><span class="w" id="mwBVw"> </span><span class="n" id="mwBV0">xs</span><span class="w" id="mwBV4"> </span><span class="p" id="mwBV8">(</span><span class="n" id="mwBWA">y</span><span class="kt" id="mwBWE">:</span><span class="n" id="mwBWI">ys</span><span class="p" id="mwBWM">)</span>

Each vertical bar ( | ) starts a guard clause with a guard expression before the = sign and the corresponding definition after it, that is evaluated if the guard is true.

Mergesort

Here is a bottom-up merge sort, defined using the higher-order function until:

<span id="mwBXA"></span><span class="nf" id="mwBXE">mergesortBy</span><span class="w" id="mwBXI"> </span><span class="n" id="mwBXM">less</span><span class="w" id="mwBXQ"> </span><span class="kt" id="mwBXU">[]</span><span class="w" id="mwBXY"> </span><span class="ow" id="mwBXc">=</span><span class="w" id="mwBXg"> </span><span class="kt" id="mwBXk">[]</span> <span class="nf" id="mwBXo">mergesortBy</span><span class="w" id="mwBXs"> </span><span class="n" id="mwBXw">less</span><span class="w" id="mwBX0"> </span><span class="n" id="mwBX4">xs</span><span class="w" id="mwBX8"> </span><span class="ow" id="mwBYA">=</span><span class="w" id="mwBYE"> </span><span class="n" id="mwBYI">head</span><span class="w" id="mwBYM"> </span><span class="o" id="mwBYQ">$</span> <span class="w" id="mwBYU"> </span><span class="n" id="mwBYY">until</span><span class="w" id="mwBYc"> </span><span class="p" id="mwBYg">(</span><span class="n" id="mwBYk">null</span><span class="w" id="mwBYo"> </span><span class="o" id="mwBYs">.</span><span class="w" id="mwBYw"> </span><span class="n" id="mwBY0">tail</span><span class="p" id="mwBY4">)</span><span class="w" id="mwBY8"> </span><span class="p" id="mwBZA">(</span><span class="n" id="mwBZE">pairwise</span><span class="w" id="mwBZI"> </span><span class="o" id="mwBZM">$</span><span class="w" id="mwBZQ"> </span><span class="n" id="mwBZU">mergeBy</span><span class="w" id="mwBZY"> </span><span class="n" id="mwBZc">less</span><span class="p" id="mwBZg">)</span><span class="w" id="mwBZk"> </span><span class="p" id="mwBZo">[[</span><span class="n" id="mwBZs">x</span><span class="p" id="mwBZw">]</span><span class="w" id="mwBZ0"> </span><span class="o" id="mwBZ4">|</span><span class="w" id="mwBZ8"> </span><span class="n" id="mwBaA">x</span><span class="w" id="mwBaE"> </span><span class="ow" id="mwBaI"><-</span><span class="w" id="mwBaM"> </span><span class="n" id="mwBaQ">xs</span><span class="p" id="mwBaU">]</span> <span class="nf" id="mwBaY">pairwise</span><span class="w" id="mwBac"> </span><span class="n" id="mwBag">f</span><span class="w" id="mwBak"> </span><span class="p" id="mwBao">(</span><span class="n" id="mwBas">a</span><span class="kt" id="mwBaw">:</span><span class="n" id="mwBa0">b</span><span class="kt" id="mwBa4">:</span><span class="n" id="mwBa8">t</span><span class="p" id="mwBbA">)</span><span class="w" id="mwBbE"> </span><span class="ow" id="mwBbI">=</span><span class="w" id="mwBbM"> </span><span class="n" id="mwBbQ">f</span><span class="w" id="mwBbU"> </span><span class="n" id="mwBbY">a</span><span class="w" id="mwBbc"> </span><span class="n" id="mwBbg">b</span><span class="w" id="mwBbk"> </span><span class="kt" id="mwBbo">:</span><span class="w" id="mwBbs"> </span><span class="n" id="mwBbw">pairwise</span><span class="w" id="mwBb0"> </span><span class="n" id="mwBb4">f</span><span class="w" id="mwBb8"> </span><span class="n" id="mwBcA">t</span> <span class="nf" id="mwBcE">pairwise</span><span class="w" id="mwBcI"> </span><span class="n" id="mwBcM">f</span><span class="w" id="mwBcQ"> </span><span class="n" id="mwBcU">t</span><span class="w" id="mwBcY"> </span><span class="ow" id="mwBcc">=</span><span class="w" id="mwBcg"> </span><span class="n" id="mwBck">t</span>

Prime numbers

The mathematical definition of primes can be translated pretty much word for word into Haskell:

<span id="mwBc8"></span><span class="c1" id="mwBdA">-- "Integers above 1 that cannot be divided by a smaller integer above 1"</span> <span class="c1" id="mwBdE">-- primes = { n ∈ [2..] | ~ ∃ d ∈ [2..n-1] ⇒ rem n d = 0 }</span> <span class="c1" id="mwBdI">-- = { n ∈ [2..] | ∀ d ∈ [2..n-1] ⇒ rem n d ≠ 0 }</span> <span class="nf" id="mwBdM">primes</span><span class="w" id="mwBdQ"> </span><span class="ow" id="mwBdU">=</span><span class="w" id="mwBdY"> </span><span class="p" id="mwBdc">[</span><span class="w" id="mwBdg"> </span><span class="n" id="mwBdk">n</span><span class="w" id="mwBdo"> </span><span class="o" id="mwBds">|</span><span class="w" id="mwBdw"> </span><span class="n" id="mwBd0">n</span><span class="w" id="mwBd4"> </span><span class="ow" id="mwBd8"><-</span><span class="w" id="mwBeA"> </span><span class="p" id="mwBeE">[</span><span class="mi" id="mwBeI">2</span><span class="o" id="mwBeM">..</span><span class="p" id="mwBeQ">],</span><span class="w" id="mwBeU"> </span><span class="n" id="mwBeY">all</span><span class="w" id="mwBec"> </span><span class="p" id="mwBeg">(</span><span class="nf" id="mwBek">\</span><span class="n" id="mwBeo">d</span><span class="w" id="mwBes"> </span><span class="ow" id="mwBew">-></span><span class="w" id="mwBe0"> </span><span class="n" id="mwBe4">rem</span><span class="w" id="mwBe8"> </span><span class="n" id="mwBfA">n</span><span class="w" id="mwBfE"> </span><span class="n" id="mwBfI">d</span><span class="w" id="mwBfM"> </span><span class="o" id="mwBfQ">/=</span><span class="w" id="mwBfU"> </span><span class="mi" id="mwBfY">0</span><span class="p" id="mwBfc">)</span><span class="w" id="mwBfg"> </span><span class="p" id="mwBfk">[</span><span class="mi" id="mwBfo">2</span><span class="o" id="mwBfs">..</span><span class="p" id="mwBfw">(</span><span class="n" id="mwBf0">n</span><span class="o" id="mwBf4">-</span><span class="mi" id="mwBf8">1</span><span class="p" id="mwBgA">)]</span><span class="w" id="mwBgE"> </span><span class="p" id="mwBgI">]</span>

This finds primes by trial division. Note that it is not optimized for efficiency and has very poor performance. Slightly faster (but still very slow) is this code by David Turner:

<span id="mwBgw"></span><span class="nf" id="mwBg0">primes</span><span class="w" id="mwBg4"> </span><span class="ow" id="mwBg8">=</span><span class="w" id="mwBhA"> </span><span class="n" id="mwBhE">sieve</span><span class="w" id="mwBhI"> </span><span class="p" id="mwBhM">[</span><span class="mi" id="mwBhQ">2</span><span class="o" id="mwBhU">..</span><span class="p" id="mwBhY">]</span><span class="w" id="mwBhc"> </span><span class="kr" id="mwBhg">where</span><span class="w" id="mwBhk"> </span> <span class="w" id="mwBho"> </span><span class="n" id="mwBhs">sieve</span><span class="w" id="mwBhw"> </span><span class="p" id="mwBh0">(</span><span class="n" id="mwBh4">p</span><span class="kt" id="mwBh8">:</span><span class="n" id="mwBiA">xs</span><span class="p" id="mwBiE">)</span><span class="w" id="mwBiI"> </span><span class="ow" id="mwBiM">=</span><span class="w" id="mwBiQ"> </span><span class="n" id="mwBiU">p</span><span class="w" id="mwBiY"> </span><span class="kt" id="mwBic">:</span><span class="w" id="mwBig"> </span><span class="n" id="mwBik">sieve</span><span class="w" id="mwBio"> </span><span class="p" id="mwBis">[</span><span class="n" id="mwBiw">x</span><span class="w" id="mwBi0"> </span><span class="o" id="mwBi4">|</span><span class="w" id="mwBi8"> </span><span class="n" id="mwBjA">x</span><span class="w" id="mwBjE"> </span><span class="ow" id="mwBjI"><-</span><span class="w" id="mwBjM"> </span><span class="n" id="mwBjQ">xs</span><span class="p" id="mwBjU">,</span><span class="w" id="mwBjY"> </span><span class="n" id="mwBjc">rem</span><span class="w" id="mwBjg"> </span><span class="n" id="mwBjk">x</span><span class="w" id="mwBjo"> </span><span class="n" id="mwBjs">p</span><span class="w" id="mwBjw"> </span><span class="o" id="mwBj0">/=</span><span class="w" id="mwBj4"> </span><span class="mi" id="mwBj8">0</span><span class="p" id="mwBkA">]</span>

Much faster is the optimal trial division algorithm

<span id="mwBkQ"></span><span class="nf" id="mwBkU">primes</span><span class="w" id="mwBkY"> </span><span class="ow" id="mwBkc">=</span><span class="w" id="mwBkg"> </span><span class="mi" id="mwBkk">2</span><span class="w" id="mwBko"> </span><span class="kt" id="mwBks">:</span><span class="w" id="mwBkw"> </span><span class="p" id="mwBk0">[</span><span class="w" id="mwBk4"> </span><span class="n" id="mwBk8">n</span><span class="w" id="mwBlA"> </span><span class="o" id="mwBlE">|</span><span class="w" id="mwBlI"> </span><span class="n" id="mwBlM">n</span><span class="w" id="mwBlQ"> </span><span class="ow" id="mwBlU"><-</span><span class="w" id="mwBlY"> </span><span class="p" id="mwBlc">[</span><span class="mi" id="mwBlg">3</span><span class="o" id="mwBlk">..</span><span class="p" id="mwBlo">],</span><span class="w" id="mwBls"> </span><span class="n" id="mwBlw">all</span><span class="w" id="mwBl0"> </span><span class="p" id="mwBl4">((</span><span class="o" id="mwBl8">></span><span class="w" id="mwBmA"> </span><span class="mi" id="mwBmE">0</span><span class="p" id="mwBmI">)</span><span class="w" id="mwBmM"> </span><span class="o" id="mwBmQ">.</span><span class="w" id="mwBmU"> </span><span class="n" id="mwBmY">rem</span><span class="w" id="mwBmc"> </span><span class="n" id="mwBmg">n</span><span class="p" id="mwBmk">)</span><span class="w" id="mwBmo"> </span><span class="o" id="mwBms">$</span><span class="w" id="mwBmw"> </span> <span class="w" id="mwBm0"> </span><span class="n" id="mwBm4">takeWhile</span><span class="w" id="mwBm8"> </span><span class="p" id="mwBnA">((</span><span class="o" id="mwBnE"><=</span><span class="w" id="mwBnI"> </span><span class="n" id="mwBnM">n</span><span class="p" id="mwBnQ">)</span><span class="w" id="mwBnU"> </span><span class="o" id="mwBnY">.</span><span class="w" id="mwBnc"> </span><span class="p" id="mwBng">(</span><span class="o" id="mwBnk">^</span><span class="mi" id="mwBno">2</span><span class="p" id="mwBns">))</span><span class="w" id="mwBnw"> </span><span class="n" id="mwBn0">primes</span><span class="p" id="mwBn4">]</span>

or an unbounded sieve of Eratosthenes with postponed sieving in stages,

<span id="mwBoc"></span><span class="nf" id="mwBog">primes</span><span class="w" id="mwBok"> </span><span class="ow" id="mwBoo">=</span><span class="w" id="mwBos"> </span><span class="mi" id="mwBow">2</span><span class="w" id="mwBo0"> </span><span class="kt" id="mwBo4">:</span><span class="w" id="mwBo8"> </span><span class="n" id="mwBpA">sieve</span><span class="w" id="mwBpE"> </span><span class="n" id="mwBpI">primes</span><span class="w" id="mwBpM"> </span><span class="p" id="mwBpQ">[</span><span class="mi" id="mwBpU">3</span><span class="o" id="mwBpY">..</span><span class="p" id="mwBpc">]</span><span class="w" id="mwBpg"> </span><span class="kr" id="mwBpk">where</span> <span class="w" id="mwBpo"> </span><span class="n" id="mwBps">sieve</span><span class="w" id="mwBpw"> </span><span class="p" id="mwBp0">(</span><span class="n" id="mwBp4">p</span><span class="kt" id="mwBp8">:</span><span class="n" id="mwBqA">ps</span><span class="p" id="mwBqE">)</span><span class="w" id="mwBqI"> </span><span class="p" id="mwBqM">(</span><span class="n" id="mwBqQ">span</span><span class="w" id="mwBqU"> </span><span class="p" id="mwBqY">(</span><span class="o" id="mwBqc"><</span><span class="w" id="mwBqg"> </span><span class="n" id="mwBqk">p</span><span class="o" id="mwBqo">*</span><span class="n" id="mwBqs">p</span><span class="p" id="mwBqw">)</span><span class="w" id="mwBq0"> </span><span class="ow" id="mwBq4">-></span><span class="w" id="mwBq8"> </span><span class="p" id="mwBrA">(</span><span class="n" id="mwBrE">h</span><span class="p" id="mwBrI">,</span><span class="w" id="mwBrM"> </span><span class="n" id="mwBrQ">t</span><span class="p" id="mwBrU">))</span><span class="w" id="mwBrY"> </span><span class="ow" id="mwBrc">=</span><span class="w" id="mwBrg"> </span> <span class="w" id="mwBrk"> </span><span class="n" id="mwBro">h</span><span class="w" id="mwBrs"> </span><span class="o" id="mwBrw">++</span><span class="w" id="mwBr0"> </span><span class="n" id="mwBr4">sieve</span><span class="w" id="mwBr8"> </span><span class="n" id="mwBsA">ps</span><span class="w" id="mwBsE"> </span><span class="p" id="mwBsI">(</span><span class="n" id="mwBsM">minus</span><span class="w" id="mwBsQ"> </span><span class="n" id="mwBsU">t</span><span class="w" id="mwBsY"> </span><span class="p" id="mwBsc">[</span><span class="n" id="mwBsg">p</span><span class="o" id="mwBsk">*</span><span class="n" id="mwBso">p</span><span class="p" id="mwBss">,</span><span class="w" id="mwBsw"> </span><span class="n" id="mwBs0">p</span><span class="o" id="mwBs4">*</span><span class="n" id="mwBs8">p</span><span class="o" id="mwBtA">+</span><span class="n" id="mwBtE">p</span><span class="o" id="mwBtI">..</span><span class="p" id="mwBtM">])</span>

or the combined sieve implementation by Richard Bird,

<span id="mwBtw"></span><span class="c1" id="mwBt0">-- "Integers above 1 without any composite numbers which</span> <span class="c1" id="mwBt4">-- are found by enumeration of each prime's multiples"</span> <span class="nf" id="mwBt8">primes</span><span class="w" id="mwBuA"> </span><span class="ow" id="mwBuE">=</span><span class="w" id="mwBuI"> </span><span class="mi" id="mwBuM">2</span><span class="w" id="mwBuQ"> </span><span class="kt" id="mwBuU">:</span><span class="w" id="mwBuY"> </span><span class="n" id="mwBuc">minus</span><span class="w" id="mwBug"> </span><span class="p" id="mwBuk">[</span><span class="mi" id="mwBuo">3</span><span class="o" id="mwBus">..</span><span class="p" id="mwBuw">]</span> <span class="w" id="mwBu0"> </span><span class="p" id="mwBu4">(</span><span class="n" id="mwBu8">foldr</span><span class="w" id="mwBvA"> </span><span class="p" id="mwBvE">(</span><span class="nf" id="mwBvI">\</span><span class="p" id="mwBvM">(</span><span class="n" id="mwBvQ">m</span><span class="kt" id="mwBvU">:</span><span class="n" id="mwBvY">ms</span><span class="p" id="mwBvc">)</span><span class="w" id="mwBvg"> </span><span class="n" id="mwBvk">r</span><span class="w" id="mwBvo"> </span><span class="ow" id="mwBvs">-></span><span class="w" id="mwBvw"> </span><span class="n" id="mwBv0">m</span><span class="w" id="mwBv4"> </span><span class="kt" id="mwBv8">:</span><span class="w" id="mwBwA"> </span><span class="n" id="mwBwE">union</span><span class="w" id="mwBwI"> </span><span class="n" id="mwBwM">ms</span><span class="w" id="mwBwQ"> </span><span class="n" id="mwBwU">r</span><span class="p" id="mwBwY">)</span><span class="w" id="mwBwc"> </span><span class="kt" id="mwBwg">[]</span><span class="w" id="mwBwk"> </span> <span class="w" id="mwBwo"> </span><span class="p" id="mwBws">[[</span><span class="n" id="mwBww">p</span><span class="o" id="mwBw0">*</span><span class="n" id="mwBw4">p</span><span class="p" id="mwBw8">,</span><span class="w" id="mwBxA"> </span><span class="n" id="mwBxE">p</span><span class="o" id="mwBxI">*</span><span class="n" id="mwBxM">p</span><span class="o" id="mwBxQ">+</span><span class="n" id="mwBxU">p</span><span class="w" id="mwBxY"> </span><span class="o" id="mwBxc">..</span><span class="p" id="mwBxg">]</span><span class="w" id="mwBxk"> </span><span class="o" id="mwBxo">|</span><span class="w" id="mwBxs"> </span><span class="n" id="mwBxw">p</span><span class="w" id="mwBx0"> </span><span class="ow" id="mwBx4"><-</span><span class="w" id="mwBx8"> </span><span class="n" id="mwByA">primes</span><span class="p" id="mwByE">])</span>

or an even faster tree-like folding variant with nearly optimal (for a list-based code) time complexity and very low space complexity achieved through telescoping multistage recursive production of primes:

<span id="mwByo"></span><span class="nf" id="mwBys">primes</span><span class="w" id="mwByw"> </span><span class="ow" id="mwBy0">=</span><span class="w" id="mwBy4"> </span><span class="mi" id="mwBy8">2</span><span class="w" id="mwBzA"> </span><span class="kt" id="mwBzE">:</span><span class="w" id="mwBzI"> </span><span class="n" id="mwBzM">_Y</span><span class="w" id="mwBzQ"> </span><span class="p" id="mwBzU">((</span><span class="mi" id="mwBzY">3</span><span class="w" id="mwBzc"> </span><span class="kt" id="mwBzg">:</span><span class="p" id="mwBzk">)</span><span class="w" id="mwBzo"> </span><span class="o" id="mwBzs">.</span><span class="w" id="mwBzw"> </span><span class="n" id="mwBz0">minus</span><span class="w" id="mwBz4"> </span><span class="p" id="mwBz8">[</span><span class="mi" id="mwB0A">5</span><span class="p" id="mwB0E">,</span><span class="mi" id="mwB0I">7</span><span class="o" id="mwB0M">..</span><span class="p" id="mwB0Q">]</span><span class="w" id="mwB0U"> </span><span class="o" id="mwB0Y">.</span><span class="w" id="mwB0c"> </span><span class="n" id="mwB0g">_U</span><span class="w" id="mwB0k"> </span> <span class="w" id="mwB0o"> </span><span class="o" id="mwB0s">.</span><span class="w" id="mwB0w"> </span><span class="n" id="mwB00">map</span><span class="w" id="mwB04"> </span><span class="p" id="mwB08">(</span><span class="nf" id="mwB1A">\</span><span class="n" id="mwB1E">p</span><span class="w" id="mwB1I"> </span><span class="ow" id="mwB1M">-></span><span class="w" id="mwB1Q"> </span><span class="p" id="mwB1U">[</span><span class="n" id="mwB1Y">p</span><span class="o" id="mwB1c">*</span><span class="n" id="mwB1g">p</span><span class="p" id="mwB1k">,</span><span class="w" id="mwB1o"> </span><span class="n" id="mwB1s">p</span><span class="o" id="mwB1w">*</span><span class="n" id="mwB10">p</span><span class="o" id="mwB14">+</span><span class="mi" id="mwB18">2</span><span class="o" id="mwB2A">*</span><span class="n" id="mwB2E">p</span><span class="o" id="mwB2I">..</span><span class="p" id="mwB2M">]))</span> <span class="w" id="mwB2Q"> </span><span class="kr" id="mwB2U">where</span> <span class="w" id="mwB2Y"> </span><span class="c1" id="mwB2c">-- non-sharing Y combinator:</span> <span class="w" id="mwB2g"> </span><span class="n" id="mwB2k">_Y</span><span class="w" id="mwB2o"> </span><span class="n" id="mwB2s">g</span><span class="w" id="mwB2w"> </span><span class="ow" id="mwB20">=</span><span class="w" id="mwB24"> </span><span class="n" id="mwB28">g</span><span class="w" id="mwB3A"> </span><span class="p" id="mwB3E">(</span><span class="n" id="mwB3I">_Y</span><span class="w" id="mwB3M"> </span><span class="n" id="mwB3Q">g</span><span class="p" id="mwB3U">)</span><span class="w" id="mwB3Y"> </span><span class="c1" id="mwB3c">-- (g (g (g (g (...)))))</span> <span class="w" id="mwB3g"> </span><span class="c1" id="mwB3k">-- big union ~= nub.sort.concat</span> <span class="w" id="mwB3o"> </span><span class="n" id="mwB3s">_U</span><span class="w" id="mwB3w"> </span><span class="p" id="mwB30">((</span><span class="n" id="mwB34">x</span><span class="kt" id="mwB38">:</span><span class="n" id="mwB4A">xs</span><span class="p" id="mwB4E">)</span><span class="kt" id="mwB4I">:</span><span class="n" id="mwB4M">t</span><span class="p" id="mwB4Q">)</span><span class="w" id="mwB4U"> </span><span class="ow" id="mwB4Y">=</span><span class="w" id="mwB4c"> </span><span class="n" id="mwB4g">x</span><span class="w" id="mwB4k"> </span><span class="kt" id="mwB4o">:</span><span class="w" id="mwB4s"> </span><span class="p" id="mwB4w">(</span><span class="n" id="mwB40">union</span><span class="w" id="mwB44"> </span><span class="n" id="mwB48">xs</span><span class="w" id="mwB5A"> </span><span class="o" id="mwB5E">.</span><span class="w" id="mwB5I"> </span><span class="n" id="mwB5M">_U</span><span class="w" id="mwB5Q"> </span><span class="o" id="mwB5U">.</span><span class="w" id="mwB5Y"> </span><span class="n" id="mwB5c">pairwise</span><span class="w" id="mwB5g"> </span><span class="n" id="mwB5k">union</span><span class="p" id="mwB5o">)</span><span class="w" id="mwB5s"> </span><span class="n" id="mwB5w">t</span>

Working on arrays by segments between consecutive squares of primes, it is:

<span id="mwB6A"></span><span class="kr" id="mwB6E">import</span><span class="w" id="mwB6I"> </span><span class="nn" id="mwB6M">Data.Array</span> <span class="kr" id="mwB6Q">import</span><span class="w" id="mwB6U"> </span><span class="nn" id="mwB6Y">Data.List</span><span class="w" id="mwB6c"> </span><span class="p" id="mwB6g">(</span><span class="nf" id="mwB6k">tails</span><span class="p" id="mwB6o">,</span><span class="w" id="mwB6s"> </span><span class="nf" id="mwB6w">inits</span><span class="p" id="mwB60">)</span> <span class="nf" id="mwB64">primes</span><span class="w" id="mwB68"> </span><span class="ow" id="mwB7A">=</span><span class="w" id="mwB7E"> </span><span class="mi" id="mwB7I">2</span><span class="w" id="mwB7M"> </span><span class="kt" id="mwB7Q">:</span><span class="w" id="mwB7U"> </span><span class="p" id="mwB7Y">[</span><span class="w" id="mwB7c"> </span><span class="n" id="mwB7g">n</span><span class="w" id="mwB7k"> </span><span class="o" id="mwB7o">|</span> <span class="w" id="mwB7s"> </span><span class="p" id="mwB7w">(</span><span class="n" id="mwB70">r</span><span class="kt" id="mwB74">:</span><span class="n" id="mwB78">q</span><span class="kt" id="mwB8A">:</span><span class="kr" id="mwB8E">_</span><span class="p" id="mwB8I">,</span><span class="w" id="mwB8M"> </span><span class="n" id="mwB8Q">px</span><span class="p" id="mwB8U">)</span><span class="w" id="mwB8Y"> </span><span class="ow" id="mwB8c"><-</span><span class="w" id="mwB8g"> </span><span class="n" id="mwB8k">zip</span><span class="w" id="mwB8o"> </span><span class="p" id="mwB8s">(</span><span class="n" id="mwB8w">tails</span><span class="w" id="mwB80"> </span><span class="p" id="mwB84">(</span><span class="mi" id="mwB88">2</span><span class="w" id="mwB9A"> </span><span class="kt" id="mwB9E">:</span><span class="w" id="mwB9I"> </span><span class="p" id="mwB9M">[</span><span class="n" id="mwB9Q">p</span><span class="o" id="mwB9U">*</span><span class="n" id="mwB9Y">p</span><span class="w" id="mwB9c"> </span><span class="o" id="mwB9g">|</span><span class="w" id="mwB9k"> </span><span class="n" id="mwB9o">p</span><span class="w" id="mwB9s"> </span><span class="ow" id="mwB9w"><-</span><span class="w" id="mwB90"> </span><span class="n" id="mwB94">primes</span><span class="p" id="mwB98">]))</span> <span class="w" id="mwB-A"> </span><span class="p" id="mwB-E">(</span><span class="n" id="mwB-I">inits</span><span class="w" id="mwB-M"> </span><span class="n" id="mwB-Q">primes</span><span class="p" id="mwB-U">),</span> <span class="w" id="mwB-Y"> </span><span class="p" id="mwB-c">(</span><span class="n" id="mwB-g">n</span><span class="p" id="mwB-k">,</span><span class="w" id="mwB-o"> </span><span class="kt" id="mwB-s">True</span><span class="p" id="mwB-w">)</span><span class="w" id="mwB-0"> </span><span class="ow" id="mwB-4"><-</span><span class="w" id="mwB-8"> </span><span class="n" id="mwB_A">assocs</span><span class="w" id="mwB_E"> </span><span class="p" id="mwB_I">(</span><span class="w" id="mwB_M"> </span><span class="n" id="mwB_Q">accumArray</span><span class="w" id="mwB_U"> </span><span class="p" id="mwB_Y">(</span><span class="nf" id="mwB_c">\</span><span class="kr" id="mwB_g">_</span><span class="w" id="mwB_k"> </span><span class="kr" id="mwB_o">_</span><span class="w" id="mwB_s"> </span><span class="ow" id="mwB_w">-></span><span class="w" id="mwB_0"> </span><span class="kt" id="mwB_4">False</span><span class="p" id="mwB_8">)</span><span class="w" id="mwCAA"> </span><span class="kt" id="mwCAE">True</span> <span class="w" id="mwCAI"> </span><span class="p" id="mwCAM">(</span><span class="n" id="mwCAQ">r</span><span class="o" id="mwCAU">+</span><span class="mi" id="mwCAY">1</span><span class="p" id="mwCAc">,</span><span class="n" id="mwCAg">q</span><span class="o" id="mwCAk">-</span><span class="mi" id="mwCAo">1</span><span class="p" id="mwCAs">)</span> <span class="w" id="mwCAw"> </span><span class="p" id="mwCA0">[</span><span class="w" id="mwCA4"> </span><span class="p" id="mwCA8">(</span><span class="n" id="mwCBA">m</span><span class="p" id="mwCBE">,</span><span class="nb" id="mwCBI">()</span><span class="p" id="mwCBM">)</span><span class="w" id="mwCBQ"> </span><span class="o" id="mwCBU">|</span><span class="w" id="mwCBY"> </span><span class="n" id="mwCBc">p</span><span class="w" id="mwCBg"> </span><span class="ow" id="mwCBk"><-</span><span class="w" id="mwCBo"> </span><span class="n" id="mwCBs">px</span> <span class="w" id="mwCBw"> </span><span class="p" id="mwCB0">,</span><span class="w" id="mwCB4"> </span><span class="n" id="mwCB8">s</span><span class="w" id="mwCCA"> </span><span class="ow" id="mwCCE"><-</span><span class="w" id="mwCCI"> </span><span class="p" id="mwCCM">[</span><span class="w" id="mwCCQ"> </span><span class="n" id="mwCCU">div</span><span class="w" id="mwCCY"> </span><span class="p" id="mwCCc">(</span><span class="n" id="mwCCg">r</span><span class="o" id="mwCCk">+</span><span class="n" id="mwCCo">p</span><span class="p" id="mwCCs">)</span><span class="w" id="mwCCw"> </span><span class="n" id="mwCC0">p</span><span class="w" id="mwCC4"> </span><span class="o" id="mwCC8">*</span><span class="w" id="mwCDA"> </span><span class="n" id="mwCDE">p</span><span class="p" id="mwCDI">]</span> <span class="w" id="mwCDM"> </span><span class="p" id="mwCDQ">,</span><span class="w" id="mwCDU"> </span><span class="n" id="mwCDY">m</span><span class="w" id="mwCDc"> </span><span class="ow" id="mwCDg"><-</span><span class="w" id="mwCDk"> </span><span class="p" id="mwCDo">[</span><span class="n" id="mwCDs">s</span><span class="p" id="mwCDw">,</span><span class="n" id="mwCD0">s</span><span class="o" id="mwCD4">+</span><span class="n" id="mwCD8">p</span><span class="o" id="mwCEA">..</span><span class="n" id="mwCEE">q</span><span class="o" id="mwCEI">-</span><span class="mi" id="mwCEM">1</span><span class="p" id="mwCEQ">]</span><span class="w" id="mwCEU"> </span><span class="p" id="mwCEY">]</span><span class="w" id="mwCEc"> </span><span class="p" id="mwCEg">)</span><span class="w" id="mwCEk"> </span><span class="p" id="mwCEo">]</span>

The shortest possible code is probably nubBy (((>1) .) . gcd) [2..]. It is quite slow.