1

Haskell から始まり、State Monad で立ち往生...

そこで、私は Haskell の State Monad を理解しようとしています。それを理解するために、PRBS シーケンスを生成するコードを書いています。興味のある方は、論文「Pseudo Random Sequences and Arrays」で説明されています。この論文の無料コピーは doi: 10.1109/PROC.1976.10411 から入手できます。

本質的な計算は非常に単純です。シフト レジスタと生成多項式があります。生成多項式は、シフト レジスタのどのビットを取得して合計し (モジュロ 2)、シフト レジスタの MSB を取得するかを示します。次の反復では、この計算された MSB を取得し、右シフト操作を行った後にシフト レジスタの MSB に貼り付けます。

モナドなしでこれを行うためのコードは非常に単純です:

import Data.List

m = (4::Int)              -- This is the degree of the polynomial
p = tail $ [4, 1, 0]      -- This is a actual polynomial
s = 1 : replicate (m-1) 0 -- This is the initial state. Note that the head is the MSB

chSt poly s = msb poly s : init s -- changes the shift register 's'
    where
        msb poly s = let tot = sum $ map ( (reverse s) !! ) poly
                     in  tot `mod` 2

word p s = take n $ bits p s
    where
        bits p s = last s : bits p (chSt p s)
        n        = 2 ^ (length s) - 1

出力は次のとおりです。

[ghci] word p s      --> [0,0,0,1,0,0,1,1,0,1,0,1,1,1,1]

それが私が欲しいものです。

もちろん、シフトレジスタは変更する状態と見なすことができるので、この目的のために状態モナドを使用できます。状態モナドについて学ぶには単純すぎる問題かもしれませんが、これは状態モナドを使って実装できる完璧な例かもしれないと思います。だからここに私がしたことがあります：

getVal :: [Int] -> State [Int] Int
getVal poly = do
    curState <- get
    let lsb = last curState
    modify $ chSt poly
    return lsb

bitM :: State [Int] Int 
bitM = getVal p

import Control.Monad.Stateこれは、プログラムの最初の likeとともに、コードの前のコード セグメントに追加するだけです。これを GHCI にインポートして状態計算を確認すると、以下に示すように個々の値を取得できます。

[ghci] runState ( bitM  ) s                                   --> (0,[0,1,0,0])
[ghci] runState ( bitM >> bitM  ) s                           --> (0,[0,0,1,0])
[ghci] runState ( bitM >> bitM >> bitM ) s                    --> (0,[1,0,0,1])
[ghci] runState ( bitM >> bitM >> bitM >> bitM) s             --> (1,[1,1,0,0])
[ghci] runState ( bitM >> bitM >> bitM >> bitM >> bitM) s     --> (0,[0,1,1,0])
[ghci]

したがって、状態が正しく更新され、返される値も正しいです。ここで、配列を作成できるように、 s時間に演算子wordを適用する前の実装の関数のような関数を作成したいと思います。私はこれを行う方法についてもまったく無知です。次のような一連の関数を入れたくないことに注意してください。>>bitMnword p s

f1 = bitM
f2 = bitM >> bitM
f3 = bitM >> bitM >> bitM 
...

渡す関数が 1 つn必要であり、bitM評価を連続して実行しn、連続する計算で内部的に状態を自動的に渡し、結果の値を収集し、結果として配列を作成します。どうすればそれを行うことができますか？これを行う方法がわかりません。どんな助けでも大歓迎です！

4

1 に答える 1

7

少し見てみると、はアクションのリストと考えることができるので、単に のシグネチャであるまたはより単純なbitM >> bitM >> ... > bitMを探しています。私たちはタイプの何かで終わるでしょうInt -> m a -> [m a]Int -> a -> [a]replicate

[State [Int] Int]

[State [Int] Int] -> State [Int] [Int]今、私たちは、またはより単純に:を探しています。[m a] -> m [a]これはたまたまsequenceです。したがって、あなたが探している

sequence . replicate n $ bitM

これはたまたま でありreplicateM、タイプはInt -> m a -> m [a]です。

于 2014-02-26T09:23:25.973 に答える