Introduction To Haskell
Power Sets & Practical Numbers
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 + 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.
Now, taking the first example, we''ll start with an empty list and the increase one item at a time.
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.
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.