Introduction To Haskell
Power Sets & Practical Numbers

Introduction

The power set of a set S is a set of all of the subsets of S, including the empty set and S itself. It is quite an easy thing to express in Haskell and a function that I find myself using quite often when solving certain problems.

To find out if a number is a practical number, first work out its proper divisors. The proper divisors of a number are all of its factors except itself. The proper divisors of 6 are,

1, 2, 3

Then work out all of the possible ways that you could add these factors together. For the factors of 6, this would be,

  • 1
  • 2
  • 3
  • 1 + 2 = 3
  • 1 + 3 = 4
  • 2 + 3 = 5
  • 1 + 2 + 3 = 6

If all of the numbers up to the number can be found by adding together combinations of factors, then the number is a practical number. 6 is a practical number because the digits, 1, 2, 3, 4 and 5 appear in this list.

Take the number 5. It is a prime number, so its only proper divisor is 1. 1 is the only digit that can be made from the factors and so 5 is not a practical number.

Generating this sequence is included here because of its dependence on the power set of the factor list.

Programming - Power Set

This is the power set function.

powerset [] = [[]]
powerset (x:xs) = map (x:) (powerset xs) ++ powerset xs

The first line says that the powerset of an empty set is an empty set. Our function is meant to return a list of lists.

The second line is where the magic happens. The (x:xs) is pattern matching. Using this with a list binds x to the head of the list and xs to the tail of the list.

This is worth testing out a little to get a better understanding of how it works.

WinGHCI

Now, taking the first example, we''ll start with an empty list and the increase one item at a time.

WinGHCI

Programming - Practical Numbers

Despite the apparent complexity of the problem, it is relatively easy to break down these steps in Haskell.

powerset [] = [[]]
powerset (x:xs) = map (x:) (powerset xs) ++ powerset xs

pdivs p = [x|x<-[1..div p 2],mod p x==0]

summings p = map (sum) (powerset (pdivs p))

practical p = all (`elem` (summings p)) [1..p-1]

The pdivs function uses a list comprehension to give the proper divisors of the input. Summings takes the powerset of the proper divisors and maps the sum function to give a list of the totals that can be made of these divisors. The final function tests whether a number p is practical using the all function to see if the preceeding integers are all present in the summings list.

WinGHCI

Challenge

Although this performs quite well, it could be a little more efficient. Apart from 1 and 2, all practical numbers are divisible by either 4, 6 or both.