交互の無限ストリームを作成するにはどうすればよいですか？

Question

無限の文字列を作成したいのですが：

「」といくつかの文字から始まり、「abc」としましょう。

["", "a", "b", "c", "aa", "ba", "ca", "ab", ..] 

基本的なロジックは、最高の長さの最後の要素を取り、私の最初のリストから文字のそれぞれを追加することです「ABC：私はこのようになります無限のストリームで終わるにはどうすればよい正確

"彼らに繰り返し、繰り返す。しかし、これがHaskellで正しい方法であるかどうかはわかりません（問題の手続き的解決策に近いようです）。

私はのの流れを作ったので、私の最初の試みは一つだけの要素指定されたストリームを作成することでした：これは動作します

let as = iterate ((++) "a") "" 

が、私はこれは私が最初に取得することができるように進化させることができるかわかりませんストリーム。

Answer 1

井戸iterateにはいくつかの便利な概念がありますが、それ自体では解決策にはなりません。あなたがしなければならないことは、あなたのパターンを認識しそこから構築することです。

"" , a: "", b : "", c : "", a: a:"", b : a : "", c : a : "", a : b : "" 

だから、明らかに我々は'a':、'b':と'c':の""と3修飾機能の基本ケースを持っています。それを書き留めましょう！

mods :: [String -> String] 
mods = [ (x:) | x <- "abc" ] 

strings :: [String] 
strings = baseCase : stringsRecursiveCase 
where baseCase = "" 

再帰的なケースは何ですか。さてあなたは、最新の文字列を取り、修飾子のそれぞれを適用一度に一つの機能：

stringsRecursiveCase = [ f s | s <- strings , f <- mods ] 

今、私たちはfunctionallityを観察し、確認するためにテストすることができます。

take 15 strings 
["","a","b","c","aa","ba","ca","ab","bb","cb","ac","bc","cc","aaa","baa"] 

Answer 2

のは、我々がすでに持っているとしましょうのような文字列のリスト。どのようにしてその文字列から次の要素を生成できますか？まあ、我々はすべての要素を取り、その前に'a'、'b'と'c'を追加することができます。

Prelude> concatMap (\xs -> ['a' : xs, 'b' : xs, 'c' : xs]) ["", "a", "b", "c"] 
["a","b","c","aa","ba","ca","ab","bb","cb","ac","bc","cc"] 

は、これまでのところ良いようです。のは、その名前を挙げてみましょう：

step :: [String] -> [String] 
step = concatMap (\xs -> ['a' : xs, 'b' : xs, 'c' : xs]) 

我々は今、ベース値とstepを再帰的に私たちの無限のストリームを定義することができます。

stream :: [String] 
stream = "" : step stream 

Answer 3

はここiterateを使用しないソリューションです。

import Control.Applicative 
gen = [(++ "a"), (++ "b"), (++ "c")] 
expand v = concatMap (<$> v) gen 
v = concat $ iterate expand [""] 

トリッキーな部分はexpandです。少しわかりやすい関数の要約版です。

expand v = concat [ fmap f v | f <- gen ] 

リストの各文字列にジェネレータの各文字を追加します。リスト[ [""], expand [""], expand . expand $ [""], ...]の無限のリストを生成することによって一緒に、最初の数回の反復で

expand [""] = ["a", "b", "c"] 
expand ["a", "b", "c"] = ["aa", "ba", "ca", "ab", "bb", "cb", "ac", "bc", "cc"] 

iterateコマンドの絆、それを探しています。