How to generate a list of all possible lines from the shortest to the longest

Question

I need to create an endless list of strings using numbers and letters. The first line should be just “a”, then “b” to “z”, then “0” to “9”, then “aa”, “ab”, etc.

I can easily generate those that have one character, but then it becomes more complex.

Answer 1

So, suppose we already had this list of all possible lines:

allStrings :: [String] allStrings = ... 

Given allStrings , how can we create a different list of all possible strings?

  alsoAllStrings :: [String] 

Let's look at each possible line as a prefix of one character and the suffix of the line

  alsoAllStrings = [ c : s 

A line suffix is ​​either an empty line or a member of a list of all possible lines.

  | s <- "" : allStrings 

The single character prefix is ​​in 'a' thru 'z' or '0' thru '9' .

  , c <- ['a'..'z'] ++ ['0'..'9'] ] 

(this is using lists - we can also do the same with concatMap :

 alsoAllStrings = concatMap (\s -> map (:s) $ ['a'..'z'] ++ ['0'..'9']) $ "" : allStrings 

)

Now back to the original question. How to find allStrings ?

In most languages, we could not - this is an endless list of lines, the program never ended. But since Haskell is lazy, it's cool, creating only the part of allStrings that we actually use.

One amazing thing that this allows us to do is to define allStrings in terms of alsoAllStrings .

  allStrings = alsoAllStrings 

Or, more likely, from the point of view of himself.

  allStrings = [ c : s | s <- "" : allStrings, c <- ['a'..'z'] ++ ['0'..'9'] ] 

This is called core-recursive data — data that is defined on its own. Try it in ghci:

  ghci> let allStrings = [ c : s | s <- "": allStrings, c <- ['a'..'z'] ++ ['0'..'9'] ] ghci> take 100 allStrings ["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z","0","1","2","3","4","5","6","7","8","9","aa","ba","ca","da","ea","fa","ga","ha","ia","ja","ka","la","ma","na","oa","pa","qa","ra","sa","ta","ua","va","wa","xa","ya","za","0a","1a","2a","3a","4a","5a","6a","7a","8a","9a","ab","bb","cb","db","eb","fb","gb","hb","ib","jb","kb","lb","mb","nb","ob","pb","qb","rb","sb","tb","ub","vb","wb","xb","yb","zb","0b","1b"] 

The reason it works (and not just the cycle endlessly) is because it defines a part of itself before it uses it. The first elements that we include in allStrings are single character extensions to the empty string "" . Thus, by the time we start repeating allStrings elements for use as suffixes, the first pairs of allStrings elements allStrings already defined and available. And the more suffixes we process, the more allStrings elements allStrings defined and available for use as suffixes.

It is very similar to general heckellism, which determines the fibonacci number:

  fibs = 1 : 1 : zipWith (+) fibs (tail fibs) 

Don't be surprised if the core recursion takes some time to wrap your head. However, it’s worth trying to understand.

Answer 2

This can be done by getting all the combinations for strings 1,2,3 ... long, then connecting them all together.

I started with the combos function, which returned the entire list of strings with the given characters and the given length:

 combos :: [Char] -> Int -> [String] 

The first case is simple, just include the input characters in the lists:

 combos chars 1 = map (:[]) chars 

In the following case, we want "aa", "ab", "ac" ... to "zx", "zy", "zz". This is the same as map ("a" ++) ["a", "b", "c"...] ++ map ("b" ++) ["a","b",...] up to map ("z" ++) ["a","b"...] .

["a".."z"] same as combos chars 1 . This function can be written as:

 combos chars 2 = concatMap (\front -> map (front ++) (combos chars 1)) (combos chars 1) 

In the following case, we want "aaa", "aab", "zzy", "zzz". This is actually very similar to combo 2, except that we use combos chars 2 as the front instead of combos chars 1 :

 combos chars 3 = concatMap (\front -> map (front ++) (combos chars 1)) (combos chars 2) 

(note that combos chars 1 does not change, it just gives us a list of one line of characters to add to the end.)

See the template here? Now it can be generalized for all n as:

 combos :: [Char] -> Int -> [String] combos chars 1 = map (:[]) chars combos chars n = concatMap (\front -> map (front ++) (combos chars 1)) $ combos chars (n - 1) 

Finally, to get an endless list of all lines, just compare all combo results along with the required characters and the entire length:

 allCombos :: [String] allCombos = concatMap (combos (['a'..'z'] ++ ['0'..'9'])) [1..] 

Output Example:

 > take 100 allCombos ["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z","0","1","2","3","4","5","6","7","8","9","aa","ab","ac","ad","ae","af","ag","ah","ai","aj","ak","al","am","an","ao","ap","aq","ar","as","at","au","av","aw","ax","ay","az","a0","a1","a2","a3","a4","a5","a6","a7","a8","a9","ba","bb","bc","bd","be","bf","bg","bh","bi","bj","bk","bl","bm","bn","bo","bp","bq","br","bs","bt","bu","bv","bw","bx","by","bz","b0","b1"] 

Answer 3

I came up with the following solution:

 -- Gives us the concatenated cartesian product of two lists of strings strCartProd :: [String] -> [String] -> [String] strCartProd xs ys = [x ++ y | x <- xs, y <- ys] -- Create initial list of strings (map chars to 1-char strings) s :: [String] s = map (:[]) $ ['a'..'z'] ++ ['0'..'9'] -- Iterate and concatenate the resulting lists result :: [String] result = id =<< iterate (strCartProd s) [""] 

Answer 4

This can be done using the replicateM predefined function from (Control.Monad).

 string = concatMap (\n -> replicateM n (['a'..'z']++['0'..'9'])) [1..]