5

xシード値から始めて、各ステップで新しいシード値と出力される値を生成するパターンに出くわしました。私が望む最終結果は、出力値のリストです。これは、次の関数で表すことができます。

my_iter :: (a -> (a, b)) -> a -> [b]
my_iter f x = y : my_iter f x'
   where (x',y) = f x

そして、これを使用する不自然な例は、フィボナッチ数を生成することです。

fibs:: [Integer]
fibs = my_iter (\(a,b) -> let c = a+b in ((b, c), c)) (0,1)
-- [1, 2, 3, 5, 8...

私の問題は、この種のことを行うためのより慣用的な方法がある可能性が非常に高いと感じていることです。私の機能の慣用的な代替手段は何ですか？

私が今考えることができるiterateのはプレリュードからのものだけですが、いくつかの欠点があります。

1つの方法は、最初に繰り返し、後でマップすることです。

my_iter f x = map f2 $ iterate f1 x
    where f1 = fst . f
          f2 = snd . f

ただし、fを別々のf1関数とf2関数に分割する自然な方法がない場合、これは見苦しく見える可能性があります。（考案されたフィボナッチの場合、これは簡単ですが、生成された値がシードの「独立した」関数ではないため、分割するのがそれほど簡単ではない場合があります）

もう1つの方法は、「出力」値をシードと一緒にタプルし、別のステップを使用してそれらを分離することです（ソート用の「シュワルツ変換」のようなものです）。

my_iter f x = map snd . tail $ iterate (f.fst) (x, undefined)

しかし、シード（（f.fst）ビット）に到達するために生成された値を無視し、最初のダミーの生成された値に「未定義」の値を追加する必要があるため、これは奇妙に思えます。

4

4 に答える 4

11

すでに述べたように、必要な関数はですunfoldr。名前が示すように、それはの反対ですfoldrが、それが本当である理由を正確に理解することは有益かもしれません。タイプは次のfoldrとおりです。

(a -> b -> b) -> b -> [a] -> b

最初の2つの引数は、型の何かを取得する方法でありb、リストの2つのデータコンストラクターに対応します。

[]  :: [a]
(:) :: a -> [a] -> [a]

...の各出現は。[a]に置き換えられbます。[]ケースが入力なしでを生成することに注意して、入力として受け取るb関数として2つを統合できMaybe (a, b)ます。

(Maybe (a, b) -> b) -> ([a] -> b)

余分な括弧は、これが本質的にある種類の変換を別の種類の変換に変える関数であることを示しています。

ここで、両方の変換の方向を逆にするだけです。

(b -> Maybe (a, b)) -> (b -> [a])

結果はまさにのタイプですunfoldr。

これが示す基本的な考え方は、他の再帰データ型にも同様に適用できます。

于 2012-09-25T20:36:57.763 に答える
6

あなたが探している標準的な関数はunfoldrと呼ばれています。

于 2012-09-25T20:15:36.640 に答える
5

Hoogleは、名前だけでなくタイプによる検索機能もサポートしているため、この場合は非常に便利なツールです。

あなたの場合、あなたは希望のタイプを思いついた(a -> (a, b)) -> a -> [b]。それを入力しても結果は得られません-うーん。

ええと、構文が少し異なる標準関数があるかもしれません。たとえば、標準関数の引数が反転している場合があります。(a -> (a, b))どこかに型アノテーションが含まれているものを探しましょう。今回はたくさんの結果があるので幸運ですが、それらはすべてエキゾチックなパッケージに入っており、どれも非常に役に立たないようです。

関数の2番目の部分の方が一致している可能性があります。結局、最初の要素からリストを生成したいので、入力しa -> [b]て検索を押します。最初の結果：unfoldr-ビンゴ！

于 2012-09-25T20:59:20.150 に答える
2

別の可能性はiterateMモナドにStateあります：

iterateM :: Monad m => m a -> m [a]
iterateM = sequence . repeat

標準ライブラリにはありませんが、簡単に作成できます。

だからあなたmy_iterは

evalState . sequence . repeat :: State s a -> s -> [a]
于 2012-09-25T20:45:07.400 に答える