Exploring Languages with Interpreters
and Functional Programming

Chapter 4
First Haskell Programs

H. Conrad Cunningham

1 September 2018

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.

First Haskell Programs

Lecture Goals

Mathematical Definitions

  1. Factorial using product operator:

    • fact(n)=i=1i=ni(n) = \prod_{i=1}^{i=n}\,i
      • fact(4)=1×2×3×4(4) = 1 \times 2 \times 3 \times 4
      • fact(0)=1(0) = 1identity element for multiplication
  2. Factorial using recursive definition (or recurrence relation):

    • fact’(n)=1(n) = 1, if n=0n = 0
      fact’(n)=n×(n) = n \times fact’(n1)(n-1), if n1n \geq 1
      • base case: n=0n = 0
      • recursive: fact(n)(n) defined in terms of fact’(n1)(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) 

Factorial Using if-then-else (2)

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

Factorial Using if-then-else (3)

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

Factorial Using if-then-else (4)

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

Function Application

Factorial Using Guards

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

Factorial Using Pattern Matching

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

Factorial Using Partial Function (1)

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

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"

Factorial Using Library Function

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

Implementation Comparison

Source Code

Using GHCi for Factorials (1)

See the Glasgow Haskell Compiler Users Guide

  1. Start REPL

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

Using GHCi for Factorials (2)

  1. Inquire about type of fact1

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

Using GHCi for Factorials (3)

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

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

Using GHCi for Factorials (4)

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

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

Using GHCi for Factorials (5)

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

Using GHCi for Factorials (6)

  1. Exit GHCi

Key Ideas

Source Code