• Choose a category
• All
• Classic-Fiction

quicksort :: (Ord a) => [a] -> [a]

quicksort [] = []

quicksort (x:xs) =

let smallerOrEqual = filter (<= x) xs

larger = filter (> x) xs

in quicksort smallerOrEqual ++ [x] ++ quicksort larger

More Examples of map and filter

As another example, let’s find the largest number under 100,000 that’s divisible by 3,829. To do that, we’ll just filter a set of possibilities in which we know the solution lies:

largestDivisible :: Integer

largestDivisible = head (filter p [100000,99999..])

where p x = x `mod` 3829 == 0

First, we make a descending list of all numbers less than 100,000. Then we filter it by our predicate. Because the numbers are sorted in a descending manner, the largest number that satisfies our predicate will be the first element of the filtered list. And because we end up using only the head of the filtered list, it doesn’t matter if the filtered list is finite or infinite. Haskell’s laziness causes the evaluation to stop when the first adequate solution is found.

As our next example, we’ll find the sum of all odd squares that are smaller than 10,000. In our solution, we’ll use the takeWhile function. This function takes a predicate and a list. Starting at the beginning of the list, it returns the list’s elements as long as the predicate holds true. Once an element is found for which the predicate doesn’t hold true, the function stops and returns the resulting list. For example, to get the first word of a string, we can do the following:

ghci> takeWhile (/=' ') "elephants know how to party"

"elephants"

To find the sum of all odd squares that are less than 10,000, we begin by mapping the (^2) function over the infinite list [1..]. Then we filter this list so we get only the odd elements. Next, using takeWhile, we take elements from that list only while they are smaller than 10,000. Finally, we get the sum of that list (using the sum function). We don’t even need to define a function for this example, because we can do it all in one line in GHCi:

ghci> sum (takeWhile (<10000) (filter odd (map (^2) [1..])))

166650

Awesome! We start with some initial data (the infinite list of all natural numbers), and then we map over it, filter it, and cut it until it suits our needs. Finally, we just sum it up!

We could have also written this example using list comprehensions, like this:

ghci> sum (takeWhile (<10000) [m | m <- [n^2 | n <- [1..]], odd m])

166650

For our next problem, we’ll be dealing with Collatz sequences. A Collatz sequence (also known as a Collatz chain) is defined as follows:

Start with any natural number.

If the number is 1, stop.

If the number is even, divide it by 2.

If the number is odd, multiply it by 3 and add 1.

Repeat the algorithm with the resulting number.

In essence, this gives us a chain of numbers. Mathematicians theorize that for all starting numbers, the chain will finish at the number 1. For example, if we start with the number 13, we get this sequence: 13, 40, 20, 10, 5, 16, 8, 4, 2, 1. (13 × 3 + 1 equals 40. 40 divided by 2 equals 20, and so on.) We can see that the chain that starts with 13 has 10 terms.

Here is the problem we want to solve: For all starting numbers between 1 and 100, how many Collatz chains have a length greater than 15?

Our first step will be to write a function that produces a chain:

chain :: Integer -> [Integer]

chain 1 = [1]

chain n

| even n = n:chain (n `div` 2)

| odd n = n:chain (n*3 + 1)

This is a pretty standard recursive function. The base case is one, because all our chains will end at one. We can test the function to see if it’s working correctly:

ghci> chain 10

[10,5,16,8,4,2,1]

ghci> chain 1

[1]

ghci> chain 30

[30,15,46,23,70,35,106,53,160,80,40,20,10,5,16,8,4,2,1]

Now we can write the numLongChains function, which actually answers our question:

numLongChains :: Int

numLongChains = length (filter isLong (map chain [1..100]))

where isLong xs = length xs > 15

We map the chain function to [1..100] to get a list of chains, which are themselves represented as lists. Then we