1

と に似た 2 つの機能がfilterありtakeWhileます。

filterAcc, takeWhileAcc :: ([a] -> Bool) -> [a] -> [a]
filterAcc p xs = go xs []
    where go [] acc     = acc
          go (x:xs) acc
            | p (x:acc) = go xs (x:acc)
            | otherwise = go xs acc

takeWhileAcc p xs = go xs []
    where go [] acc     = acc
          go (x:xs) acc
            | p (x:acc) = go xs (x:acc)
            | otherwise = acc

どちらも述語とリストを取り、述語が累積された結果を入力として受け取るという点で通常のfilterand とは異なります。takeWhile

私の問題は、filter even [1..]すぐに（遅延して）出力の生成を開始しながら、filterAcc (any even) [1..]ハングすることです。私の疑いは、ヘルパー関数goがこれらの関数の遅延動作を妨げているということです。

これらの関数を遅延して動作させるにはどうすればよいですか?

4

2 に答える 2

6

問題は、コンス ケースがgo常にそれ自体の末尾呼び出しで終了することです。リストの最後に達したときにのみ有用なものを返しますが、これはもちろん無限リストでは決して起こりません。

代わりに、要素を返す必要があります。

filterAcc, takeWhileAcc :: ([a] -> Bool) -> [a] -> [a]
filterAcc p xs = go xs []
    where go [] acc     = []
          go (x:xs) acc
            | p (x:acc) = x : go xs (x:acc)
            | otherwise = go xs acc

takeWhileAcc p xs = go xs []
    where go [] acc     = []
          go (x:xs) acc
            | p (x:acc) = x : go xs (x:acc)
            | otherwise = []
于 2012-11-21T04:24:04.253 に答える
1

レイジー リストの消費は通常、 によって実現されfoldrます。

アキュムレータには左から右への情報の流れが必要です。これは通常、 を使用して実現されますが、これはfoldl厳密なリスト消費を意味します。

解決策は使用することscanlです：

--- mapAccumL :: (acc -> x -> (acc, y)) -> acc -> [x] -> (acc, [y])
--- scanl     :: (a   -> b -> a)        -> a   -> [b] -> [a]

takeWhileAcc p []     = []
takeWhileAcc p (x:xs) = map snd $ takeWhile (p.fst) 
                                $ scanl (\(acc,_) y-> (y:acc,y)) ([x],x) xs

filterAcc p []        = []
filterAcc p (x:xs)    = map snd $ filter (p.fst) 
                                $ scanl (\(acc,_) y-> (y:acc,y)) ([x],x) xs

別の可能性はuntil、またはを使用することmapAccumLです。後者は、累積された値を収集せず、最後のアキュムレータ値を渡すことを除いて、自然に適合します。

于 2012-11-21T14:32:34.713 に答える