Бесконечный список бесконечных счетчиков

Question

Для людей с подозрительным умом это не домашняя работа, а просто любопытная.

При условии ограниченного алфавита, возможно ли составить список бесконечно длинных слов из алфавита в обратном лексографическом порядке?

то есть с учетом алфавита "ab"

возможно ли построить список:

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

, где ... представляет список (и список списков), простирающийся до бесконечностидлина.

Наивная попытка:

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..." и т. д.

Answer 4

Как насчет этого?

f@(a:as) = a:('b':a):concatMap (\x -> ['a':x,'b':x]) as where a = ['a','a'..]

Также (\x -> ['a':x,'b':x]) можно записать в Applicative как ([('a':),('b':)] <*>) . pure, если вы считаете его более элегантным.

Answer 5

Еще одна версия, основанная на идее Даниэля:

counters = transpose $ map cycle $ iterate (>>= \x -> [x,x]) "ab"

Answer 6

Последовательность выглядит как кодирование числа base-N с наименьшей значащей цифрой слева, поэтому мы можем приблизиться к нему как

1. Создайте функцию «к основанию N» f, используя алфавиты в качестве букв.
2. map f до [0..]
3. Добавить repeat $ head alphabets к каждому элементу списка.