Coin Change Problem

Famously (or at least famously in maths puzzle circles) there are 293 ways to make a US dollar using the following coins:

Penny (1 cent) | Nickel (5 cents) | Dime (10 cents) | Quarter (25 cents) | Half Dollar (50 cents) | Dollar (100 cents)

You could make a dollar with, for example, 4 quarters or 10 dimes.

How many ways are there of making a Brtish pound?

At the time of writing GB currency has the following coins

1p, 2p, 5p, 10p, 20p, 50p and £1 or 100p.

It’s usually a good idea to start problems like this by looking at simpler cases.

If we only have 1p coins, the answer is easy. There’s only 1 way to make any value: 1p = 1, 2p = 1 + 1, 3p = 1 + 1 + 1 etc

How about if we have 1p and 2p coins?

ValuePossibleWays
1p1p1
2p2 x 1p, 2p2
3p3 x 1p, 2p + 1p2
4p4 x 1p, 2p + 2p, 2p + 1p + 1p3
5p5 x 1p, 2 x 2p +1p, 2p + 3 x 1p3

Extend the table and you quickly see a pattern

ValueWays
1p1
2p2
3p2
4p3
5p3
6p4
7p4
8p5
9p5
10p6

We could write the following python code to work out the number of ways of making values with only 1 or 2p coins:

def coin12(n):
if n%2 == 0:
return int(n/2 +1)
else:
return int((n + 1)/2)

What about if we have 1p, 2p and 5p coins?

It turns out we can use our previous function to help us work this out.

For example, we could make 8p entirely of 2s and 1s. But this is just coin12(8) ways using the above function

We could make 8p using a 5p coin and 3p made of 2s and 1s: this is coin12(3) ways

This lets us write out the following table.

ValuePossibleWays
1pcoin12(1)1
2pcoin12(2)2
3pcoin12(3)2
4pcoin12(4)3
5p5p, coin12(5)4
6p5p + 1p, coin12(6)5
7p5p + coin12(2), coin12(7)6
8p5p + coin12(3), coin12(8)7
9p5p + coin12(4), coin12(9)8
10p5p + 5p, 5p + coin12(5), coin12(10)10

We can use this to help us write a new function

def coin125(n):
total =0
while n >= 5:
total += coin12(n)
n -= 5
return total + coin12(n)

When the function is tested, the results match the table above.

for i in range (1,11):
print(i ,": " ,coin125(i))

Now we can look at using the 1p, 2p, 5p and 10p coins. Our coin125 function suggests a way this can be done:

def coin12510(n):
total =0
while n >= 10:
total += coin125(n)
n -= 10
return total + coin125(n)

Similarly we could make functions for coins up to 20p, 50p and 100p

I’ve missed out some of the steps below, but working through all the coins I finished up with the following function:

 def coin125102050100(n):
total =0
while n >= 100:
total += coin125102050(n)
n -= 100
return total + coin125102050(n)
print(coin125102050100(100))

Which gave me the correct answer: 4563. In other words, there are 4,563 ways to make £1 using 1p, 2p, 5p, 10p, 20p, 50p and £1 coins.

However.

This isn’t very elegant. Looking at the code we can see we’re doing the same thing over and over again. Also, what if we had a currency that used 100 coins? Or 1000? It would take a lot of copying and pasting to work those problems out.

There has to be a better way.

Let’s look at the functions again. It’s easy to spot a pattern to them. Using pseudocode, they can be written out something like this:

define coinVALUES(n):
total =0
while n >= VALUE:
total += coinVALUES-1(n)
n -= VALUE
end while
return total + coinVALUES-1(n)
end define

Here’s a first attempt at writing the above in Python

values = [100, 50, 20, 10, 5, 2, 1]
def coin(n, val):
total = 0
while n> values[val]:
total += coin(n, val+1)
n -= values[val]
return total + coin(n, val+1)

You might notice I’ve written a recursive function, but there’s a problem. There’s no escape clause, there’s nothing to stop the function calling itself forever.

That’s quite easy to fix though

All we have to do is realise that coin1(n) = 1. If you want to make 5p using only 1p coins, there’s only one way to do it: 1p + 1p + 1p + 1p + 1p.

We can use that to add a clause to make a proper recursive function.
It also sorts out an irritating niggle: why should coin12 be different to all the other coin functions?

values = [100, 50, 20, 10, 5, 2, 1]
def coin(n, val):
if values[val] == 1:
return 1
total = 0
while n>= values[val]:
total += coin(n, val+1)
n -= values[val]
return total + coin(n, val+1)
print(coin(100,0))

This works but it’s a little bit messy. I have to call the function with an extra argument, 0, telling it to start at the beginning of the values list.

It would be better to treat coin as a “helper” function and to write another function to call it. This would make the function a lot more user friendly.

I’ve wrapped the coin function in a one called makechange. To show the flexibility of my function, I’ve used makechange to work out how many ways there are to make change from a dollar.

 values = [100, 50, 25, 10, 5, 1]

def coin(n, val):
if values[val] == 1:
return 1
total = 0
while n>= values[val]:
total += coin(n, val+1)
n -= values[val]
return total + coin(n, val+1)

def makechange(n):
return coin(n,0)

print(makechange(100))

The Best Programming Language

As Andrew Hunt and David Thomas say in the Pragmatic Programmer, there’s no such thing as the best programming language, just the best programming language for the job in hand.

However, if I had to choose the best language it would be Lisp. Here’s why:

The following code is written in Emacs Lisp. It prints out all the elements of a list

