无限计数器的无限列表

Question

对于那些有可疑头脑的人来说,这不是家庭作业,只是好奇.

给定一个有限的字母表,是否有可能构建一个由反向词汇顺序的字母表组成的无限长单词列表？

即给出字母表 "ab"

是否可以构建列表:

["aaaaaa...", "baaaaa...", "abaaaa...", "bbaaaa...", "aabaaa...", ...]

where ...表示扩展到无限长度的列表(和列表列表).

一个天真的尝试是:

counters alphabet = [c:ounter | ounter <- counters alphabet, c <- alphabet]

但这不起作用,因为它是递归的.

当然,对于工作版本,如果您尝试打印结果,则只会看到第一个元素被打印为字母表中第一个元素的无限列表.但是,您应该能够这样做:

mapM_ (print . take 2) . take 4 . counters $ "ab"

并看到输出:

aa
ba
ab
bb

Answer 1

为什么不fix呢？

ghci> let bar = let foo ~(st:sts) = [c:st | c <- "ab"] ++ foo sts in fix foo
ghci> take 5 . map (take 5) $ bar
["aaaaa","baaaa","abaaa","bbaaa","aabaa"]
take 10 . map (take 5) $ bar
["aaaaa","baaaa","abaaa","bbaaa","aabaa","babaa","abbaa","bbbaa","aaaba","baaba"]

Answer 2

可能不是最有效的解决方案,但至少它有效:

counters alphabet = map f [0..]
  where f n = let (q, r) = quotRem n (length alphabet) in alphabet !! r : f q

> take 10 $ map (take 5) $ counters "ab"
["aaaaa","baaaa","abaaa","bbaaa","aabaa","babaa","abbaa","bbbaa","aaaba","baaba"]

Answer 3

您可能会发现以下方法有趣/令人困惑:

duplicates s ss = cycle ss : duplicates s (ss >>= \c -> s >> [c])
counters = transpose . join duplicates

这来自观察到第一个字母遵循图案"ababab...",第二个字母遵循图案"aabbaabbaabb...",第三个字母遵循图案"aaaabbbbaaaabbbb..."等.