HASKELL CASE EXPRESSIONS

REVISED: Thursday, February 8, 2024

Haskell Case Expressions.

I.  WRITING HASKELL CASE EXPRESSIONS

A. PATTERN MATCHING

You can use pattern matching on function parameters only when you are defining functions.

Copy the following module example and paste it into your text editor:

module ListCasesPM where
import Data.List
listCasesPM          :: [a] -> String  
listCasesPM xs     = "The list is " ++ what xs  
     where what []   = "empty."  
                what [x] = "a singleton list."  
                what xs  = "a longer list."  

The example above should be saved as ListCasesPM.hs.

Load the module ListCasesPM as shown below:

Prelude> :load ListCasesPM

[1 of 1] Compiling ListCasesPM      ( ListCasesPM.hs, interpreted )

Ok, modules loaded: ListCasesPM.

Prelude>

Since the function signature for listCasesPM shows a list [a] mapped to a String, we have to use a list of arguments when we call the function in GHCi, as shown below:

Prelude> listCasesPM []
"The list is empty."

Prelude>

Prelude> listCasesPM ["Hello, World!"]

"The list is a singleton list."

Prelude>

Prelude> listCasesPM ["Hello, World!","Good-bye, World!"]

"The list is a longer list."

Prelude>

B. CASE EXPRESSIONS

Case expressions can be used anywhere.

The syntax for case expressions is as follows:

case expression of pattern -> result  
                                pattern -> result  
                                pattern -> result  
                                ...  

"Copy Paste" the following module example and into your text editor:

module ListCasesCE where
import Data.List
listCasesCE     :: [a] -> String  
listCasesCE xs = "The list is " ++ case xs of []   -> "an empty list."  
                                                                         [x] -> "a singleton list."   
                                                                         xs   -> "a longer list."  

The example above should be saved as ListCasesCE.hs to your working directory.

Open GHCi and load ListCasesCE as shown below:

Prelude> :load ListCasesCE
[1 of 1] Compiling ListCasesCE      ( ListCasesCE.hs, interpreted )
Ok, modules loaded: ListCasesCE.

Prelude>

Since the function signature for listCasesCE shows a list [a] mapped to a String, we have to use a list of arguments when we call the function in GHCi, as shown below:

Prelude> listCasesCE []
"The list is empty."

Prelude>

Prelude> listCasesCE ["Hello, World!"]

"The list is a singleton list."

Prelude>

Prelude> listCasesCE ["Hello, World!","Good-bye, World!"]

"The list is a longer list."

Prelude>

C. CONDITIONAL EXPRESSIONS

There is one use of a case expression that is so common that it has special syntax: the conditional expression.

Conditional expressions have the form:

if e1 then e2 else e3

which is really short-hand for:

case e1 of True  -> e2
                  False -> e3

A case expression must have at least one alternative and each alternative must have at least one body. Each body must have the same type, and the type of the whole expression is that type.

You can put any valid Haskell expression between the keywords case and of.

The case statement will check each alternative, in the order they are listed until it finds a pattern that matches. Once a match is found, the expression on the right hand side of the -> is evaluated. After a match is found, no further alternatives are considered.

The case statement will always evaluate exactly one alternative.

To avoid a compiler "non-exhaustive pattern" warning, you must include a pattern that matches.

To avoid a compiler "overlapping pattern" warning, do not include overlapping alternatives, for example, more than one pattern that matches.

III. CONCLUSION

The case statement will check each alternative; after a match is found, no further alternatives are considered.

IV. 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.

WRITING HASKELL FUNCTIONS

REVISED: Saturday, February 10, 2024

Writing Haskell Functions.

I.  WRITING HASKELL FUNCTIONS

Haskell is sensitive to indentation and spacing.

A. FOLLOW GOOD CODING STYLE

1. Follow the 80 column rule: a line of code must not exceed 80 columns.

2. Avoid too many parentheses by using ($) and (.) function composition.

3. Use {- for large multi-lined comments. -}

4. Use type synonyms to make code readable.

B. DEFINE THE TYPE

We will discuss a Haskell function writing process by using the process to write a function which will provide the product of the elements of a list.

products :: [Int] -> Int     -- Function signature.

The function products takes a list of integers and produces a single integer.

C. ENUMERATE THE CASES

For most types of argument, there are a number of standard cases to consider. For non-negative integers, the standard cases are 0 and n+1, for logical values they are False and True, and so on.

