Nieskończona lista nieskończonych liczników

Question

Dla tych, którzy mają podejrzane umysły, to nie jest praca domowa, tylko ciekawa.

Biorąc pod uwagę skończony alfabet, czy możliwe jest skonstruowanie listy nieskończenie długich słów wykonanych z alfabetu w odwrotnej kolejności leksykograficznej?

to podano alfabetu "ab"

możliwe jest skonstruowanie listy:

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

gdzie ... przedstawia listę (i listę listy) rozciągający się w nieskończonej długości.

naiwna próba jest:

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

ale to nie działa, ponieważ pozostało rekurencyjne.

Oczywiście, w wersji roboczej, jeśli próbowałeś wydrukować wynik, zobaczyłbyś tylko pierwszy element drukowany jako nieskończona lista pierwszego elementu z alfabetu. Jednakże, powinieneś być w stanie to zrobić:

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

i zobaczyć wyjście:

aa 
ba 
ab 
bb 

Answer 1

Dlaczego nie fix to?

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

Prawdopodobnie nie jest to najbardziej efektywne rozwiązanie, ale przynajmniej to działa:

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

Progresja wygląda jak kodowanie numeru bazowego N z najmniej znaczącym wykopem to po lewej stronie, więc możemy zbliżyć go jako

1. Zrób „N” do bazy przy użyciu funkcji falfabetów jak litery.
2. mapf do [0..]
3. Append repeat $ head alphabets do każdego elementu listy.

Answer 4

można znaleźć następujące podejście zabawny/mylące:

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

ten pochodzi z obserwacji, że pierwsze litery naśladowania wzór "ababab...", drugi litery naśladowania wzór "aabbaabbaabb..." litery trzecie naśladowania wzór "aaaabbbbaaaabbbb...", itp.

Answer 5

Co z tym?

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

także (\x -> ['a':x,'b':x]) mogą być napisane w Applicative jak ([('a':),('b':)] <*>) . pure jeśli wziąć pod uwagę, że jest to bardziej eleganckie.

Answer 6

Jeszcze inna wersja opiera się na idei Daniela:

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