4

これは SO に関する私の最初の投稿であり、Haskell には比較的慣れていないため、間違いや私のコードが慣用的でない場合はご容赦ください。

a、f(a)、f(f(a))... の次の 2 つの直感的な説明を考えてみましょう。

A. 以下を含むリスト: a、a への f の適用、それへの fの適用、それへの f の適用...

B. i 番目の位置に i ネストされた f から a への適用を含むリスト。

私の問題はiterate、Haskell の関数を使用してAを実行しようとして火傷を負ったことです。私の実際のアプリケーションはシミュレーションですが、次の不自然な例が問題を浮き彫りにしています。

import Control.Monad.State

example :: State Int [[String]]

step :: [String] -> State Int [String]
step l = do
         currentState <- get
         let result = if (currentState == 1)
                          then "foo":l
                          else "bar":l
         put (currentState + 1)
         return result

example = do
          sequence $ take 3 . iterate (>>= step) $ return []

これらの定義により、

evalState example 1

結果:

[[],["foo"],["bar","bar"]]

明らかに、AではなくiterateBです! 関数は入力リストに何かを追加するだけなので、状態に関係なく、結果が になる可能性はありません!stepstep ["foo"]["bar", "bar"]

私はここで何が起こっているのかを理解していると言わせてください.step f(a))、状態が変更されたため、2 番目のリスト項目から取得されるのではなく、再計算されます。また、実際のアプリケーションでは、累積リストをステート内に配置することでこれを回避できることにも気付きました。

それにもかかわらず、これを投稿する理由は 2 つあります。

まず、ポイントは、実際にはBiterateを実行するときに、初心者がAを実行すると誤解する可能性がある方法で頻繁に説明されることです。これには、Learn You A Haskell (それ以外の場合は非常に便利だと思います) が含まれますが、SO への投稿 (たとえば、hereおよびhere ) も含まれます。実際、LYAHFGG の口頭での説明は、ほぼ正確に上記の定義Aです。したがって、これが原因でバグが発生し、説明を探している他の Haskell 初心者のためのリソースとして、これに関する投稿を行うと役立つ場合があります (したがって、より正確で、技術的で、より適切な言い回しの説明を、Aとの違いiterate以下B）。

第二に、実際にA !を実行する関数があるかどうかに興味があります。つまり、上記のステートフルな例で、[a, b = f(a), f(b), ...] というリストを作成するにはどうすればよいでしょうか? 言い換えれば、与えられた

example2 = do
           firstResult <- step []
           secondResult <- step firstResult
           return $ [[], firstResult, secondResult]

そのために

evalState example2 1

望ましい結果が得られます

[[],["foo"],["bar","foo"]]

example2を使用してどのように書き換えることができiterateますか?

初心者 Haskell リストに、のメモ化バージョンに関する関連する質問iterateが投稿されました。ただし、そのクエリには回答がなかったようです。

怠惰が私のアプリケーションの問題であるかどうかは完全にはわかりません。の厳密なバージョンはiterate私が望むことをしますか? 以下のような私自身の素朴な「厳密な反復」は、何の違いもないようです。

iterate' f x = x : rest
               where previous = f x
                     rest = previous `seq` iterate f previous

このすべてに関する洞察をいただければ幸いです。

4

2 に答える 2

17

A.とB.の間に違いはありません。参照透過性により、同じものになります。
問題の核心は、ステートフル計算の実行のコンテキストでそれらを解釈していることのようです。そのコンテキストでは、期待しているAの類似物は
A'です。1。最初の計算の結果をリストに入れ、2。前の結果から次の計算を決定し、実行して追加することにより、結果リストを作成します。その結果をリストに追加します。3。goto2.B
の類似物は
B'です。計算のリストを作成し（反復（>> =ステップ））、そこから次々に計算を実行して結果リストを作成します。
ステートレス計算の場合、またはB'で生成されたすべての計算に同じ初期状態を渡す場合、唯一の違いは効率にありますが、を使用している場合sequence、各計算は異なる状態で開始されるため、A'から異なる結果が得られます。 。あなたの内訳example、私たちは持っています

actionList = take 3 $ iterate (>>= step) (return [])
           = [return [], return [] >>= step, return [] >>= step >>= step]

内のアクション（またはモナディック値）のリストState Int [String]。さて、それに応募sequenceすると、

example = sequence actionList

実行されると、これらのアクションの最初のアクションを初期状態で実行し、2番目のアクションを最初の状態で更新された状態で実行し、3番目のアクションを2番目の状態で更新された状態で実行するアクションを取得します。期待する動作を得るには、すべて同じ初期状態で実行する必要があります。

基本的に、typeの値はtypeState s vの関数ですs -> (v, s)。iterate関数のリストを作成し、sequenceこれらの関数を適用して、さまざまなs引数を提供します（それぞれが前の関数sによって生成されます）。

目的の動作を得るには、新しいコンビネータを導入する必要があります。とてもいいですが、ごく少数のモナドでしか使えません

iterateM :: Monad m => (a -> m a) -> m a -> m [a]
iterateM step start = do
    first <- start
    rest <- iterateM step (step first)
    return (first:rest)

生成する

Prelude Control.Monad Control.Monad.State> evalState (fmap (take 4) (iterateM step (return []))) 1
[[],["foo"],["bar","foo"],["bar","bar","foo"]]

しかし、それは十分に怠惰なモナドでのみ機能し、数少ないものの1つであり、そうで(>>=)はありません。また、、を使用しても、後の状態を使用することはできません。計算を続行するには、新しい状態にする必要があります。他のモナドで使用できるものを取得するために、カウントパラメータを追加できます。Control.Monad.State.LazyControl.Monad.State.StrictC.M.S.LazyiterateMput

iterCountM :: (Monad m) => Int -> (a -> m a) -> m a -> m [a]
iterCountM 0 _ _ = return []
iterCountM k step start = do
    first <- start
    rest <- iterCountM (k-1) step (step fisrt)
    return (first:rest)

したがって、柔軟性は失われますが、より多くのモナドで使いやすさが向上します。

于 2011-10-28T11:04:12.683 に答える
3

これはあなたが提起した質問に答えないかもしれませんが、あなたがしていることは非常に似ているように聞こえますunfoldr.

step (seed, l) = Just (l', (seed', l'))
  where seed' = succ seed
        l' = (if seed == 1 then "foo" else "bar"):l

ghci> take 3 $ unfoldr step (1, [])
[["foo"], ["bar", "foo"], ["bar", "bar", "foo"]]

モナドは必要ありません。あなたが実際に何をしようとしているのかを指定しなかったので、私は暗闇の中で突き刺していますが、私がstep正しかったかどうかにかかわらず、持ち帰りのメッセージは、unfoldr単純な状態のスレッド化にも使用できるということです.

unfoldr :: (seed -> Maybe (val, seed)) -> seed -> [val]
于 2011-10-29T06:03:06.713 に答える