For lists, the standard cases are the empty list and non-empty lists.

products          [] =
products (n : ns) =

D. DEFINE THE SIMPLE CASES

By definition, the product of zero integers is one, because one is the identity for multiplication. Hence it is straightforward to define the empty list case:

products          [] = 1

products (n : ns) =

As in this example, the simple cases often become base cases for recursion.

E. DEFINE THE OTHER CASES

How can we calculate the product of a non-empty list of integers? For this step, it is useful to consider the ingredients that can be used, such as the product function itself, the n and ns arguments, and library functions of relevant types: +, -, *, and so on. In this case, we simply multiply the first integer and the product of the remaining list of integers:

products          [] = 1                           -- Base case.

products (n : ns) = n * products ns   -- Recursive case.

As in this example, the other cases often become recursive cases.

F. GENERALISE AND SIMPLIFY

Once a function has been defined using the above process, it often becomes clear that it can be generalised and simplified. For example, the function products does not depend on the precise kind of numbers to which it is applied, so its type can be generalised from integers to any numeric type:

products :: Num a => [a] -> a     -- Function signature.

In terms of simplification, we see that the pattern of recursion used in products is encapsulated by a library function called foldr.  Using folder, products can be redefined by a single equation:

products = foldr (*) 1

In conclusion, our final definition for product is as follows:

products :: Num a => [a] -> a     -- Function signature.
products = foldr (*) 1

"Copy Paste" the above products function into your text editor and "File, Save As" products.hs to your working directory.

II.  USING GHCI TO VALIDATE HASKELL FUNCTIONS

"Copy Paste" the following module example into your text editor:

module Products where
products :: Num a => [a] -> a     -- Function signature.
products = foldr (*) 1

The example above should be saved as Products.hs.

Open GHCi and load the module Products as shown below:

Prelude> :load Products
[1 of 1] Compiling Products         ( Products.hs, interpreted )
Ok, modules loaded: Products.

Prelude>

Since the function signature for Products shows a list of numbers mapped to a single number; therefore, we have to use a list of arguments when we call the function in GHCi, as shown below:

Prelude> products [1,2,3,4]

24

it :: Num a => a
Prelude>  

III. IDENTITY

True is the identity for && and.
False is the identity for || or.
1 is the identity for * multiplication.
0 is the identity for +  addition.
[] empty list is the identity for ++ append.

IV. REMOVING DUPLICATES

Prelude>  import Data.List
Prelude>

Prelude>  let f = nub [1,1,1,2,2,2,3,3,3]
f :: (Num a, Eq a) => [a]
Prelude>

Prelude>  f

[1,2,3]

it :: (Num a, Eq a) => [a]

Prelude>  

V. FACTORS

"Copy Paste" the following example into your text editor:

factors :: Int -> [Int]
factors n = [x | x <- [1..n], n `mod` x == 0]

prime :: Int -> Bool
prime n = factors n == [1,n]

primes :: Int -> [Int]
primes n = [x | x <- [2..n], prime x]

The example above should be saved as factors.hs to your working directory.

Open GHCi and load factors as shown below:

Prelude> :l factors.hs
[1 of 1] Compiling Main             ( factors.hs, interpreted )
Ok, one module loaded.
*Main> factors 15
[1,3,5,15]
*Main> prime 15
False
*Main> primes 15
[2,3,5,7,11,13]
*Main>  

VI. CONCLUSION
 

In this tutorial, you have learned a process for writing Haskell functions.

VII. 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.

HASKELL QUICKSORT EXAMPLE

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.

Open GHCi and load Quicksort as shown below:

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.

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.

HASKELL RECURSION

REVISED: Wednesday, January 24, 2024

Haskell Recursion.

I.  HASKELL RECURSION SOURCE CODE EXAMPLES

Loops:

Haskell has neither a "for loop" nor a "while loop."

When trying to understand recursion, you may find it easier to think about how the algorithm behaves for a given input. It is easy to get hung up on what the execution path looks like, so instead ask yourself questions like:

What happens if I pass an empty list?

What happens if I pass a list with one item?

What happens if I pass a list with many items?

Or, for recursion on numbers:

What happens if I pass a negative number?
What happens if I pass 0?
What happens if I pass a number greater than 0?

The structure of a recursive algorithm is often just a matter of covering the above cases.

Recursive Definitions: 

