1

タイトルの内容を実装しようとしましたが、遅延評価のために結果を取得できません:

data AlgorithmM = AlgorithmM {fm::[Int],fa::[Int],fj::Int,fn::Int}
m1a :: AlgorithmM->(IO (),AlgorithmM)
m1a (AlgorithmM m a j n) = (return (),AlgorithmM (2:m) a j n)

m1b :: AlgorithmM->(IO (),AlgorithmM)
m1b (AlgorithmM m a j n) = (return (),AlgorithmM m (take n $! repeat 0) j n)


m2 algo = (visit False $ fa algo,algo)
  where visit True l =do
             mapM (\z->putStr $ show z) l
             putStr "\n"
    visit False (x:xs) = do
                          mapM (\z->putStr $ show z) xs
                          putStr "\n"
initN :: AlgorithmM->(IO (),AlgorithmM)
initN (AlgorithmM m a j n) = (return (),AlgorithmM m a j ((length m)-1))

m3 :: AlgorithmM->(IO (),AlgorithmM)
m3 (AlgorithmM m a j n) = (return (),AlgorithmM m a n n)


m4 :: AlgorithmM->(IO (),AlgorithmM)
m4 (AlgorithmM m a j n) = if (a !! j) == (m !! j) - 1 then m4 (AlgorithmM m (setajZero a j) (j-1) n) else  (return (),AlgorithmM m a j n)
 where setajZero (x:xs) 0 = 0:xs
       setajZero (x:xs) j = x:(setajZero xs (j-1))

m5 :: AlgorithmM->(IO (),AlgorithmM)
m5 (AlgorithmM m a j n) = if j==0 then (return (),AlgorithmM m a j n) else m2 (AlgorithmM m a j n)

bind :: (IO(),AlgorithmM)->(AlgorithmM->(IO (),AlgorithmM))->(IO(),AlgorithmM)
bind g f = f $! snd g 

testAlgorithmM = m1a (AlgorithmM [2,2,2] [] 0 0) `bind` initN `bind` m1b `bind` m2 `bind` m3 `bind` m4 `bind` m5

main = do
    let (x,y) = testAlgorithmM
    x

上記のコードをインタープリターに実行すると、

例外: Prelude.(!!): インデックスが大きすぎます

私が思うに、m1a のリストは n+1 を展開しないため、m4 は例外をスローします。

何か案は？ありがとう。

4

3 に答える 3

2

上のポスターが言ったように、あなたはリストを不適切に索引付けしました。に置き換える(a !! j) == (m !! j) - 1と(a !! (j - 1)) == (m !! (j - 1)) - 1動作します。

ただし、余分なreturn ()ステートメントはすべて何もしません。モナドの役割、特にIO. また、怠惰がコードを機能させないと信じているようです。これは技術的には正しいのですが、問題は haskell が遅延しているということではなく、何を計算したいかを伝えていないことです。

コードを修正して、すべてのreturn ()ステートメントを削除しました。コードの実行を変更していないことに注意してください。オリジナルとまったく同じ順序ですべてを実行します。

data AlgorithmM = AlgorithmM {fm::[Int],fa::[Int],fj::Int,fn::Int} deriving Show

m1a :: AlgorithmM -> AlgorithmM
m1a (AlgorithmM m a j n) = AlgorithmM (2:m) a j n

m1b :: AlgorithmM -> AlgorithmM
m1b (AlgorithmM m a j n) = AlgorithmM m (take n $! repeat 0) j n

m2 :: AlgorithmM -> (String, AlgorithmM)
m2 algo = (visit False $ fa algo,algo)
  where visit True l = (concatMap show l) ++ "\n"
        visit False (x:xs) = concatMap show xs ++ "\n"

initN :: AlgorithmM -> AlgorithmM
initN (AlgorithmM m a j n) = AlgorithmM m a j ((length m)-1)

m3 :: AlgorithmM-> AlgorithmM
m3 (AlgorithmM m a j n) = AlgorithmM m a n n