(cl-loop for element in mylist do (print element))

In the code below I’ve set mylist to equal the numbers one to five. Evaluating the loop will, unsurprisingly, print the numbers one to five.

(setq mylist '(1 2 3 4 5))
(cl-loop for element in mylist do (print element))
=> 1
2
3
4
5

You’re probably thinking you can do the same in Python or Java or whatever your preferred language is, and you’d be right.

But can your preferred language do this?

(setq mylist '(cl-loop for element in mylist do (print element)))
mylist
=> (cl-loop for element in mylist do (print element))

In the above code I’ve set mylist to be the loop itself.
That means I can set the loop code to loop across itself and print itself out one word at a time.

 (cl-loop for element in mylist do (print element))
=> cl-oop
for
element
in
... etc

In Lisp, code is data. So mylist is data; it’s a list of symbols: cl-loop for element etc. But I can also evaluate mylist in which case mylist will be a set of instructions to loop across itself and print itself out.

(eval mylist) 
=> cl-oop
for
element
in
... etc

Or to put it another way, I’ve just written a list that can read itself!

The thing that makes this possible is the fact that Lisp is a homoiconic language: programs written in such a language can be manipulated as data using the language.

Things like this give me a warm glow inside. They remind me why I love coding so much.

Writing Better Code 1

The number 28 has 6 divisors:

1,2,4,7,14,28

The number 5 only has 2 divisors:

1,5

Write a program to find all the divisors of a number.

The mod operator is useful here. Remember that the mod operator gives the remainder when two numbers are divided, so

28 % 14 = 0 
28 % 5  = 3

We can use the mod function to write code as follows

def divisors(n):
    divs = []
    for i in range(1,n+1):
    if n%i == 0:
        divs.append(i)
    return divs

print(divisors(28))

The above code is inefficient. To find the divisors of 28, you have to go through the for loop 28 times. To find the divisors of n, we have to go through the for loop n times. We say the code has time complexity O(n).

Try running the code to find the divisors of a large number such as 1347663998. You’ll notice it takes a long time to find the answer. We need a way to make the code more efficient.

You should notice that the divisors come in pairs. (1,28, 2,14 4,7). This suggests a way of saving loops. Rather than looking at all the numbers, we could look at just half of them.

import math

def divisors(n):
    divs = []
    for i in range(1,int(n/2)):
    if n%i == 0:
        divs.append(i)
        divs.append(int(n/i))
    return divs

print(divisors(28))

That seems better, but testing we get repeated divisors

[1, 28, 2, 14, 4, 7, 7, 4]

Thinking about it further we see that we only need to count as far as the square root of n (because root n * root n = n)

import math

def divisors(n):
    divs = []
    for i in range(1,int(math.sqrt(n))):
    if n%i == 0:
        divs.append(i)
        divs.append(int(n/i))
    return divs

print(divisors(28))

There’s still a problem though.

What about divisors of 9?

Run the above code with divisors(9) and you just get

[1, 9]

Isn’t 3 a divisor of 9? The problem lies in our range. We’re counting up to one less then root 9. Let’s tweak the code to take this case into account.

import math

def divisors(n):
    divs = []
    for i in range(1, int(math.sqrt(n))):
    if n%i == 0:
        divs.append(i)
        divs.append(int(n/i))
    if math.sqrt(n).is_integer():
        divs.append(int(math.sqrt(n)))
    return divs

print(divisors(9))

We’ve now got working code that runs a lot faster than the original code.

There are a couple of further tweaks we can make. 

Firstly, all numbers are divisible by 1 and themselves, so we can just append them without checking.

Odd numbers are never divisible by even numbers.  So, if n is odd, we only need to check if n is divisible by 3, 5, 7 …

If n is even we need to check all numbers from 2 onwards.

import math

def divisors(n):
divs = []
step = 1
start = 2
if n%2 == 1:
step = 2
start = 3
for i in range(start, int(math.sqrt(n)), step):
if n%i == 0:
divs.append(i)
divs.append(int(n/i))
if math.sqrt(n).is_integer():
divs.append(int(math.sqrt(n)))
divs.append(1)
divs.append(n)
return divs

One last thing. In the new code the following calculation appears three times: math.sqrt(n)

It takes the computer a lot longer to work out square roots than to do other calculations. Now, a good compiler should notice this. It will perform optimisation on your code and will store repeated calculations to stop them having to be worked out over and over again.

However, it might be more elegant to adjust your code as follows.  I’ve also added a line to sort the divisors into order.

import math

def divisors(n):
divs = []
rootn = math.sqrt(n)
step = 1
start = 2
if n%2 == 1:
step = 2
start = 3
for i in range(start, int(rootn), step):
if n%i == 0:
divs.append(i)
divs.append(int(n/i))
if rootn.is_integer():
divs.append(int(rootn))
divs.append(1)
divs.append(n)
divs.sort()
return divs

Code is Poetry

Brian Bilston has written a History of Modern Art in Poetry.  I  wondered what it would be like to do something similar in various programming languages.

Here’s the original poem:

Roses are red
Violets are blue
Sugar is sweet
And so are you

Haskell

Here’s the poem constructed using a zip statement in Haskell

Prelude> zip ["roses","violets","sugar","you"]["red","blue","sweet","sweet"]
[("roses","red"),("violets","blue"),("sugar","sweet"),("you","sweet")]

The list produced holds the relationship that sugar is sweet and you are sweet. The comparison between “you” and sugar is not made clear.

Lisp

Here’s the poem stored as an alist in Lisp

(setq poem '(("roses" . "red") ("violets" . "blue") ("sugar" . "sweet")("you" . "sweet")))
(mapcar (lambda (x) (concat (car x) " are " (cdr x))) poem)

I’ve gone one stage further here, using a mapcar function to produce something that looks a little bit more like the original poem, however we’re still missing the connection between “you” and sugar.

("roses are red" "violets are blue" "sugar are sweet" "you are sweet")

Python

Of course, sugar are sweet isn’t right.   Let’s try some Python.

poem = {"roses":"red","violets":"blue","sugar":"sweet","you":"sweet"}

for key, value in poem.items():
    if key == "sugar":
        print(key, "is" ,value)
    else:
        print(key, "are", value)

This output is at least grammatically correct.

roses are red
violets are blue
sugar is sweet
you are sweet

Java

Java can do something similar using a HashMap

Map<String, String> poem = new HashMap<String, String>();

        poem.put("roses", "red");
        poem.put("violets", "blue");
        poem.put("sugar", "sweet");
        poem.put("you", "sweet");

        for (Map.Entry<String, String> entry : poem.entrySet()) {
            if(entry.getKey().equals("sugar")){
                System.out.println(entry.getKey() + " is " + entry.getValue());
            } else{
                System.out.println(entry.getKey() + " are " + entry.getValue());
            }
            
        }

But we’re still no closer to conveying the connection between “you” being sweet, just like sugar is sweet.

Fortunately, Java allows us to use some object oriented design to better convey the meaning of the poem.

In the example below I’ve used an interface to allow sweetness to be applied to both sugar and to the special one to whom the poem refers.  The comparison is at last made clear.  As there can only be one true love, it seemed reasonable to make a singleton class for TheOne, inherited from a regular person.

Run the code and the poem is printed out properly, just like the original.  More importantly though, the concepts to which the poem refers are properly encapsulated and related.

The original poem was only 4 lines long.  My implementation takes 80 lines, but I think you’ll agree I’ve done a rather better job, providing clarity and removing any ambiguity.

public class Love {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        Flower [] rose = new Flower[12]; // 12 roses in a bunch
        Flower [] violet = new Flower[30]; // more violets in bunch
        Sugar sugar = new Sugar();
        TheOne myLove = TheOne.getInstance();  // Singleton class
        // There can only be one true love
        
        rose[0] = new Flower();
        rose[0].setColour("red");  // colour is static so only need
                                    // to instantiate one here
        
        violet[0] = new Flower();
        violet[0].setColour("blue");
        
        System.out.println("Roses are " + rose[0].getColour());
        System.out.println("Violets are " + violet[0].getColour());
        System.out.println(sugar.sweet());
        System.out.println(myLove.sweet());
    }
    
}

class Flower {
    private static String colour;
    
    public void setColour(String colour){
        this.colour = colour;
    }
    
    public String getColour (){
        return colour;
    }
}

class Sugar implements Sweetness {

    @Override
    public String sweet() {
        return "Sugar is sweet";
    }
    
}

class Person {
    public String sweet()
    {
        return "Not sweet";
    }
}

class TheOne extends Person implements Sweetness{
    private static TheOne instance = null;
    
    private TheOne()
    {
        
    }
    
    public static TheOne getInstance()
    {
        if(instance == null)
            instance = new TheOne();
        
        return instance;
    }

    @Override
    public String sweet() {
         return "And so are you";
    }
}

interface Sweetness {
    String sweet();
}

Functional Programming in Haskell for A level teachers

About this document

Functional Programming is now part of the A level curriculum. This document is intended to get those who already have some programming experience in an imperative language (such as Python or Java) up and running in Haskell, one of the functional languages recommended by AQA specification 7516.

Important!

Please note, if you have no experience of programming, then this document is not for you. Try learning an imperative language such as Python first.
This is far from being a full course in Haskell, it’s purely intended to get you through the A level syllabus. Many important features of Haskell are omitted, the most important being how Haskell handles types – you’ll need to learn about these if you want to learn Haskell properly.
A good place to start is http://learnyouahaskell.com/ by Miran Lipovaca

Getting Started

Installation

Before you start, you’ll need to install the Haskell Platform. This contains, amongst other things, the Haskell compiler GHC and the Haskell interpreter GHCi. If you install the Windows version you’ll also get WinGHCi, a simple GUI for the interpreter.
https://www.haskell.org/platform/index.html

Using the Haskell Interpreter

Once everything’s installed, open the Haskell interpreter by either running ghci in a terminal or opening WinGHCi in Windows.
The Haskell interpreter will load, showing the Prelude> prompt. Prelude refers to the standard module imported by default into all Haskell modules: it contains all the basic functions and types you need.
Try out some arithmetic operators as follows:

Prelude> 3+4
7
Prelude> (5*6)+7
37
Prelude> 2^12
4096

Saving Your Work

Haskell programs aren’t intended to be written as line after line of code, but rather as a collection of functions. Haskell programs are a little like a spreadsheet: you write lots of functions that call each other.
Here’s an example of how to save your functions and load them into the interpreter.

  1. Open your favourite text editor (Notepad, Notepad++, TextEdit, Emacs, Vim, …) and type in some Haskell functions. I’ve given two simple examples below.
areaCircle x = 3.14 * x
areaSquare x = x * x
  1. Save the file. I’ve saved my file as c:/haskell/example.hs
  2. Run the Haskell interpreter
  3. Type :l c:/haskell/example.hs to load your functions into the interpreter. You should see that the prompt now says Main>. Main refers to the module you just loaded. Note, you still have access to the Prelude functions
  4. Experiment using your functions in the Haskell interpreter. If you make changes to your functions, hit :r to reload the file.
areaCircle 3
9.42
areaSquare 4
16

Exercise

Write a functions to work out the following

  1. The perimeter of circle
  2. The perimeter of a square
  3. The perimeter of a rectangle

Lists

AQA Quick Reference

The following is taken from the AQA syllabus:
Be familiar with representing a list as a concatenation of a head and a tail. Know that the head is an element of a list and the tail is a list.
Know that a list can be empty.
Describe and apply the following operations:

  • return head of list
  • return tail of list
  • test for empty list
  • return length of list
  • construct an empty list
  • prepend an item to a list
  • append an item to a list.

Have experience writing programs for the list operations mentioned above in a functional programming language or in a language with support for the functional paradigm

Syllabus Haskell Example
Create a list let xs = [1,2,3,4,5]
return head of list head xs
return tail of list tail xs
test for empty list null xs
return length of list length xs
construct an empty list xs = []
prepend an item to a list element : xs
append an item to a list xs ++ [element]

Going beyond the specification, there are many more list examples here: https://wiki.haskell.org/How_to_work_on_lists

Using Lists

Haskell lists are homgenous: all the elements must be the same type.

  • [1,2,3] OK
  • [‘a’,’b’,’c’] OK
  • [1,’b’,2] X Not allowed

A string is simply a list of characters
“This” = [‘T’,’h’,’i’,’s’]
Haskell lists have a head and tail, they also have an init and a last (see below for examples of these). You can prepend an element to a list (add it to the front) using the : operator, and concatenate (join) two lists using the ++ operator.
Use the : operator for preference in Haskell: it’s much faster than ++
Here are some examples to illustrate the above

Prelude> let xs = [1,2,3,4,5]
Prelude> head xs
1
Prelude> tail xs
[2,3,4,5]
Prelude> init xs
[1,2,3,4]
Prelude> last xs
5
Prelude> tail xs ++ init xs
[2,3,4,5,1,2,3,4]
Prelude> head xs ++ last xs
<interactive>:15:1:
    No instance for (Num [a0]) arising from a use of ¡®it¡¯
    In a stmt of an interactive GHCi command: print it
Prelude> [head xs] ++ [last xs]
[1,5]
Prelude> xs!!2
3
Prelude> xs!!6
 *** Exception: Prelude.(!!): index too large
Prelude> xs!!0
1
Prelude> 0:xs
[0,1,2,3,4,5]
Prelude> xs ++ 6
<interactive>:25:1:
    No instance for (Num [a0]) arising from a use of ¡®it¡¯
    In a stmt of an interactive GHCi command: print it
Prelude> xs ++ [6]
[1,2,3,4,5,6]

List Exercise

  1. Write a list containing the days of the week
  2. Find the head of the list
  3. Find the tail of the list
  4. Find the last element of the list
  5. Find the last but one element of the list
  6. A new day is invented: Haskellday. Prepend this to the list

Remember that a string is a list of characters. Let name = <your name>

  1. Find the first character in your name
  2. Find the last character
  3. Find the length of your name.
  4. Find all the characters but the last.
  5. What output will the following produce?
let ls = [1,2,3,4,5]
last ls:init ls ++ tail ls ++ [head ls] ++ [ls!!3]
  • Why is [head ls] written as a list, and not as an element, eg head ls?

A Brief Diversion: List Comprehensions and Ranges

List Comprehensions aren’t mentioned on the AQA syllabus, but they’re too powerful a feature not to take a look at. It’s worth understanding how they work: similar functionality has been introduced into languages such as Java.
Let’s start with some ranges

Prelude> [1..5]
[1,2,3,4,5]
Prelude> [1,3..10]
[1,3,5,7,9]
Prelude> [10,9..1]
[10,9,8,7,6,5,4,3,2,1]
Prelude> [-5,-3..5]
[-5,-3,-1,1,3,5]

Now for some list comprehensions. The following examples show how to draw down from ranges in a list comprehension

Prelude> [x*2 | x <- [1..5]]
[2,4,6,8,10]
Prelude> [x*x | x <- [1..10]]
[1,4,9,16,25,36,49,64,81,100]

You can add predicates to restrict the values of a list comprehension as follows

Prelude> [x | x <- [1..10], odd x]
[1,3,5,7,9]

You can add more than one predicate. What are the even numbers between 1 and 50 that are divisible by 3?

Prelude> [x|x<-[1..50], x `mod` 3==0, even x]
[6,12,18,24,30,36,42,48]

You can draw down from two variables as follows. Watch out for the order! Note that x**y means x to the power of y

Prelude> [x**y | x <- [1..5], y <- [2,3,4]]
[1.0,1.0,1.0,4.0,8.0,16.0,9.0,27.0,81.0,16.0,64.0,256.0,25.0,125.0,625.0]
Prelude> [x**y | y <- [2,3,4], x <- [1..5]]
[1.0,4.0,9.0,16.0,25.0,1.0,8.0,27.0,64.0,125.0,1.0,16.0,81.0,256.0,625.0]

List Comprehension Exercise

Use list comprehensions to produce the following lists:

  1. [5,10,15,20,25,30,35,40,45,50,55,60]
  2. [0.5,0.4,0.3,0.2,0.1,0]
  3. [3,2,1,0,-1,-2,-3]
  4. [1,8,27,64,125,216,343,512,729,1000]
  5. [1,3,5,7,9]
  6. [100,102,104,106,108,110,112,114,116,118,120]

Haskell and Lazy Evaluation

Haskell doesn’t work things out until it has to – this is called lazy evaluation.
This means you can write down things that might not lead to errors in imperative languages.
For example

take 5 [1..]
[1,2,3,4,5]

The above means take the first 5 elements from the infinite list that counts up from 1. Haskell only creates as much of the list as it needs.
Combining lazy evaluation with functions that produce infinite lists means you can do such things as the following

Prelude> take 10 (cycle [1,2])
[1,2,1,2,1,2,1,2,1,2]
Prelude> take 5 (repeat "Brubeck")
["Brubeck","Brubeck","Brubeck","Brubeck","Brubeck"]

Summary

  • Haskell allows you to use list comprehensions to work out lists of numbers.
  • A list comprehension draws down from a range (e.g. x <- [1..10]) or a number of ranges.
  • You can apply predicates (e.g. odd or even) to your list comprehension to decide what goes in it.
  • List comprehensions allow you to solve problems in a completely different way to imperative programming languages. For example, here’s how you’d find all the pythagorean triples (numbers such that a2 = b2+c2) for a,b,c <x.
pythagTriples x = [(a, b, c)  | a <-[1..x], b <- [1..x], c <- [1..x], c^2 == a^2 + b^2]

More on Functions

More than one parameter

Here are the two Haskell functions used in the Getting Started section:

areaCircle x = 3.14 * x
areaSquare x = x * x

Note that Haskell functions must start with lower case letters.
Remember, whilst you are learning you can type up functions in your favourite editor and then load them into the editor using :l path/to/file. Use :r to reload the functions when you’ve made changes to them.
Here’s how to write functions with two parameters:

areaRectangle l w = l*w
perimeterRectangle l w = 2*l + 2*w

Partial Application

AQA defines partial application as the process of applying a function by creating an intermediate function by fixing some of the arguments to the function
As and example, lets consider the areaRectangle function above. Suppose you want to work out the areas of all rectangles where one side is fixed at 3. You can write a function, area3Rect, as follows

area3Rect = areaRectangle 3

You can now work out the areas of different rectangles as follows

*Main> area3Rect 4
12
*Main> area3Rect 5
15
*Main> area3Rect 6
18
*Main>

area3Rect is a partially applied function – a function where some of the parameters have been fixed.
Try creating a partially applied function based on perimeterRectangle.
This leads us nicely on to Higher Order Functions…

Higher Order Functions

AQA Quick Reference

A function is higher-order if it takes a function as an argument or returns a function as a result, or does both.
Have experience of using the following in a functional programming language:

  • map
  • filter
  • reduce or fold.

map is the name of a higher-order function that applies a given function to each element of a list, returning a list of results.
filter is the name of a higher-order function that processes a data structure, typically a list, in some order to produce a new data structure containing exactly those elements of the original data structure that match a given condition.
reduce or fold is the name of a higher-order function which reduces a list of values to a single value by repeatedly applying a combining function to the list values.

Syllabus Example
map map (+3) [1,2,3,4,5] -> [4,5,6,7,8]
filter filter (>3) [1,2,3,4,5] -> [4,5]
fold foldl (+) 0 [1..10] -> 55

Map

The Map function applies a function to every element of a list. In other words, it’s a function that takes a function as a parameter, in other words a higher order function.
Here we map the function (+3) to the list

*Main> map (+3) [1,2,3,4,5]
[4,5,6,7,8]

Here we map the odd function…

*Main> map odd [1..10]
[True,False,True,False,True,False,True,False,True,False]

Filter

The filter function filters a list according to a predicate – a function that returns true or false. Filter is therefore a higher order function, a function that takes a (predicate) function as a parameter.
Here we filter the numbers >3 from the list.

*Main> filter (>3) [1,2,3,4,5]
[4,5]

Here we filter out the odd numbers in a list.

*Main> filter (odd) [1..20]
[1,3,5,7,9,11,13,15,17,19]

A string in Haskell is treated as a list of letters. `elem` returns true if the letter is an element of the list so…

*Main> filter (`elem` ['A'..'Z']) "What Are The Capitals In This Sentence?"
"WATCITS"

Fold

A fold has three parts. A function, and accumulator and a list to work on.
Haskell gives you two types of fold, foldl which folds from the left side of a list, and foldr which folds from the right.
Fold works it way through a list one item at a time, performing an operation on that item and storing it in the accumulator.
This is probably best demonstrated with a few examples

Prelude> foldl (+) 0 [1..10]
55
Prelude> foldr (+) 0 [1..10]
55
Prelude> foldl (-) 0 [1..10]
-55
Prelude> foldr (-) 0 [1..10]
-5

The first example is quite straighforward. Foldl takes the first item from the list (1) adds it to the accumulator (0) and stores the result in the accumulator (1)
It then takes the second item from the list (2) adds it to the accumulator and stores the result (3). Working through the list you get the result 55.
The second and third examples are similar.
The last example is particularly interesting, however. Why does it give the result -5? Try and work through the logic, and remember that if you subtract a -ve number its the same as adding
You can use fold in haskell like you use loops in imperative languages

Exercises

  1. Use the map function on a list [1..5] to produce a list [2..6]
  2. Use the map function on a list [1..10] to produce a list of even numbers [2..20]
  3. Use the filter function to find the odd numbers between 1 and 30
  4. Use the filter function to find the numbers <4 in the list [1..10]
  5. Use the foldl function to add up the numbers from 1 to 100
  6. Use the foldr function to find 4! (4 x 3 x 2 x 1)

Beyond the AQA specification

The following are not part of the current specification. I’ve included in case you want to get more of a taste of Haskell…

Pattern Matching

Haskell allows pattern matching. The following function counts one, two or many objects

simpleCount 1 = "One"
simpleCount 2 = "Two"
simpleCount x = "Many"

You can use pattern matching to set base cases in recursive functions. Here’s an example of a factorial function from later on. Note how factorial 0 is defined as being 1 using pattern matching.

factorial 0 = 1
factorial n = n * factorial (n-1)

ifs and guards

Haskell allows you to use ifs and guards in your functions. A guard is a more readable version of an if.
People can learn to drive from the age of 17 in the UK. The following function uses to an if statement to check if someone is old enough to drive

canDrive x = if x <18 then  "Too young to drive" else "Old enough to drive"

Here it is using guards:

canDrive' x
          | x<18 = "Too young to drive"       |
          | otherwise = "Old enough to drive" |

The following function uses guards to work out the cost in pence of sending a large letter in the UK

letterCost weight
       | weight <= 100 = 96
       | weight <= 250 = 127
       | weight <= 500 = 171
       | otherwise = 2.46

Looking at the above letterCost function you might reasonably deduce that you could send an elephant via the UK postal service for £2.46. Unfortunately, the prices given are only for large letters which can weigh no more than 1kg.

show

What if you want to mix text and numbers when using ifs and guards?
For example, in the game of fizz, you say “Fizz” if a number is divisible by 3, otherwise you just say the number. Writing a funciton to implement this can cause a problem in Haskell, as the function will have to return text or a number. One way round this is to convert the number to text using show, as follows.

fizz n
  | n `mod` 3 == 0  = "Fizz"
  | otherwise = show n

Pattern Matching, Ifs and Guards Exercise

Write the following functions:

  1. A function that returns “Zero” if 0 is passed, then “Odd Number” or “Even Number” if an odd or even number is passed.
  2. A grade function that calculates students grade as follows: A >50, B >40, C>30 otherwise fail
  3. A fizz function, the returns “Fizz” if a number is divisible by three, otherwise it just returns the number
  4. A buzz function, the returns “Buzz” if a number is divisible by five, otherwise it just returns the number
  5. A FizzBuzz Function that returns “FizzBuzz” if a number is divisible by 3 and 5, Fizz if it’s divisible by three and Buzz if it’s divisible by five. Otherwise, just return the number.

Functions and List Comprehensions

Let’s define a function that uses a list comprehension to find the factors of n

factors n = [x | x <- [1..n], n `mod` x == 0]

Now, remembering that a number n is prime if and only if it has two factors, [1,n], let’s define function to determine if a number is prime

prime n = factors n == [1,n]
*Main> factors 15
[1,3,5,15]
*Main> factors 7
[1,7]
*Main> prime 7
True
*Main> prime 2
True

Oops, 2 is not a prime number. Use pattern matching to fix the prime function…

prime 2 = False
prime n = factors n == [1,n]

Check that…

*Main> prime 7
True
*Main> prime 2
False

Done!

Recursive Functions

Pattern matching is very useful when writing recursive functions. Recursive functions work very well on Haskell: it was designed for them. Here’s an example of a recursive function in Haskell

factorial 0 = 1
factorial n = n * factorial (n-1)

As you can see, pattern matching makes it very easy to set the base case for a recursive function. Here’s another recursive function. This one reverses a list. I’ve called my function reverse’ to distinguish it from the existing Haskell reverse function,

reverse' [] = []
reverse' (x:xs) = reverse(xs)++[x]

There are two important things to note here:
First, pattern matching is used to ensure the case of an empty list is handled.
Second, note the use of the (x:xs) pattern to identify the head and the tail of the list. Haskell programmers use this pattern a lot.

Recursion Exercise

Here some recursion problems from the Daily Java. See if you can solve them using Haskell

  1. The first 6 triangle numbers are 0, 1, 3, 6, 10, 15. The nth triangle number is 1 + 2 + 3 + … + n. Write a recursive method to find the nth triangle number
  2. Write a recursive method that returns m to the nth power, e.g. 2 to the power of 3 returns 8.
  3. The Harmonic Series begins 1 + 1/2 + 1/3 + 1/4 + 1/5 + … Write a recursive method that finds the Harmonic Series up to the nth term.
  4. The Fibonacci Series begins 1,1,2,3,5,8,13,… The next digit is the sum of the last two digits, so 1 + 1 = 2, 1 + 2 = 3 etc. Write a recursive method to print the nth fibonacci number

Lambda Functions

Lambda functions are sometimes called anonymous functions. Quite simply, they are a function without a name. It’s often more convenient to not bother naming a function when you’re only going to use it once.
Lambda is a Greek letter that looks like this: λ
Haskell uses a \ as it looks a little like a lambda.
Here’s an example of a lambda function that doubles a number

*Main> (\x -> x*2) 3
6

Here’s another lambda function that multiplies two numbers

*Main> (\x y -> x*y) 3 4
12

The above example is an anonymous version of the areaRectangle function mentioned earlier.
Here’s how to use a lambda function to find the numbers that divide by 3

*Main> filter (\x -> x `mod` 3 == 0) [1..20]
[3,6,9,12,15,18]

Putting it all together: Perfect Numbers

Here’s a Haskelly way of solving a problem, using some of the things learned so far.
A perfect number is a number that is the sum of its factors. 6 is a perfect number as its factors are 1, 2 and 3 and 1 + 2 + 3 = 6.
Find all the perfect numbers < 10000
We know from earlier that we can find the factors of a number using the following function

factors n = [x | x <- [1..n], n `mod` x == 0]

Here’s an example

*Main> factors 6
[1,2,3,6]

Remember that a number is perfect if it’s the sum of its factors, not including the number itself, so we add an extra predicate to eliminate that.

factors n = [x | x <- [1..n], n `mod` x == 0, x/=n]

Check this

*Main> factors 6
[1,2,3]

So a number is perfect if sum (factors x) == x. Lets run a list comprehension to find the perfect numbers <1000.

*Main> [x | x <- [1..1000], sum (factors x) == x]
[6,28,496]

Or use a filter…

*Main> filter (\x -> sum(factors x) == x) [1..1000]
[6,28,496]

Try running that on [1..10000] to see how long it takes Haskell to figure out the next perfect number!

Microbits. Really?

The BBC likes to think it single handedly ignited the 80’s UK programming boom thanks to its BBC B micro. Well, maybe so. If you were the sort of kid who’s parents could afford one. Most of us learned our chops on cheaper machines like Spectrums, Vic 20s and even Dragon 32s. (Remember them?) – and were grateful for the opportunity.

Well, now the BBC is back to save the world (or at least that part of it that concerned with educating British children) with the Microbit. Another spectacular example of Auntie knows best.

Now don’t get me wrong. The Microbit is a lovely piece of kit. It’s cheap, it’s flexible, it comes with a well thought out website to help program it. Boxes of the things are being sent out, free of charge, to schools up and down the country.

The thing is, I never asked for them. Are Microbits the best way to teach kids programming? I’m a teacher and I don’t remember being asked for my opinion. The trouble with this sort of thing is that they’re always proposed and built by tech-heads; by people who are very good at IT. They get it, they enjoy it. They always found it easy.

… exactly the wrong sort of person to understand what the average 12 year old non techy finds interesting or difficult. I’m not saying that you can’t motivate kids to learn computing. That’s my day job. But you don’t do it this way. I’m sure that Microbits are going to be featuring in the pages of most local newspapers over the next few months. Expect to see lots of photographs of smiling school children talking about how they’re learning to program. You can’t argue with that. Except the lessons won’t stick, there’ll be no progress for the majority and in a year’s time the Microbits will be sitting in the bin next to the video conferencing kits, the control equipment and the ghosts of the Learning Grids.

No doubt a group of manufacturers are currently sitting round, patting each other on the back as they congratulate each other on doing their bit for education. Frankly, I’d rather the money had been spent giving me a bit more preparation and marking time.

There’s a teacher shortage in this country, there are too many people saying what needs to be done and precious few actually prepared to get their hands dusty at the chalkface. You want to help, get in the classroom and get teaching. Otherwise, shut up, and stop wasting my time.

British Informatics Olympiad: Breaking Down Problems

Make sure you’ve read this post on the Olympiad Format before reading on…

Here’s an old BIO question

Goldbach Conjecture

A prime number is a whole number, greater than 1, that can only be divided by itself and the number 1.  It is known that all even numbers between 4 and 300,000,000,000,000,000 are equal to the sum of two primes (a fact that is believed to be true for all larger even numbers as well, and called the Goldbach Conjecture).

For example, 30 = 7 + 23.  There are two other ways of expressing 30 as the sum of two primes, which are 11 + 19 and 13 + 17.  These are the only ways of expressing 30 as the sum of two primes, since the order of the numbers in the additions does not matter.

1(a) [ 25 marks ]
 Write a program which inputs a single even number (between 4 and 10,000 inclusive) and outputs a single number which is the number of different ways the input can be expressed as the sum of two primes.
 Sample run
 22
 3

This problem can look quite daunting at first.  Don’t let that put you off.  All the questions in the BIO are there to test you as a programmer, there will be a way to solve them.  As a matter of fact, this is a classic programming problem, one that I included as one of my 99 Java Problems

So let’s break the problem down

The Goldbach problem consists of three separate programming problems:

  1. Testing if a number is prime
  2. Looping over the possible pairs of numbers
  3. Testing if the Goldbach Conjecture holds true for each pair of numbers in the loop

Solving the Goldbach problem requires solving these three problems

The first problem, writing a method to check if a number is prime, is a classic programming problem. Many solutions can be found online.

The second problem, thinking of all the possible pairs of numbers that need to be tested, is more interesting.  At this time it’s worth using the mathematicians trick of thinking about simple cases.   Suppose you were testing the number 10.  Which pairs of numbers add up to 10?  1+9, 2+8, 3+7, 4+ 6, 5+5.  Is that it?

What about the number 8? 12?  Does this help you to write a loop listing all the pairs of numbers adding up to 10?  Now think of the general case.
Now combine 1 & 2 to get your final solution.

Is there a more elegant way of solving the problem?  In terms of the BIO, it doesn’t matter.  As a programmer, though, you’ll always be thinking about ways to make your code more efficient.

What happens if you’ve got all the bits working but you can’t combine them?  The bad news is that you’re not going to gain very many marks.  But the good news is that you’ve had a go, and so you’re just a little bit better at coding than when you went into the exam…

British Informatics Olympiad: Format

The British Informatics Olympiad is the national computing competition for schools and colleges.

There are lots of excellent reasons for entering an Olympiad, here are three to get you going:

  • Every time you program you become a little bit better at programming
  • Solving new problems encourages new ways of thinking.
  • You may be the best in your school, you get to compete with people who may be as good as if not better than you

The following guide to answering Olympiad questions was originally put together to help my own students.  I’ve shared it here in the hope you’ll find it useful.


Olympiad Format

In the Olympiad, as with any examination, you should make sure you’ve looked at past papers and understood how you will be tested.

The first stage of the BIO is a three-hour exam, taken at school, in which students solve problems with the aid of a computer. These are marked by a teacher and submitted for moderation.

It’s important to understand just how these problems are marked.  The vast majority of marks are awarded for output from your program.  Unlike the usual sort of exams you might be familiar with, you don’t get many marks for method or elegance.  In the Olympiad, nearly all the marks are based on results.  Your teacher is given a set of test data to enter into your program, they award marks based on the program’s output.   One of the challenges is to ensure that your program considers all possible inputs.

Here’s a worked example to illustrate this, based on a past Olympiad question:

Example: Time in Words

Given a time in numbers we can convert it into words. For example:

5:00 Five o’clock
5:10 Ten minutes past five
5:15 Quarter past five
5:30 Half past five
5:45 Quarter to six
5:47 Thirteen minutes to six
Write a program which inputs two numbers (the first between 1 and 12, the second between 0 and 59 inclusive) and then prints out the time they represent, in words. You should follow the format of the examples above. Your program should then terminate.
Sample run
Hours: 4
Minutes: 12
Twelve minutes past four

First Attempt

As a first attempt, you might write a partial solution to the problem such as  the following Java example

String [] times = {"o'clock","One","two","three","four", "five", "six", "seven", "eight", "nine", "ten", "eleven", "twelve", "thirteen", "fourteen",              "quarter", "sixteen", "seventeen", "eighteen", "nineteen", "twenty", "twenty one", "twenty two", "twenty three", "twenty four", "twenty five","twenty six","twenty seven","twenty eight", "twenty nine","Half past"};
int hours = 4;
int minutes = 12;
if (minutes>30)
{
     System.out.println(times[60-minutes]+ " minutes to " + times[hours]);
}
else
{
       System.out.println(times[minutes] + " minutes past " + times[hours]);
}

Running the program with the sample data (4 hours 12 Minutes) produces the correct result.  But does it work for all cases?

Refining

You should now try the examples given at the start of the question.  If you do, you’ll notice that the program prints out such things as “Quarter minutes past five”

Clearly, you’ll need to modify the program to take these cases into account.

Once you’ve done that, you’ve solved the problem…

… or have you?  Whilst there are no “trick” questions in the BIO, you are expected to think like a programmer.  Have you considered all of the possible cases?  Are you sure that you have covered all the possible test data that will be contained in the mark scheme?

You might want to have a go at writing the program yourself.  When you’ve done so, check if your program gives the right answers when you enter the following data.  Did you consider all the possibilities?

Time in Words: Test Data

  1. 6:25
  2. 7:45
  3. 12:00 (noon)
  4. 0:00 (midnight)
  5. 12:55
  6. 0:05
  7. 0:30
  8. 0:52

If you’ve worked through the above you should have a good idea how to go about answering the Olympiad.  But what happens when you encounter a particularly difficult problem?  Follow this link to find out about breaking down problems

The Turtle System

I’ve always been a huge fan of Logo as a way of teaching programming: not just the use of turtle graphics to provide immediate visual feedback, but also the way the structure of the language naturally leads students through key programming concepts as they learn how to draw increasingly complicated shapes.

So I was rather delighted whilst at BETT to discover Peter Millican’s Turtle System. Originally written with Pascal in mind, it’s now being developed to use a simplified version of Java to produce turtle graphics and more.

The system comes as a lightweight Windows exe (which runs perfectly fine on Linux under WINE) and a simplified browser based version.

To program in Java…

  1. View|Display Power User Menu. Amongst other things, this will make the Language option appear in the menu bar
  2. Choose Language|Java. This is the preliminary version. I notice that a Python and BASIC version are still to come.
  3. Choose Help|Illustrative Java Programs to see some samples. Notice the simplified syntax in the main() method signature.

Sample Program

class drawPause
{
    void main()
    {
            colour(green);
            blot(100); //green blot
            pause(1000); //pause 1 sec
            colour(red);
            forward(450); //red line
            pause(1000);
            right(90); //90 degrees
            thickness(9); //thickness 9
            colour(blue);
            pause(1000);
            forward(300); //blue line
    }
}

 

HTML, DOT and Non Turing Complete Languages

I’ve written elsewhere about why I think students should learn textual programming.  One point worth restating is that in my experience it isn’t the syntax that causes students problems when learning to program, it’s the structures.

So why not teach students languages where the confusing structures don’t exist?  And by confusing structures, I mean loops and branches, these are confusing enough for beginners.

Let’s stop there for a moment.  The fact that you’re reading this blog means you’re probably a competent programmer.  You’re probably thinking that there’s nothing very difficult about looping and branching, these are basic concepts, and of course they are.  If you don’t understand these, you can’t program.  And that’s the point I’m trying to make.  Some students will struggle with the concept of a simple loop to print out the numbers from one to ten.  Many more students will struggle to apply that concept of a loop to problems, for example to realise that a simple password entry procedure requires a loop.

I think that it’s a good idea to avoid loops and branches when students begin coding.  Non Turing Complete Languages such as HTML and DOT give students a chance to learn syntax and to get a feel for coding environments whilst getting immediate visual feedback on what they’ve done.   I think that DOT is a great place to start, it’s a real world language with a definite use, one that can be of benefit to most users.  I’ve written more about DOT here.  Follow the link to my Dot and Graphviz Tutorial.