[Haskell-cafe] Re: Function to detect duplicates

[Ketil Malde]

| 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