[Haskell-cafe] Combination-lock problem

Cale Gibbard cgibbard at gmail.com
Wed Aug 11 14:38:51 EDT 2004


Oops, just realised that I didn't include the mailing list in my
original reply to Florian -- here was my reply:
---------

Hi,

I would write it as one of the following,
----
keys [] = [[]]
keys (x:xs) = [0..x] >>= (\k -> map (k:) (keys xs))
-- or,
keys' [] = [[]]
keys' (x:xs) = do { k <- [0..x] ; map (k:) (keys' xs) }
-- or,
keys'' [] = [[]]
keys'' (x:xs) = concat [map (k:) (keys'' xs) | k <- [0..x]]
-- or,
keys''' [] = [[]]
keys''' (x:xs) = concat (map (\k -> map (k:) (keys''' xs)) [0..x])
----

Each of which does what I think you want. The first two use the fact
that lists are a monad, using bind and do notation respectively. (You
might have a look at http://www.haskell.org/hawiki/MonadsAsContainers
for more information and intuition about what's going on there.) The
third makes use of a list comprehension, and the fourth is written
using just list functions without any special syntax.

The general idea is that to construct keys (x:xs) you add each of
[0..x] to the front of each list produced by keys xs.

Which of these is most elegant is up to you :)

 - Cale


More information about the Haskell-Cafe mailing list