Due Week 12
The search for numerical sequences have been part of mathematics since its inception. Sequences such as the mersenne primes and the optical golomb rulers are still of great interest today. Related to the search for numerical sequences is the ability to identify a list of numbers as a certain numerical sequence; once you've identified the type of sequence, you can then predict what the next number in the sequence should be. In this assignment, you will be writing some Haskell functions to do exactly this task: determine whether a list of numbers is indeed a numerical sequence, and also predict the next number if it is a known sequence.
The assignment is divided up into a number of tasks. Each task will be assessed separately, although they are structured so that the programming required for later tasks will be much easier if you build on the code you've written for previous tasks.
delta :: [Int] -> [Int]which calculates the differences (also called the deltas) between adjacent numbers in the list, and outputs those differences. The resulting list should have one less element than the original list (since there will be n - 1 differences in a list consisting of n numbers). If this function is given an empty list (a.k.a. the Nil list, or []), you should return an empty list.
Predict> delta [5, 9, 4, 7, 3, 6, 18, 29]
[4,-5,3,-4,3,12,11]
Predict> delta [1, 2, 4, 8, 16, 32]
[1,2,4,8,16]
Predict> delta [2, 4, 6, 8, 10, 12]
[2,2,2,2,2]
Predict> delta [4, 9]
[5]
Predict> delta [3, 3]
[0]
Predict> delta [1]
[]
Predict> delta []
[]
isAP :: [Int] -> Boolwhich, given a list of Ints, returns True if the Ints are in the form of an Arithmetic Progression (AP). Mathematically inclined people may prefer the MathWorld definition of an Arithmetic Sequence. For the purposes of this assignment, any list with a single Int in it is considered to be an Arithmetic Progression, and the Nil list (a list with no elements) is not considered to be an Arithmetic Progression.
Predict> isAP [1, 2, 3, 4, 5, 6]
True
Predict> isAP [9, 7, 5, 3, 1, -1, -3, -5]
True
Predict> isAP [4, 9, 14, 18]
False
Predict> isAP [1, 1, 1, 1]
True
Predict> isAP [10]
True
Predict> isAP []
False
isGP :: [Int] -> Boolwhich, given a list of Ints, returns True if the Ints are in the form of an Geometric Progression (GP). In simple terms, a geometric sequence is one where the next number in a the sequence is a constant multiplier of the previous number. (Note that negative multipliers are permitted!). MathWorld provides a more mathematical definition of a Geometric Sequence.
For the purposes of this assignment, any list with a single Int in it is considered to be a Geometric Progression, and the Nil list (a list with no elements) is not considered to be an Geometric Progression.
Predict> isGP [1, 2, 4, 8, 16, 32]
True
Predict> isGP [15625, 3125, 625, 125, 25, 5]
True
Predict> isGP [4, 9, 17, 44]
False
Predict> isGP [2, 3, 4, 5]
False
Predict> isGP [3, -3, 3, -3, 3, -3]
True
Predict> isGP [17]
True
Predict> isGP []
False
predict :: [Int] -> Intwhich, given a list of Int, returns an Int which is the next number in that sequence. If you can't guess what the next number in the sequence is, your function should output 0; we will never test a numeric sequence in which a predicted value of 0 is a valid answer. Sequences can be:
Predict> predict [1, 2, 3, 4]or
5
Predict> predict [5, -10, 20, -40]
80
Predict> predict [1, 2, 3, 5]
0
A GP where each element has a constant added to it:
Predict> predict [6, -9, 21, -39]
81
Note that the above sequence is the same as [5, -10, 20, -40] with +1 added to each number
Predict> predict [2, 3, 4, 6]
0
COMP3906 Advanced
smartPredict :: [Int] -> Intwhich, given a list of Int, returns an Int which is the next number in that sequence. Sequences may be one of:
A subset of the Fibonacci number sequence, possibly multiplied by a constant or +/- a constant (but not both). We are only interested in the actual fibonacci sequence, i.e. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...; we are not interested in other recurrence relations (e.g. 1, 6, 7, 13, 20).
Predict> smartPredict [5, 8, 13, 21, 34, 55, 89, 144, 233]A subset of the prime number sequence, possibly multiplied by a constant or +/- a constant (but not both):
377
Predict> smartPredict [7, 10, 15, 23, 36, 57, 91, 146, 235]
379
Predict> smartPredict [10, 16, 26, 42, 68, 110, 178, 288, 466]
754
Predict> smartPredict [11, 17, 27, 43, 69, 111, 179, 289, 467]
0
(This is the Fibonacci sequence both multiplied and added to – you are not expected to be able to predict this, although that's fantastic if you can!)
Predict> smartPredict [7, 11, 13, 17, 19, 23, 29, 31, 37]The addition of any of the previously-mentioned sequences; e.g. the Fibonacci number sequence added to a geometric progression added to an arithmetic progression:
41
Predict> smartPredict [14, 22, 26, 34, 38, 46, 58, 62, 74]
82
Predict> smartPredict [10, 14, 16, 20, 22, 26, 32, 34, 40]
44
Predict> smartPredict [8, 12, 18, 27, 41, 63, 98, 154, 244]
389
([7, 10, 15, 23, 36, 57, ...] which is the Fibonacci sequence +2 on each number, added to the arithmetic sequence [1, 2, 3, 4, 5, 6, ...])
Predict> smartPredict [20, 13, 47, -5, 119, -113, 379, -577, 1355]
-2477
([14, 22, 26, 34, 38, 46, ...] which is the prime number sequence *2 on each number, added to the geometric sequence [5, -10, 20, -40, 80, -160, ...] with each number +1)
Do the simple things first! Don't try to write the predict function first before doing the previous tasks. Even for the easier tasks, split them up into as many functions as you need, so each function has a dedicated job, but a simple one. You won't get penalised for five or ten functions per question if those functions are helpful!
Comment things as you go along, not after you've finished writing all your code. You are marked on style precisely because it's very important. Do yourself a favour and make your code neat from the beginning; it'll help you later when you're finding bugs in your code.
bigHint :: String
bigHint = "Start Early!" ++ bigHint