A list is either

null, written []; or cons, written :

which is constructed, and written x:xs, with head x (an element), and tail xs (a list). xs is the plural of x, and should be read that way.

A natural number is either

zero, written 0, or

successor, written n+1

with predecessor n (a natural number).

Commonly used symbols are

--     :: is read as "has type of."
--     [] is read as "empty list."
--     -> is read as an "arrow" and separates parameters.
--     : is read as "cons" and is the append-head operator.
--     | is read as "guard."

--     = is read as "is."
--     := is read as "is replaced by."

A. HASKELL RECURSION

1. Pattern Matching

Pattern matching is basically giving cases of the function. Haskell looks through the patterns and applies the first one that fits what it is trying to evaluate.

Example 1

"Copy Paste" the following Haskell squaresRec function into your text editor and "File, Save As" squaresRec.hs to your working directory:

squaresRec            :: [Double] -> [Double]   -- Type signature.
squaresRec []        = []                                  -- Base case.
squaresRec (x:xs) = x*x : squaresRec xs     -- Recursive case.

The "base case" ensures that squaresRec halts when it reaches the end of the input list.

The "recursive case" constructs a new list that is the same length as its input list, with every element in the input list substituted with its square in the output list.

Load squaresRec into GHCi:

Prelude>  :load squaresRec
[1 of 1] Compiling Main             ( squaresRec.hs, interpreted )
Ok, modules loaded: Main.
Prelude>

Call the squaresRec function as follows:

Prelude>  squaresRec [1.0,2.0,3.0]
[1.0,4.0,9.0]
it :: [Double]
Prelude>

Prelude>  :type squaresRec
squaresRec :: [Double] -> [Double]   -- squaresRec type signature.
Prelude> 

When the recursive function squaresRec is called its execution path is as follows:

squaresRec [1.0,2.0,3.0]
=
squaresRec (1.0 : (2.0 : (3.0 : [])))
=
1.0*1.0 : squaresRec (2.0 : (3.0 : []))
=
1.0*1.0 : (2.0*2.0 : squaresRec (3.0 : []))
=
1.0*1.0 : (2.0*2.0 : (3.0*3.0 : squaresRec []))
=
1.0*1.0 : (2.0*2.0 : (3.0*3.0 : []))
=
1.0 : (4.0 : (9.0 : []))
=
[1.0,4.0,9.0]

Example 2

"Copy Paste" the following Haskell oddsRec function into your text editor and "File, Save As" oddsRec.hs to your working directory:

oddsRec :: [Integer] -> [Integer]                         -- Type signature.
oddsRec []                                  = []                             -- Base case.
oddsRec (x:xs) | odd x          = x : oddsRec xs    -- Guard recursive case.
                          | otherwise = oddsRec xs          -- Guard recursive case.

The "base case "ensures that oddsRec halts when it reaches the end of the input list.

Load oddsRec into GHCi:

Prelude>  :load oddsRec
[1 of 1] Compiling Main             ( oddsRec.hs, interpreted )
Ok, modules loaded: Main.
Prelude>

Call the oddsRec function as follows:

Prelude>  oddsRec [1,2,3]
[1,3]
it :: [Integer]
Prelude>

Prelude>  :type oddsRec
oddsRec :: [Integer] -> [Integer]   -- oddsRec type signature.
Prelude>  

When the recursive function oddsRec is called its execution path is as follows:

oddsRec [1,2,3]
=
oddsRec (1 : (2 : (3 : [])))
=
1 : oddsRec (2 : (3 : []))
=
1 : oddsRec (3 : [])
=
1 : (3 : oddsRec [])
=
1 : (3 : [])
=
[1,3]

Example 3

"Copy Paste" the following Haskell enumFromToRec function into your text editor and "File, Save As" enumFromToRec.hs to your working directory:

enumFromToRec :: Int -> Int -> [Int]     -- Type signature.
enumFromToRec m n | m > n     = []         -- Guard base case.
                                    | m <= n = m : enumFromToRec (m+1) n

Load enumFromToRec into GHCi:

Prelude>  :load enumFromToRec
[1 of 1] Compiling Main             ( enumFromToRec.hs, interpreted )
Ok, modules loaded: Main.
Prelude>

Call the enumFromToRec function as follows:

Prelude>  enumFromToRec 1 3
[1,2,3]
it :: [Int]
Prelude>

