Copyright (C) 2017, 2018, H. Conrad Cunningham

Acknowledgements: I created these slides in Fall 2018 to accompany Chapter 4, First Haskell Programs, of the book Exploring Languages with Interpreters and Functional Programming.

Browser Advisory: The HTML version of this document may require use of a browser that supports the display of MathML. A good choice as of August 2018 is a recent version of Firefox from Mozilla.

Lecture Goals

• Examine syntax and semantics of Haskell functions using factorial examples

• Explore how to execute functions using Haskell REPL ghci

Mathematical Definitions

1. Factorial using product operator:

   • fact$(n) = \prod_{i=1}^{i=n}\,i$
     • fact$(4) = 1 \times 2 \times 3 \times 4$
     • fact$(0) = 1$ – identity element for multiplication

2. Factorial using recursive definition (or recurrence relation):

   • fact’$(n) = 1$, if $n = 0$
     fact’$(n) = n \times$ fact’$(n-1)$, if $n \geq 1$
     • base case: $n = 0$
     • recursive: fact$(n)$ defined in terms of fact’$(n-1)$
     • terminates, gets closer to 0 on each step

Factorial Using if-then-else (1)

    fact1 :: Int -> Int 
    fact1 n = if n == 0 then 
                  1 
              else 
                  n * fact1 (n-1) 

• First line type signature of form object :: type.

• Type name begins with uppercase letter

• Type fact1 is function (->)

  • takes one bounded integer (Int) argument, returns integer

• No builtin natural number type

Factorial Using if-then-else (2)

    fact1 :: Int -> Int 
    fact1 n = if n == 0 then 
                  1 
              else 
                  n * fact1 (n-1) 

