haskell - 如何生成从最短到最长的所有可能字符串的列表

Question

我需要使用数字和字母生成无限的字符串列表。第一个字符串应该简单地是“a”，然后是“b”到“z”，然后是“0”到“9”，然后是“aa”、“ab”等。

我可以轻松地生成具有一个字符的字符，但随后会变得更加复杂。

Answer 1

所以，假设我们已经有了所有可能字符串的列表:

 allStrings :: [String]
 allStrings = ...

给定 allStrings ，我们如何创建另一个包含所有可能字符串的列表？

 alsoAllStrings :: [String]

让我们将每个可能的字符串视为单个字符前缀和字符串后缀

 alsoAllStrings = [ c : s 

字符串后缀要么是空字符串，要么是所有可能字符串列表的成员。

                  | s <- "" : allStrings

单个字符前缀在 'a'通过 'z'或 '0'通过 '9' .

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

(这是使用列表推导 - 我们也可以使用 concatMap 来做同样的事情:

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

)

现在让我们回到最初的问题。我们如何找到 allStrings ?

在大多数语言中，我们不能——它是一个无限的字符串列表，程序永远不会完成。但是由于 Haskell 是懒惰的，所以只生成 allStrings 的数量就很酷了。正如我们实际使用的那样。

这让我们做的一件令人惊讶的事情是我们可以定义 allStrings根据 alsoAllStrings .

 allStrings = alsoAllStrings

或者，更有可能的是，就其本身而言。

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

这被称为核心数据——根据自身定义的数据。
在 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"]

它起作用(并且不仅仅是无限循环)的原因是它在使用自身之前定义了自身的一部分。我们在 allStrings 中包含的第一个元素是空字符串 "" 的单个字符扩展.所以当我们开始遍历 allStrings 的元素时用作后缀，前几个元素 allStrings已经定义并且可用。而且我们处理的后缀越多， allStrings 的元素就越多。已定义并可用作后缀。

它与核心递归定义斐波那契数的常见haskellism非常相似:

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

如果 corecursion 需要一段时间来绕开你的脑袋，请不要感到惊讶。不过，值得努力去理解。