無限のカウンターの無限リスト

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

プログレッションは、最下位桁のベースNコードをエンコードするように見えますその左に、私たちは、文字としてあなたアルファベットを使用して機能f「Nをベースに、」作る

1. としてそれに近づくことができます。リストの各要素に[0..]
2. 追加repeat $ head alphabetsから
map
3. f。

Answer 4

次のアプローチを見つけることが混乱を招く/面白い：

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

これは、最初の文字がパターン"ababab..."、二文字はパターン"aabbaabbaabb..."、第三文字が続くに従ってくださいに従って観察から来ていますパターン"aaaabbbbaaaabbbb..."など

Answer 5

これはどうですか？あなたはそれがよりエレガントであることを考慮すれば

また

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

(\x -> ['a':x,'b':x])は([('a':),('b':)] <*>) . pureとしてApplicativeに書き込むことができます。

Answer 6

ダニエルの考え方に基づいて、さらに別のバージョン：

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