module Recursion where
import Question
factorialURL = "http://en.wikipedia.org/wiki/Factorial"
gcdUrl = "http://en.wikipedia.org/wiki/Gcd"
euclidUrl = "http://en.wikipedia.org/wiki/Euclidean_algorithm"
divisorUrl = "http://en.wikipedia.org/wiki/Divisor"
recursion = do
h2 <#>Recursion
-- Factorial.
<#>Implement the >factorial
function. ?> do
ul $ do
li $ p <#>Name: factorial.
li $ p <#>Arguments: n.
li $ p <#>Comment: -- Calculates the factorial of the
argument.
li $ p <#>Type signature: factorial :: Integer -> Integer
li $ do
p <#>Properties:
ul $ do
li $ fixed $ unlines
[ "prop_factorial :: Integer -> Property"
, "prop_factorial n ="
, " n >= 0 ==> factorial (n+1) `div` factorial n == n+1"
]
li $ fixed $ unlines
[ "-- n `divides` m is True iff n divides m."
, "divides :: Integer -> Integer -> Bool"
, "n `divides` m | n == 0 = error \"divides: Zero divisor.\""
, " | otherwise = m `mod` n == 0"
, ""
, "prop_factorial' :: Integer -> Property"
, "prop_factorial' n ="
, " n >= 0 ==> factorial n `divides` factorial (n+1)"
]
li $ fixed $ unlines
[ "-- Calculates the factorial of the argument."
, "factorial :: Integer -> Integer"
, "factorial n | n < 0 = error \"factorial: Negative input not allowed.\""
, "factorial 0 = 1"
, "factorial n = n * factorial (n-1)"
]
li $ do
p <#>The error function can be used to signal invalid
input. It halts the program and prints the given error message.
Try to write understandable error messages.
fixed $ unlines
[ "Main> factorial (-3)"
, ""
, "Program error: factorial: Negative input not allowed."
]
li $ p <#>By putting a function name in backquotes we can use it in an
infix style. Writing m `divides` n means
exactly the same thing as writing divides m
n. The reason for doing this is that the
expression becomes easier to read.
-- Even/odd.
<#>Write two functions. One should check whether its argument is
even, and the other whether its argument is odd. Use
recursion. ?> do
ul $ do
li $ p <#>Name: even and odd are already
defined by the Prelude. However, we can use
these names anyway if we hide the predefined functions
by writing import Prelude hiding (even, odd)
in the beginning of the file.
li $ p <#>Arguments: n.
li $ do
p <#>Comments:
ul $ do
li $ p <#>-- Checks if argument is even.
li $ p <#>-- Checks if argument is odd.
li $ do
p <#>Type signatures:
ul $ do
li $ fixed "even :: Integer -> Bool"
li $ fixed "odd :: Integer -> Bool"
li $ do
p <#>Properties:
ul $ do
li $ fixed $ unlines
[ "prop_even :: Integer -> Bool"
, "prop_even n = even (2*n) && not (even (2*n + 1))"
]
li $ fixed $ unlines
[ "prop_odd :: Integer -> Bool"
, "prop_odd n = odd (2*n + 1) && not (odd (2*n))"
]
li $ do
p <#>Three ways of solving the problem:
ul $ do
li $ fixed $ unlines
[ "-- Checks if argument is even."
, "even :: Integer -> Bool"
, "even 0 = True"
, "even n | n > 0 = not (even (n-1))"
, "even n | n < 0 = not (even (n+1))"
, ""
, "-- Checks if argument is odd."
, "odd :: Integer -> Bool"
, "odd n = not (even n)"
]
li $ fixed $ unlines
[ "-- Checks if argument is even."
, "even :: Integer -> Bool"
, "even 0 = True"
, "even 1 = False"
, "even n | n >= 2 = even (n-2)"
, "even n | n < 0 = even (-n)"
, ""
, "-- Checks if argument is odd."
, "odd :: Integer -> Bool"
, "odd n = not (even n)"
]
li $ fixed $ unlines
[ "-- Checks if argument is even."
, "even :: Integer -> Bool"
, "even 0 = True"
, "even n | n > 0 = odd (n-1)"
, "even n | n < 0 = odd (n+1)"
, ""
, "-- Checks if argument is odd."
, "odd :: Integer -> Bool"
, "odd 0 = False"
, "odd n | n > 0 = even (n-1)"
, "odd n | n < 0 = even (n+1)"
]
-- Number of divisors.
p <#>Compute the number of positive >divisors of an arbitrary positive
integer. You may want to write a helper function that takes two
integer arguments m and n:
ul $ do
li $ p <#>n: We want to know how many divisors n
has in the range 1 to m.
li $ p <#>m: The number next in turn. We should check
whether it divides n or not.
<#>If you get stuck, don't hesitate to take a peak at the
solution. ?> do
ul $ do
li $ fixed $ unlines
[ "-- n `divides` m is True iff n divides m."
, "divides :: Integer -> Integer -> Bool"
, "n `divides` m | n == 0 = error \"divides: Zero divisor.\""
, " | otherwise = m `mod` n == 0"
, ""
, "-- divisors n, for positive n, yields the number of positive divisors"
, "-- of n."
, "divisors :: Integer -> Integer"
, "divisors n | n <= 0 = error \"divisors: Negative input.\""
, " | otherwise = divisors' n"
, " where"
, " divisors' :: Integer -> Integer"
, " divisors' 1 = 1"
, " divisors' m | m `divides` n = 1 + divisors' (m - 1)"
, " | otherwise = divisors' (m - 1)"
, ""
, "-- All numbers greater than 1, also primes, have at least two divisors."
, "prop_divisors :: Integer -> Property"
, "prop_divisors n = n > 1 ==> 2 <= divs && divs <= n"
, " where divs = divisors n"
, ""
, "prop_divisors' :: Integer -> Integer -> Property"
, "prop_divisors' m n ="
, " m > 0 && n > 0 ==>"
, " divisors m <= divisors (m * n)"
]
li $ do
p <#>We use where to introduce local values and
functions. The names introduced using where are
only visible in the current function definition. We could
also have written divisors as follows (as
proposed in the hint):
fixed $ unlines
[ "-- divisors n, for positive n, yields the number of positive divisors"
, "-- of n."
, "divisors :: Integer -> Integer"
, "divisors n | n <= 0 = error \"divisors: Negative input.\""
, " | otherwise = divisors' n n"
, ""
, "-- Helper function for divisors."
, "divisors' :: Integer -> Integer -> Integer"
, "divisors' 1 n = 1"
, "divisors' m n | m `divides` n = 1 + divisors' (m - 1) n"
, " | otherwise = divisors' (m - 1) n"
]
p <#>However, this definition introduces another name into the
top-level scope, and unless we plan to use divisors'
in another context there is no point in having it as a
separate entity.
li $ do
p <#>You may want to think about why the last property above is to
be preferred over the one below. (See the next exercise for
an explanation.)
fixed $ unlines
[ "prop_divisors'' :: Integer -> Integer -> Property"
, "prop_divisors'' m n ="
, " m > 0 && n > 0 && m `divides` n ==>"
, " divisors m <= divisors n"
]
li $ p <#>Note that if we had calculated the set of all divisors,
instead of just the size of this set, then it would have
been easier to write interesting properties.
-- Gcd.
<#>Write down some properties which the >greatest common divisor (gcd) of two integers, not both
zero, should satisfy. Then implement a function which calculates
the gcd. If you get stuck, try using >Euclid's algorithm. (You may not use the function
gcd found in the Prelude.) ?> do
p <#>We cannot use the name gcd, so let's use
gcd' instead.
p <#>Some properties:
fixed $ unlines
[ "-- n `divides` m is True iff n divides m."
, "divides :: Integer -> Integer -> Bool"
, "n `divides` m | n == 0 = error \"divides: Zero divisor.\""
, " | otherwise = m `mod` n == 0"
, ""
, "-- x =^= y is True iff the absolute values of x and y are equal."
, "(=^=) :: Integer -> Integer -> Bool"
, "x =^= y = abs x == abs y"
, ""
, "prop_gcdDivisor :: Integer -> Integer -> Property"
, "prop_gcdDivisor m n ="
, " m /= 0 || n /= 0 ==> gcd' m n `divides` m"
, ""
, "prop_gcdCommutative :: Integer -> Integer -> Property"
, "prop_gcdCommutative m n ="
, " m /= 0 || n /= 0 ==> gcd' m n =^= gcd' n m"
, ""
, "prop_gcdGreatest :: Integer -> Integer -> Integer -> Property"
, "prop_gcdGreatest m n p ="
, " (m /= 0 || n /= 0) && p /= 0 &&"
, " p `divides` m && p `divides` n ==>"
, " p `divides` gcd' m n"
]
p <#>(We have not specified whether the gcd should be positive or
negative, hence the use of (=^=).)
<#>Can you find any problems with the last property? ?> do
p <#>What is the probability that the precondition is
True for randomly generated m, n
and p? We can collect test statistics using
collect:
fixed $ unlines
[ "prop_gcdGreatest' :: Integer -> Integer -> Integer -> Property"
, "prop_gcdGreatest' m n p ="
, " (m /= 0 || n /= 0) && p /= 0 &&"
, " p `divides` m && p `divides` n ==>"
, " collect p $"
, " p `divides` gcd' m n"
]
fixed $ unlines
[ "Main> quickCheck prop_gcdGreatest'"
, "OK, passed 100 tests."
, "37% -1."
, "28% 1."
, "10% -2."
, "7% 2."
, "6% 3."
, "5% 4."
, "3% -3."
, "2% 6."
, "1% 5."
, "1% -6."
]
p <#>We can see that over 60% of the ps are 1 or
-1; the precondition is almost always true for such
ps. You will learn more about how this situation
can be avoided later in the course.
fixed $ unlines
[ "-- gcd' m n computes the greatest common divisor of m and n. At most"
, "-- one of m and n may be zero."
, "gcd' :: Integer -> Integer -> Integer"
, "gcd' 0 0 = error \"The gcd of 0 and 0 is undefined.\""
, "gcd' m 0 = m"
, "gcd' m n = gcd' n (m `mod` n)"
]