Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Infinite list of infinite counters

For those with suspicious minds, this is not homework, just curious.

Given a finite alphabet, is it possible to construct a list of infinitely long words made from the alphabet in reverse lexographic order?

i.e. given the alphabet "ab"

is it possible to construct the list:

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

where ... represents the list (and list of lists) extending to infinite length.

A naïve attempt is:

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

but this doesn't work since it is left recursive.

Of course, with a working version, if you tried to print the result, you would only see the first element being printed as an infinite list of the first element from the alphabet. However, you should be able to do this:

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

and see the output:

aa
ba
ab
bb
like image 480
pat Avatar asked Jan 06 '12 19:01

pat


1 Answers

Why not fix it?

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"]
like image 61
Daniel Fischer Avatar answered Sep 16 '22 21:09

Daniel Fischer