Prelude>  :type enumFromToRec
enumFromToRec :: Int -> Int -> [Int]   -- enumFromToRec type signature.
Prelude>  

When the recursive function enumFromToRec is called its execution path is unfolded as follows:

               
enumFromToRec 1 3
=
1 : enumFromToRec 2 3
=
1 : (2 : enumFromToRec 3 3)
=
1 : (2 : (3 : enumFromToRec 4 3))
=
1 : (2 : (3 : []))
=
[1,2,3]

Example 4

"Copy Paste" the following Haskell factorialRec function into your text editor and "File, Save As" factorialRec.hs to your working directory:

factorialRec    :: Int -> Int                                    -- Type signature.
factorialRec n = fact 1 n
    where
    fact :: Int -> Int -> Int                                     -- Type signature.
    fact m n | m > n     = 1                                      -- Guard base case.
                   | m <= n = m * fact (m+1) n      -- Guard recursive case.

Load factorialRec into GHCi:

Prelude>  :load factorialRec
[1 of 1] Compiling Main             ( factorialRec.hs, interpreted )
Ok, modules loaded: Main.
Prelude>

Call the factorialRec function as follows:

Prelude>  factorialRec 3

6
it :: Int
Prelude>  

Prelude>  :type factorialRec

factorialRec :: Int -> Int  -- Type signature.

Prelude>

When the recursive function factorialRec is called its execution path is unfolded as follows:
             
factorialRec 3
=
fact 1 3
=
1 * fact 2 3
=
1 * (2 * fact 3 3)
=
1 * (2 * (3 * fact 4 3))
=
1 * (2 * (3 * 1))
=
6

Example 5

"Copy Paste" the following Haskell factorial function into your text editor and "File, Save As" factorial.hs to your working directory:

factorial :: Int -> Int                         -- Type signature.
factorial 0 = 1                                      -- Base case.
factorial n = n * factorial (n - 1)  -- Recursive case.

Load factorial into GHCi:

Prelude>  :load factorial
[1 of 1] Compiling Main            ( factorial.hs, interpreted )
Ok, modules loaded: Main.
Prelude>

Call the factorial function as follows:

Prelude>  factorial 3

6
it :: Int
Prelude>  

Prelude>  :type factorial

factorial :: Int -> Int  -- Type signature.

Prelude>

When the recursive function factorial is called its execution path is as follows:

factorial 3
=
3 * factorial (3 - 1)
=
3 * factorial 2
=
3 * (2 * factorial (2 - 1))
=
3 * (2 * factorial 1)
=
3 * (2 * ( 1 * factorial (1 - 1)))
=
3 * (2 * ( 1 * factorial 0))
=
3 * (2 * (1))
=
6

2. Conditionals With Binding

"Copy Paste" the following Haskell squaresCond function into your text editor and "File, Save As" squaresCond.hs to your working directory:

squaresCond :: [Integer] -> [Integer]
squaresCond ws =
    if null ws then
        []
    else
        let
            x   = head ws
            xs = tail ws
        in
            x*x : squaresCond xs

Load squaresCond into GHCi:

Prelude>  :load squaresCond
[1 of 1] Compiling Main             ( squaresCond.hs, interpreted )
Ok, modules loaded: Main.
Prelude>  

Call the squaresCond function as follows:

Prelude>  squaresCond [1,2,3]
[1,4,9]
it :: [Integer]
Prelude>  

Prelude>  :type squaresCond
squaresCond :: [Integer] -> [Integer]
Prelude>

When the recursive function squaresCond is called its execution path is as follows:

squaresCond [1,2,3]
=
squaresCond (1 : (2 : (3 : [])))
=
1*1 : squaresCond (2 : (3 : []))
=
1*1 : (2*2 : squaresCond (3 : []))
=
1*1 : (2*2 : (3*3 : squaresCond []))
=
1*1 : (2*2 : (3*3 : []))
=
1 : (4 : (9 : []))
=
[1,4,9]

B. HASKELL RECURSIVE MULTIPLICATION EXAMPLE

Mathematical induction is the basic theoretical background for recursion.

Recursion replaces loop constructs in imperative programs in a mathematically sound way.

"Copy Paste" the following module example into your text editor:

module Productx where

productx              :: Num a => [a] -> a   -- Function signature.
productx []             = 1                               -- Base case.
productx (n : ns) = n * productx ns        -- Recursive case.

