Sorting in Haskell

Haskell’s Data.List module provides sorting functionality for lists. We’ll look at sorting for built-in types first.

import Data.List (sort)

main :: IO ()
main = do
    -- Sorting functions work for any Ord type.
    -- For a list of Ord types, see the Haskell documentation.
    let strs = ["c", "a", "b"]
    putStrLn $ "Strings: " ++ show (sort strs)

    -- An example of sorting Ints.
    let ints = [7, 2, 4]
    putStrLn $ "Ints:    " ++ show (sort ints)

    -- We can also check if a list is already in sorted order.
    let s = isSorted ints
    putStrLn $ "Sorted:  " ++ show s

-- Helper function to check if a list is sorted
isSorted :: Ord a => [a] -> Bool
isSorted [] = True
isSorted [_] = True
isSorted (x:y:xs) = x <= y && isSorted (y:xs)

When you run this program, you’ll see:

$ runhaskell sorting.hs
Strings: ["a","b","c"]
Ints:    [2,4,7]
Sorted:  True

In this Haskell version:

1. We use the sort function from Data.List to sort lists of any Ord type.

2. The sort function works on lists of any type that implements the Ord typeclass, which includes strings and integers.

3. We’ve implemented a custom isSorted function to check if a list is already sorted, as Haskell’s standard library doesn’t provide this functionality out of the box.

4. Haskell’s type system ensures that we can only sort lists of comparable types, similar to Go’s generic constraints.

5. The output is formatted similarly to the original example, showing the sorted lists and whether the final list is sorted.

This example demonstrates Haskell’s powerful type system and its built-in support for working with lists. The sort function is polymorphic, working on any list of Ord elements, which is similar to Go’s generic sorting functions.