REVISED: Saturday, February 10, 2024
Haskell Quicksort Example.
I. HASKELL QUICKSORT
A. HASKELL QUICKSORT EXAMPLE
"Copy Paste" the following module example into your text editor and "File, Save As" Quicksort.hs to your working directory:
module Quicksort where
quicksort :: Ord a => [a] -> [a]
quicksort [] = []
quicksort (x : xs) = quicksort smaller ++ [x] ++ quicksort larger
where
smaller = [a | a <- xs, a <= x ]
larger = [b | b <- xs, b > x ]
The function quicksort is defined in terms of itself; therefore, quicksort is recursive.
The function signature shows, a is a type belonging to the Ord type class. The quicksort function takes a list of type a and returns a list of type a. For any type a of ordered values, quicksort is a function that maps between lists of such values.
In the definition of the function, the first equation shows an empty list is already sorted. The second states that any non-empty list can be sorted by inserting the first number between the two lists that result from sorting the remaining numbers that are smaller and larger than this number.
Each application of quicksort reduces the length of the argument list by one, until the list eventually becomes empty at which point the recursion stops.
Prelude> :load Quicksort
[1 of 1] Compiling Quicksort ( Quicksort.hs, interpreted )
Ok, modules loaded: Quicksort.
Prelude>
Since the function signature for Quicksort shows quicksort taking a list of type a and returning a list of type a, we call quicksort in GHCi using a list of arguments as shown below:
Prelude> quicksort [1,7,2,9,5,4,3]
[1,2,3,4,5,7,9]
it :: (Ord a, Num a) => [a]Prelude>
In quicksort, an element that you compare against is called a pivot. The quicksort function uses the head of the list as the pivot.
A sorted list is a list that has all the values smaller than or equal to the head of the list in front, and those values are sorted, then comes the head of the list in the middle, and then come all the values that are bigger than the head, they are also sorted.
A sorted list is a list that has all the values smaller than or equal to the head of the list in front, and those values are sorted, then comes the head of the list in the middle, and then come all the values that are bigger than the head, they are also sorted.
The recursive quicksort function calls are shown below:
([ ] ++ [1] ++ [7,2,9,5,4,3])
[ ] ++ [1] ++ ([2,5,4,3] ++ [7] ++ [9])
[ ] ++ [1] ++ ([ ] ++ [2] ++ [5,4,3]) ++ [7] ++ ([ ] ++ [9] ++ [ ])
[ ] ++ [1] ++ [ ] ++ [2] ++ ([4,3]++ [5] ++ [ ]) ++ [7] ++ [ ] ++ [9] ++ [ ]
[ ] ++ [1] ++ [ ] ++ [2] ++ ([3] ++ [4] ++ [ ]) ++ [5] ++ [ ] ++ [7] ++ [ ] ++ [9] ++ [ ]
[ ] ++ [1] ++ [ ] ++ [2] ++ ([ ] ++ [3] ++ [ ]) ++ [4] ++ [ ] ++ [5] ++ [ ] ++ [7] ++ [ ] ++ [9] ++ [ ]
[1, 2, 3, 4, 5, 7, 9]
The argument list has a length of seven. An argument list element that is in place and will not move anymore is represented in blue.
II. CONCLUSION
In this tutorial, we have discussed an example of Haskell quicksort.
III. REFERENCES
Bird, R. (2015). Thinking Functionally with Haskell. Cambridge, England: Cambridge University Press.
Davie, A. (1992). Introduction to Functional Programming Systems Using Haskell. Cambridge, England: Cambridge University Press.
Goerzen, J. & O'Sullivan, B. & Stewart, D. (2008). Real World Haskell. Sebastopol, CA: O'Reilly Media, Inc.
Hutton, G. (2007). Programming in Haskell. New York: Cambridge University Press.
Lipovača, M. (2011). Learn You a Haskell for Great Good!: A Beginner's Guide. San Francisco, CA: No Starch Press, Inc.
Thompson, S. (2011). The Craft of Functional Programming. Edinburgh Gate, Harlow, England: Pearson Education Limited.