m4 :: AlgorithmM -> AlgorithmM
m4 (AlgorithmM m a j n) = if (a !! (j - 1)) == (m !! (j - 1)) - 1 then m4 (AlgorithmM m (setajZero a j) (j-1) n) else AlgorithmM m a j n
 where setajZero (x:xs) 0 = 0:xs
       setajZero (x:xs) j = x:(setajZero xs (j-1))

m5 :: AlgorithmM -> (String, AlgorithmM)
m5 (AlgorithmM m a j n) = if j==0 then ("", AlgorithmM m a j n) else m2 (AlgorithmM m a j n)

testAlgorithmM = s0
    where (s0, a) = m2 $ m1b $ initN $ m1a (AlgorithmM [2,2,2] [] 0 0)
          b       = m5 $ m4 $ m3 a

調べると、毎回m2電話していることがわかります。visit Falseこれをさらに減らすことができます

m2 :: AlgorithmM -> (String, AlgorithmM)
m2 algo = ((\xs -> concatMap show xs ++ "\n") $ tail $  fa algo,algo)

visit関数を に対応する関数の分岐に置き換えただけFalseです。

次に、で何が起こるかという問題がありtestAlgorithmMます。繰り返しますが、実行は同じです (strictness プロパティを削除しただけです)。ただし、の値はtestAlgorithmMisであるため、目的の出力を生成するために it の値は必要ないため、s0評価されないことに注意してください。m5 $ m4 $ m3 a元のコードでは、これが起こっていることを確認することは不可能でしたが、すべての難読化を削除すると、明らかに明らかです。

関数アプリケーションのチェーンの途中で文字列を作成することは、中間状態を保存する方法のようです。その場合は、ST モナドを調べる必要があります。IOできないことを除いて、同じことを行いprintますputStrLn。ただし、すべての計算を実行した後、これらのことを行うことができます。

アルゴリズム変換のチェーン全体を計算する場合は、次の手順を実行する必要があります。

testAlgorithmM = (b,s0)
    where (s0, a) = m2 $ m1b $ initN $ m1a (AlgorithmM [2,2,2] [] 0 0)
          b       = m5 $ m4 $ m3 a

これは、見たい場合に備えて、中間文字列値も出力します。

于 2013-10-06T21:20:20.950 に答える
1

まず第一に、怠惰は純粋な関数の値に目に見える影響を与えるべきではありません (非常に病理学的な状況を除いて)。したがって、リストのインデックス作成エラーは、あまりにも怠惰な結果であってはなりません。

エラー メッセージを額面どおりに受け取って、エラーが直接m4呼び出すから来ていると推測してみましょう。GHCi のデバッガPrelude.!!を使ってみましょう:

ghci> :break m4
ghci> :step main
ghci> :continue
Stopped at foo.hs:(24,1)-(26,50)
ghci> :step
Stopped at foo.hs:24:27-137
_result :: (IO (), AlgorithmM) = _
a :: [Int] = _
j :: Int = _
m :: [Int] = _
n :: Int = _
ghci> :list
23  m4 :: AlgorithmM->(IO (),AlgorithmM)
24  m4 (AlgorithmM m a j n) =
      if (a !! j) == (m !! j) - 1
         then m4 (AlgorithmM m (setajZero a j) (j-1) n)
         else  (return (),AlgorithmM m a j n)
25   where setajZero (x:xs) 0 = 0:xs
ghci> :force a j m n
a = [0,0,0]
j = 3
m = [2,2,2,2]
n = 3

次に何が起こると思いますか？

于 2013-10-06T21:15:16.937 に答える
0

このエラーは、インデックスがリストの末尾を超えていることを意味します。怠惰とは何の関係もありません。実装を見てください。

あなたの実装は明らかに間違っています。おそらく、あなたはそれが正しいことを証明しただけですか？

于 2013-10-06T20:54:43.023 に答える