8

私は Haskell をまったく初めて使用するので、質問がばかげている場合は申し訳ありません。

私がやりたいことは、リストを再帰的に構築すると同時に、再帰呼び出しに基づいて累積値を構築することです。これは私が Coursera コースで行っている問題のためのものなので、正確な問題は投稿しませんが、類似したものを投稿します。

たとえば、int のリストを取得し、それぞれを 2 倍にしたいとします (単に使用できる例の目的のために無視しますmap) が、リストに数字 '5' が表示される回数もカウントしたいと考えています。

したがって、倍増を行うには、次のようにします。

foo []     = []
foo (x:xs) = x * 2 : foo xs

ここまでは簡単。しかし、どうすれば 5 の回数を数えることができるxでしょうか? 私が得た最善の解決策は、このような明示的なアキュムレータを使用することです。これは、リストを逆にするので好きではないので、最後に逆にする必要があります。

foo total acc []     = (total, reverse acc)
foo total acc (x:xs) = foo (if x == 5 then total + 1 else total) (x*2 : acc) xs

しかし、これは以前に使用したことのないモナドでより適切に処理できるはずですがState、見たパターンに適合する関数を構築しようとすると、への再帰呼び出しのために行き詰まりますfoo. これを行うより良い方法はありますか？

編集:これは非常に長いリストで機能する必要があるため、再帰呼び出しも末尾再帰にする必要があります。(私がここに持っている例は、Haskell の 'tail recursion modulo cons' のおかげで、なんとか末尾再帰になっています)。

4

2 に答える 2

11

モナドを使用Stateすると、次のようになります。

foo :: [Int] -> State Int [Int] 
foo [] = return []
foo (x:xs) = do
    i <- get
    put $ if x==5 then (i+1) else i
    r <- foo xs
    return $ (x*2):r

main = do
     let (lst,count) = runState (foo [1,2,5,6,5,5]) 0 in
         putStr $ show count
于 2013-07-07T17:12:01.580 に答える