3
\$\begingroup\$

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?

\$\endgroup\$
1
  • 1
    \$\begingroup\$ This function is called replicateM in Control.Monad \$\endgroup\$
    – 4castle
    Oct 17 at 21:23
2
\$\begingroup\$

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.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ I'd probably choose comb n = sequenceA . replicate n instead of explicit recursion. Feel free to incorporate that into your answer if you want to :) \$\endgroup\$
    – Zeta
    Sep 18 at 21:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.