[Haskellcafe] Re: Function to detect duplicates
Ketil Malde
ketil at malde.org
Fri Feb 26 10:50:42 EST 2010
 Am Freitag 26 Februar 2010 00:57:48 schrieb Rafael Gustavo da Cunha Pereira
 Pinto:

> There is a single 10 digit number that:
>
> 1) uses all ten digits [0..9], with no repetitions
> 2) the number formed by the first digit (right to left, most
> significant) is divisible by one
> 3) the number formed by the first 2 digits (again right to left) is
> divisible by two
> 4) the number formed by the first 3 digits is divisible by three
> and so on, until:
> 11) the number formed by the first 10 digits (all!) is by 10
Since Ishaaq Chandy just posted about how to generalize nested list
comprehensions, I thought this was an interesting way to approach this.
First a couple of simple helper functions:
> val = foldl (\x y > x*10+y) 0
> divides d n = n `mod` d == 0
So you could solve it using a set of list comprehensions:
> solutions = [[x1,x2,x3,x4,x5,x6,x7,x8,x9,x10]
>  x1 < [0..9]
> , x2 < [0..9], divides 2 $ val [x1,x2]
> , x3 < [0..9], divides 3 $ val [x1,x2,x3]
> , x4 < [0..9], divides 4 $ val [x1,x2,x3,x4]
> , x5 < [0..9], divides 5 $ val [x1,x2,x3,x4,x5]
> , x6 < [0..9], divides 6 $ val [x1,x2,x3,x4,x5,x6]
> , x7 < [0..9], divides 7 $ val [x1,x2,x3,x4,x5,x6,x7]
> , x8 < [0..9], divides 8 $ val [x1,x2,x3,x4,x5,x6,x7,x8]
> , x9 < [0..9], divides 9 $ val [x1,x2,x3,x4,x5,x6,x7,x8,x9]
> , x10 < [0]
> , length (nub [x1,x2,x3,x4,x5,x6,x7,x8,x9,x10]) == 10
> ]
This is a nicely declarative way to do it, and a pretty clear way to
formulate the original problem statement. But it's a bit tedious with
all the repetitions, so you would rather recurse to make it more
general. Since list comprehensions are just a different way to work in
the list monad (where  becomes 'guard'), I managed to come up with this:
> solve :: [Int] > [[Int]]
> solve prefix = do
> let l = length prefix
> if l == 10
> then return prefix
> else do
> x < [0..9]
> let r = prefix++[x]
> guard (divides (l+1) (val r) && nub r == r)
> solve r
k
(PS: I'm happy to hear any comments regarding style or other issues)

If I haven't seen further, it is by standing in the footprints of giants
More information about the HaskellCafe
mailing list