Functional Programming and Intelligent Algorithms

Tutorial 1.3bis: More on Lists and Tuples

(Last update: 12 January 2015)

Menu

Overview

This is an optional tutorial, building on Tutorial 3.

Problem 3: Positioned Pictures (Optional)

See Thompson Chapter 6.6

Problem 4: Credit card numbers (optional)

This exercise is based on a an exercise given by Richard Eisenberg for the cis194 module at University of Pennsylvania. He in turn adapted it from a practicum assigned at the University of Utrecht functional programming course taught by Doaitse Swierstra, 2008-2009.

Working with long numbers, such as national insurance numbers, account numbers, ISBN numbers or credit card numbers, it is easy to make mistakes. Therefore such numbers are designed using an error correcting codes. The most probable mistakes lead to an invalid number, so that it is easily seen that an error has occurred.

In this exercise, we shall explore credit card numbers and write a functional program to validate such numbers. The validation comprises the following steps:

  1. Double the value of every second digit beginning from the right. That is, the last digit is unchanged; the second-to-last digit is doubled; the third-to-last digit is unchanged; and so on. For example, [1,3,8,6] becomes [2,3,16,6].
  2. Calculate the digit sum of each number in the list. For the one-digit numbers, this is just the number itself. For two-digit numbers, it is the sum of the two digits. For example, [2,3,16,6] becomes [2,3,7,6].
  3. Add all the digit sums together. For example, [2,3,7,6] becomes 18.
  4. Calculate the remainder when the sum is divided by 10. For example, 18 becomes 8.
  5. If the result equals 0, then the number is valid. In the running example, we got 8, which means the number is invalid.

We will implement the validation through a series of small exercises.

Exercise 1

We first need to be able to split a number into its last digit and the rest of the number. Write these functions:

lastDigit :: Integer -> Integer dropLastDigit :: Integer -> Integer

Haskell has built-in functions or operators for integer division and remainder (modulo).

Examples:

lastDigit 123 == 3 lastDigit 9 == 9 dropLastDigit 123 == 12 dropLastDigit 9 == 0

Task: Implement and test the two functions described above.

Exercise 2

Now, we male a function to break a number into a list of digits. The method is the standard approach to writing a number to base b (with b=10 in our case). You will need the functions from the previous exercise and apply them with recursion. The function should have the following signature,

toDigits :: Integer -> [Integer]

Positive numbers must be converted to a list of digits. For 0 or negative inputs, toDigits should return the empty list.

Examples:

toDigits 1234 == [1,2,3,4] toDigits 0 == [] toDigits (-17) == []

Task: Implement and test the toDigits function.

Exercise 3

Once we have the digits in a list, we need to double every other one. Define a function doubleEveryOther :: [Integer] -> [Integer]

Remember that doubleEveryOther doubles every other number starting from the right, i.e. the second-to-last, fourth-to-last, and so on. This is easiest to do if the the list is put reverse order, so that one can count from the left instead. Check out the builtin reverse function.

Examples:

doubleEveryOther [8,7,6,5] == [16,7,12,5] doubleEveryOther [1,2,3] == [1,4,3]

Task: Implement and test the doubleEveryOther function.

Exercise 4

We need to write a function to calculate the digit sum of an arbitrary integer. The digit sum is the sum of the digits, e.g. 7, 16, 25, and 34 each have 7 as the digit sum. Thus we are looking for a function with the following signature:

sumDigits :: Integer -> Integer

You probably want to use toDigits as an auxiliary.

Task: Implement and test the digitSum function.

Exercise 5

The output of doubleEveryOther has a mix of one-digit and two-digit numbers. Define the function sumDigits :: [Integer] -> Integer to calculate the sum of all digits.

Examples:

sumDigits [16,7,12,5] = 1 + 6 + 7 + 1 + 2 + 5 = 22

The digitSum can be used as an auxiliary here.

Task: Implement and test the sumDigits function.

Exercise 6

Define the function validate :: Integer -> Bool that indicates whether an Integer could be a valid credit card number. This will use all functions defined in the previous exercises.

Examples:

validate 4012888888881881 = True validate 4012888888881882 = False Task: Implement and test the validate function.