Exercise 5

For this exercise, put all of your function definitions in a file exer5.hs. You will also create a text file, exer5.txt. You must include an appropriate type declaration (::) for each function you define in your exer5.hs.

Built-In Functions

There are many useful functions that come with the language, but most of them are actually fairly simple to implement recursively. Let's prove that by doing a few.

• Write a recursive function myIterate that behaves identically to the built-in iterate.
• Write a recursive function myTakeWhile that behaves identically to the built-in takeWhile.

Pascal's Triangle

Write a recursive function pascal to generate the nth row of Pascal's triangle. Forget anything you might remember about combinatorics: we'll calculate the values in each row by recursively adding elements from the previous row.

*Main> pascal 0
[1]
*Main> pascal 1
[1,1]
*Main> pascal 2
[1,2,1]
*Main> pascal 3
[1,3,3,1]
*Main> pascal 12
[1,12,66,220,495,792,924,792,495,220,66,12,1]


Hint: given the previous row of Pascal's triangle prev, consider the result of

zip prev (tail prev)


Use the curry or uncurry functions to give a pointfree (or tacit) definition of a function addPair (i.e. do not mention any arguments: define it like addPair = …).

*Main> addPair (2,3)
5
107


Pointfree Filtering

Use partial function application to give a pointfree definition of a function withoutZeros that removes any zeros from a list of numbers.

*Main> withoutZeros [1,2,0,3,4,0,5,6,0]
[1,2,3,4,5,6]
*Main> withoutZeros [0.0, 0.1, 0.2, 0.3]
[0.1,0.2,0.3]


Hint: you'll need to get the typeclasses right for the arguments. The list must have elements that are both comparable for equality (Eq, since you want to use /= on them) and are numeric (Num, since you want to compare to zero).

Exploring Fibonacci

The Fibonacci sequence is an infinite sequence of values formed by using the identity $$F_n = F_{n-1} + F_{n-2}$$. Write a function fib that calculates the given value in the sequence using this identity. (Like with the Pascal's Triangle example: forget anything you might know about a closed-form solution to calculate these values. Implement the naïve recursive algorithm.)

*Main> fib 0
0
*Main> fib 1
1
*Main> fib 2
1
*Main> fib 3
2
*Main> fib 10
55
*Main> fib 20
6765


Also define the infinite sequence of Fibonacci numbers like this:

fibs = map fib [0..]


Fibonacci Speed

Try evaluating fib 33 with your function defined above. It should take a few seconds to evaluate, depending on your system. (If it doesn't take a noticeable amount of time, try fib 35. If you happen to be using Hugs, try starting with 25.) Try evaluating fib 45. (Control-C will stop a long calculation.)

In your exer5.txt file, answer this question: Why do you think the fib function you have defined takes so long to do seemingly simple calculations?

Something Else

Add this definition to your exer5.hs:

things :: [Integer]
things = 0 : 1 : zipWith (+) things (tail things)


Have a look at the first values of this infinite list (with take). In your exer5.txt file, answer these questions…

Describe the values in the things list. [Hint: compare with the previous questions.]

Describe how the values in things are calculated, using what you know about lazy evaluation.

Evaluate things!!33 and things!!45. Why is this calculation so much faster than calculating the values in the list fibs?

Submitting

Submit your files through CourSys for Exercise 5.

Updated Fri April 17 2020, 09:40 by ggbaker.