The example above should be saved as Productx.hs to your working directory.

The function productx is defined in terms of itself; therefore, productx is recursive.

The function signature shows, for any type a of Num, productx is a function that maps a list of such numbers to a single such number.

In the definition of the function, the first equation states that the empty list is one, the identity for multiplication. The second equation states that the product of any non-empty list is given by multiplying the first number and the product of the remaining list of numbers.

Each application of productx reduces the length of the argument list by one, until the list eventually becomes empty at which point the recursion stops.

Open GHCi and load Productx as shown below:

Prelude> :load Productx

[1 of 1] Compiling Productx         ( Productx.hs, interpreted )

Ok, modules loaded: Productx.

Prelude>

Since the function signature for Productx shows a list of numbers mapped to  a single number, we have to use a list of arguments when we call the function in GHCi, as shown below:

Prelude> productx [1..4]

24

it :: (Num a, Enum a) => a
Prelude>

Prelude>  :type productx
productx :: Num a => [a] -> a
Prelude>  

When the recursive function productx is called its execution path is as follows:

productx [1..4]
=
productx (1 : (2 : (3 : (4 : []))))
=
1 * productx (2 : (3 : (4 : [])))
=
1 * (2 * productx (3 : (4 : [])))
=
1 * (2 * (3 * productx (4 : [])))
=
1 * (2 * (3 * (4  * productx ([])))
=
1 * (2 * (3 * (4 * (1))))
=
24

C. HASKELL RECURSIVE PERMUTATIONS EXAMPLE

A permutation of a list is a list with the same elements in a different order. The permutats function returns a list of all permutations of a list.

"Copy Paste" the following module example into your text editor:

module Permutats where

import Data.List

permutats     :: Eq a => [a] -> [[a]]                                                -- Function signature.
permutats [] = [[ ]]                                                                          -- Base case.
permutats xs = [ x:ps | x <- xs , ps <- permutats (xs\\[x]) ]        -- Recursive case.

The example above should be saved as Permutats.hs to your working directory.

The function permutats is defined in terms of itself; therefore, permutats is recursive.

Recursively [[a]] is a list of values of type [a], i.e. a list of lists of a.

The Eq class defines equality == and inequality /=.

The function signature shows, for any type a of Eq, permutats is a function that maps a list of such numbers to a list of lists of such numbers.

In the definition of the function, the first equation states that the empty list has one permutation, itself. The second equation states that if xs is not empty, a permutation is given by picking an element x from xs and putting x at the front of a permutation of the remainder xs \\ [x] . The operation '\\' returns the difference of two lists: xs \\ ys is the list xs with each element of ys removed, if it is present.

Each application of permutats reduces the length of the argument list by one, until the list eventually becomes empty at which point the recursion stops.

Open GHCi and load Permutats as shown below:

Prelude> :load Permutats

[1 of 1] Compiling Permutats        ( Permutats.hs, interpreted )

Ok, modules loaded: Permutats.

Prelude>

Since the function signature for Permutats shows a list of numbers mapped to a list of lists, we have to use a list of arguments when we call the function in GHCi, as shown below:

Prelude> permutats [1..4]

[[1,2,3,4],[1,2,4,3],[1,3,2,4],[1,3,4,2],[1,4,2,3],[1,4,3,2],[2,1,3,4],[2,1,4,3],[2,3,1,4],[2,3,4,1],[2,4,1,3],[2,4,3,1],[3,1,2,4],[3,1,4,2],[3,2,1,4],[3,2,4,1],[3,4,1,2],[3,4,2,1],[4,1,2,3],[4,1,3,2],[4,2,1,3],[4,2,3,1],[4,3,1,2],[4,3,2,1]]

it :: (Num a, Eq a, Enum a) => [[a]]
Prelude> 

Prelude>  :type permutats
permutats :: Eq a => [a] -> [[a]]
Prelude>  

D. HASKELL RECURSIVE SUMMATION EXAMPLES

Example 1

"Copy Paste" the following module example into your text editor:

module Summation where
summation             :: Num a => [a] -> a    -- Function signature.
summation []            = 0                                -- Base case.
summation (x : xs) = x + summation xs    -- Recursive case.

The example above should be saved as Summation.hs to your working directory.

The function summation is defined in terms of itself; therefore, summation is recursive.

The function signature shows, for any type a of Num, summation is a function that maps a list of such numbers to a single such number.

In the definition of the function, the first equation states that the sum of the empty list is zero, the identity for addition. The second equation states that the sum of any non-empty list comprising a first number x and a remaining list of numbers xs is given by adding x and the summation of xs.

Each application of summation reduces the length of the argument list by one, until the list eventually becomes empty at which point the recursion stops.

Open GHCi and load Summation as shown below:

Prelude> :load Summation

[1 of 1] Compiling Summation        ( Summation.hs, interpreted )

Ok, modules loaded: Summation.

Prelude>

Since the function signature for Summation shows a list of numbers mapped to  a single number, we have to use a list of arguments when we call the function in GHCi, as shown below:

Prelude> summation [1..4]
10
it :: (Num a, Enum a) => a
Prelude>  

Prelude>  :type summation
summation :: Num a => [a] -> a
Prelude>

Example 2

"Copy Paste" the following Haskell sumRec function into your text editor and "File, Save As" sumRec.hs to your working directory:

sumRec            :: [Integer] -> Integer
sumRec []          = 0
sumRec (x:xs) = x + sumRec xs

Open GHCi and load sumRec as shown below:

Prelude>  :load sumRec
[1 of 1] Compiling Main             ( sumRec.hs, interpreted )
Ok, modules loaded: Main.
Prelude> 

Call the sumRec function as follows:

Prelude>  sumRec [1,2,3]
6
it :: Integer
Prelude>  

Prelude>  :type sumRec
sumRec :: [Integer] -> Integer
Prelude>  

When the recursive function sumRec is called its execution path is as follows:

sumRec [1,2,3]
=
sumRec (1 : (2 : (3 : [])))
=
1 + sumRec (2 : (3 : []))
=
1 + (2 + sumRec (3 : []))
=
1 + (2 + (3 + sumRec []))
=
1 + (2 + (3 + 0))
=
6

Example 3

"Copy Paste" the following Haskell sumSqOddRec function into your text editor and "File, Save As" sumSqOddRec.hs to your working directory:

sumSqOddRec :: [Integer] -> Integer
sumSqOddRec []                                  = 0
sumSqOddRec (x:xs) | odd x          = x*x + sumSqOddRec xs
                                    | otherwise = sumSqOddRec xs

Open GHCi and load sumSqOddRec as shown below:

Prelude>  :load sumSqOddRec
[1 of 1] Compiling Main             ( sumSqOddRec.hs, interpreted )
Ok, modules loaded: Main.
Prelude>  

Call the sumSqOddRec function as follows:

Prelude>  sumSqOddRec [1,2,3]
10
it :: Integer
Prelude>  

Prelude>  :type sumSqOddRec
sumSqOddRec :: [Integer] -> Integer
Prelude> 

When the recursive function sumSqOddRec is called its execution path is as follows:

sumSqOddRec [1,2,3]
=
sumSqOddRec (1 : (2 : (3 : [])))
=
1*1 + sumSqOddRec (2 : (3 : []))
=
1*1 + sumSqOddRec (3 : [])
= 
1*1 + (3*3 + sumSqOddRec [])
=
1*1 + (3*3 + 0)
=
1 + (9 + 0)
=
10

II. TYING THE KNOT

Tying the knot is a solution to the problem of circular data structures. This procedure allocates only two numbers 0 and 1 in memory. We produce two open-ended objects, and then link their ends together. The procedure of doing so is called tying the knot. 

"Copy Paste" the following Haskell function into your text editor and "File, Save As" TyingTheKnot.hs to your working directory:

module TyingTheKnot where

cyclic :: [Integer]
cyclic = let x = 0 : y
                   y = 1 : x
              in  x

Load TyingTheKnot into GHCi:

Prelude>  :load TyingTheKnot
[1 of 1] Compiling TyingTheKnot     ( TyingTheKnot.hs, interpreted )
Ok, modules loaded: TyingTheKnot.
Prelude>

Call the cyclic function:

Prelude>  take 10 cyclic
[0,1,0,1,0,1,0,1,0,1]
Prelude>

When the function cyclic is called its execution path is as follows:

= x
= 0 : y
= 0 : 1 : x -- Knot! Back to the beginning.
= 0 : 1 : 0 : y
= -- etc. take had to be used when calling cyclic without take cyclic is an infinite loop.

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.

In this tutorial, you have received an introduction to Haskell recursion.