Generate possible combinations by range and length

Question

I am learning Haskell and I implemented a recursive function that generates possible strings by length and array (e.g. ['a'..'z']):

comb :: Int -> [a] -> [[a]]
comb 0 _ = []
comb 1 r = map (:[]) r  -- convert "abc.." to ["a","b"...]
comb n r = [i:s | i <- r, s <- comb (n-1) r]

For example, comb 2 ['a'..'z'] gives ["aa","ab","ac", ... "zx","zy","zz"]. It works with any range: comb 3 [0,1] is [[0,0,0],[0,0,1] ... [1,1,0],[1,1,1]]. Is there a way to improve it?

Answer 1

It looks very good already!

I think it is nicer to have a single base-case, which is possible if you change the comb 0 _ case:

comb :: Int -> [a] -> [[a]]
comb 0 _ = [[]]
comb n r = [i:s | i <- r, s <- comb (n-1) r]

This also kind of makes sense: every element of the resulting list has length n and there are (length r) ^ n such elements. Since (length r) ^ 0 = 1, I would expect one element of length 0 in the resulting list.

You can also use the ... <$> ... <*> ... pattern here, then you do not have to use the useless i and s names:

comb :: Int -> [a] -> [[a]]
comb 0 _ = [[]]
comb n r = (:) <$> r <*> comb (n-1) r

The following is somewhat more advanced, maybe not suitable for a beginner, so don't worry if it doesn't make sense yet.

Additionally, with the simplified base case this now forms a standard recursion scheme over the natural number argument. You could express it as a fold over natural numbers:

data Nat = Zero | Succ Nat

foldNat :: b -> (b -> b) -> Nat -> b
foldNat z s Zero = z
foldNat z s (Succ n) = s (foldNat z s n)

comb :: [a] -> Nat -> [[a]]
comb r = foldNat [[]] (\r' -> (:) <$> r <*> r')

I would not recommend to actually write it this way, but I think it is good to be aware of it.