• Second line defining equation fname parms = body

  • fname function’s name – begins lowercase, followed alphanumerics, underscore, prime (')
  • parms function’s formal parameters – zero or more, no comma or parentheses
  • body expression defining function result
  • actual argument values substituted for parameter name in body

Factorial Using if-then-else (3)

    fact1 :: Int -> Int 
    fact1 n = if n == 0 then 
                  1 
              else 
                  n * fact1 (n-1) 

• Body expression if condition then expression1 else expression2

  • condition Boolean (Bool) value, either True or False
  • expression1 value returned when True
  • expression2 value returned when False

• Indentation is significant, indicates nesting

Factorial Using if-then-else (4)

    fact1 :: Int -> Int 
    fact1 n = if n == 0 then 
                  1 
              else 
                  n * fact1 (n-1) 

• then clause base case n == 0

• else clause recursive case

  • apply fact1 to entire expression (n-1) – parenthesis
  • terminates because argument gets closer to 0

• Difference with mathematical definition?

Function Application

• Function application by listing argument expressions after function name

  • apply function f to argument expressions x and y
  • write in prefix form f x y

• Conventional infix form for convenience (syntactic sugar)

  • prefix add x y written x + y

• Function application higher precedence than others

  • f x + y same as (f x) + y

Factorial Using Guards

    fact2 :: Int -> Int 
    fact2 n 
        | n == 0    = 1 
        | otherwise = n * fact2 (n-1)

• | denotes guarded equation

  • expression evaluated only if guard True
  • guards evaluated top to bottom

• Function fact2 equivalent to fact1

Factorial Using Pattern Matching

    fact3 :: Int -> Int 
    fact3 0 = 1 
    fact3 n = n * fact3 (n-1)

• Two equations, each with a different pattern in parameter list

  • pattern 0 in first leg matches value 0
  • pattern n in second matches anything
  • patterns evaluated top-to-bottom

• Functions fact1, fact2, and fact3 equivalent

Factorial Using Partial Function (1)

    fact4 :: Int -> Int 
    fact4 n 
        | n == 0 =  1 
        | n >= 1 =  n * fact4 (n-1)

• To stop “infinite loop”, remove negative integers from domain

• Function fact4 undefined for negatives – fails quickly

Factorial Using Partial Function (2)

    fact4' :: Int -> Int 
    fact4' n 
        | n == 0    =  1 
        | n >= 1    =  n * fact4' (n-1)
        | otherwise = error "fact4' called with negative argument"

• Function fact4'

  • displays custom error message
  • shows stack trace of active function calls

Factorial Using Library Function

    fact5 :: Int -> Int
    fact5 n = product [1..n]

• [1..n] generates list of integers from 1 to n, inclusive

• Library function product multiplies elements of list

• What if apply fact5 to negative?

  • [1..0] generates empty list
  • product of empty list is 1 – identity for multiplication
  • fact5 (-1) yields 1

Implementation Comparison

• Which function is better?

Source Code

• Haskell factorial functions Factorial.hs

• Haskell test script TestFactorial.hs

  Discussed in Chapter 12 on software testing

Using GHCi for Factorials (1)

See the Glasgow Haskell Compiler Users Guide

1. Start REPL

       bash-3.2$ ghci
       GHCi, version 8.4.3: http://www.haskell.org/ghc/  :? for help

2. Load module Factorial holding factorial function definitions – assumes file Factorial.hs in current directory – load command abbreviated :l

       Prelude> :load Factorial
       [1 of 1] Compiling Factorial        ( Factorial.hs, interpreted )
       Ok, one module loaded.

Using GHCi for Factorials (2)

3. Inquire about type of fact1

       *Factorial> :type fact1
       fact1 :: Int -> Int

4. Apply function fact1 to 7, 0, 20, 1 – note 21 exceeds Int range

       *Factorial> fact1 7
       5040
       *Factorial> fact1 0
       1
       *Factorial> fact1 20
       2432902008176640000
       *Factorial> fact1 21
       -4249290049419214848

Using GHCi for Factorials (3)

5. Apply functions fact2, fact3, fact4, fact5 to 7

       *Factorial> fact2 7
       5040
       *Factorial> fact3 7
       5040
       *Factorial> fact4 7
       5040
       *Factorial> fact5 7 
       5040 

6. Apply functions fact1, fact2, fact3 to -1 – infinite recursion – eventually runtime stack overflow

       *Factorial> fact1 (-1)
       *** Exception: stack overflow
       *Factorial> fact2 (-1)
       *Factorial> fact3 (-1)
       *** Exception: stack overflow

Using GHCi for Factorials (4)

7. Apply functions fact4, fact4' to -1 – quickly return with error

       *Factorial> fact4 (-1)
       *** Exception: Factorial.hs:(54,1)-(56,29):
         Non-exhaustive patterns in function fact4
       *Factorial> fact4' (-1)
       *** Exception: fact4' called with negative argument
       CallStack (from HasCallStack):
         error, called at Factorial.hs:64:17 in main:Factorial

8. Apply function fact5 to -1 – returns 1 because defined for negative integers

       *Factorial> fact5 (-1)
       1

Using GHCi for Factorials (5)

9. Set +s option to get information about time and space required – +t option to get type of the returned value

       *Factorial> :set +s
       *Factorial> fact1 20
       2432902008176640000
       (0.00 secs, 80,712 bytes)
       *Factorial> :set +t
       *Factorial> fact1 20
       2432902008176640000
       it :: Int
       (0.05 secs, 80,792 bytes)
       *Factorial> :unset +s +t
       *Factorial> fact1 20
       2432902008176640000

Using GHCi for Factorials (6)

10. Exit GHCi

        :quit
        Leaving GHCi.

• To edit source from within GHCi (using e.g. Aquamacs)

  • set shell environment variable EDITOR
export EDITOR=Aquamacs
  • or use GHCi :set editor Aquamacs
  • then GHCi :edit command invokes editor

Key Ideas

• Haskell has a syntax and semantics similar to mathematical notation

• GHCI REPL enables interactive execution and exploration of Haskell functions

Source Code

• Haskell factorial functions Factorial.hs

• Haskell test script TestFactorial.hs

  Discussed in Chapter 12 on software testing