Sorting, searching and deduplication

sort and sortBy

sort takes a list and returns it in ascending order, using the Ord instance of the element type. sortBy takes the comparison as a function of two arguments, and sortOn takes a key function and sorts by the key. All three are in Data.List, all three are stable, and all three return a new list: the input is not modified.

module Main (main) where import Data.List (nub, sort, sortBy) main :: IO () main = do print (sort [3, 1, 2] :: [Int]) print (sortBy (flip compare) [1, 3, 2] :: [Int]) print (nub [1, 2, 1, 3, 2] :: [Int]) print (elem (2 :: Int) [1, 2, 3] :: Bool) print (lookup "b" [("a", 1), ("b", 2)] :: Maybe Int) print (minimum [3, 1, 2] :: Int) print (maximum [3, 1, 2] :: Int)

ghc -Wall -O1 -o sorting sorting.hs
./sorting

[1,2,3]
[3,2,1]
[1,2,3]
True
Just 2
1
3

The second line is the descending order: flip compare is the comparison with its arguments swapped, so it is the same sortBy with the opposite answer. The fifth line shows a search that can fail: lookup returns a Maybe, so a missing key is a value and not an exception.

nub, elem and lookup

Three small search functions cover most of what a loop would do in another language, and each has a cost worth knowing:

nub [1, 2, 1, 3, 2] -- [1,2,3] nub "banana" -- "ban" elem (2 :: Int) [1, 2, 3] -- True lookup "b" [("a", 1), ("b", 2)] -- Just 2 lookup "z" [("a", 1), ("b", 2)] -- Nothing

For a large table, a list of pairs is the wrong structure and Data.Map from the containers package is the right one; the lesson on modules comes back to it. For a handful of records the list is simpler and the difference does not show, which is why the Prelude and Data.List keep these functions.

minimum and maximum

minimum and maximum return the smallest and largest element, and both are partial: on the empty list there is no answer, so both throw. When the list may be empty, the total replacement is a fold with a starting value:

minimum [3, 1, 2] -- 1 maximum [3, 1, 2] -- 3 foldr max 0 [] -- 0, an answer for the empty list foldr max 0 [3, 1, 2] -- 3

The choice of the starting value is a decision about the empty case: zero is right for a count or a sum of non-negative numbers, and wrong for a list of temperatures where the maximum of nothing should probably be a Maybe. A Maybe is the honest answer when there is no sensible default, and the lesson on Maybe comes back to it.

A table of records

A list of pairs is a table, and the search functions work on it directly. This program keeps a phone book and asks two questions of it: the number of one person, and the table sorted by number.

module Main (main) where import Data.List (sortOn) phones :: [(String, String)] phones = [("Ada", "555-0101"), ("Grace", "555-0199"), ("Alan", "555-0142")] main :: IO () main = do print (lookup "Ada" phones) print (sortOn snd phones) print (any (\(name, _) -> name == "Alan") phones)

ghc -Wall -O1 -o search search.hs
./search

Just "555-0101"
[("Ada","555-0101"),("Alan","555-0142"),("Grace","555-0199")]
True

sortOn snd sorts by the second component, which is the number, and lookup finds a record by the first. The lambda in the last line destructures each pair in the pattern, which is the pattern matching of the earlier lesson used as an argument. A real phone book would use Data.Map for the lookup, and the shape of the program would not change.

Exercises

  1. Sort ["pear", "apple", "fig"] with sort and then with sortOn length, and compare.
  2. Write myNub with foldr and elem, and check it against nub.
  3. Use lookup on a table of three pairs and print both a hit and a miss.
  4. Replace minimum with a fold that has a starting value and explain the choice of the value.
  5. Time nub on lists of 1000 and 2000 elements and say which growth the two runs show.
  6. Sort the phone book by name with sortOn fst and print it.

Questions

A new set of questions in a new order every time. Choose one answer for each, then check.

  1. What does sort [3, 1, 2] return?

    Answer

    [1,2,3]

    sort orders by the Ord instance of Int, ascending.

  2. What does sortBy (flip compare) [1, 3, 2] return?

    Answer

    [3,2,1]

    flip compare is the comparison with its arguments swapped, which reverses the order.

  3. What does nub [1, 2, 1, 3, 2] return?

    Answer

    [1,2,3]

    nub keeps the first occurrence of each value and drops the later duplicates.

  4. What is the cost of nub on a list of length n?

    Answer

    About n squared, because each element is searched in the result so far

    Each of the n elements is compared with the elements kept so far with elem, so the work adds up to about n squared.

  5. What does lookup "z" [("a", 1), ("b", 2)] return?

    Answer

    Nothing

    lookup wraps the result in Maybe, and a missing key is Nothing rather than an exception.

  6. What does this program print? module Main (main) where main :: IO () main = print (lookup "b" [("a", 1), ("b", 2)] :: Maybe Int)

    Answer

    Just 2

    The key b is found and its value 2 is wrapped in Just.

  7. What happens when minimum is called on the empty list?

    Answer

    It throws an error at run time

    minimum is partial: the empty list has no smallest element and no default, so it fails when forced.

  8. What is a total replacement for maximum []?

    Answer

    foldr max start [], with a starting value chosen for the empty case

    A fold with an explicit starting value answers for the empty list, and the value documents what the empty maximum means.

  9. What does this program print? module Main (main) where import Data.List (sortBy) main :: IO () main = print (sortBy (flip compare) [1, 3, 2] :: [Int])

    Answer

    [3,2,1]

    The flipped comparison sorts in descending order.

  10. Which function sorts by a key without writing a comparison?

    Answer

    sortOn

    sortOn takes the key function and compares the keys for you.

The code on this page was built with GHC 9.10.3 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container.

Article author: Arthur Isaev

Banner image