練習として、私はruler
価値を定義しようとしています
ruler :: (Num a, Enum a) => [a]
これは定規機能に対応する
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2...
ここで、n
リストの 番目の要素 (最初の要素が に対応すると仮定n=1
) は、 を均等に割り切れる 2 の最大の累乗です。これをさらに面白くするために、割り切れるかどうかのテストを一切行わずにn
実装しようとしています。ruler
ヘルパー関数の使用
interleave :: [a] -> [a] -> [a]
これは、与えられた 2 つのリストの要素を単純に交互に並べるだけですが、私はこれを思いつきました - しかし残念ながら、これは機能しません:
interleave :: [a] -> [a] -> [a]
interleave (x:xs) (y:ys) = x : y : interleave xs ys
interleave _ _ = []
ruler :: (Num a, Enum a) => [a]
ruler = foldr1 interleave . map repeat $ [0..]
main :: IO ()
main = print (take 20 ruler)
プログラムは最終的にすべてのスタックスペースを使い果たします。
interleave
さて、奇妙なのは、定義を次のように調整すると、プログラムは問題なく動作するということです。
interleave (x:xs) ys = x : head ys : interleave xs (tail ys)
つまり、2 番目の引数でパターン マッチングを使用しなくなりました。ここでと を使用するhead
と終了するのはなぜでしょうか。結局のところ、パターン マッチングはむしろ防御的です (リスト スパインの最初の要素のみを評価する、そうではありませんか)。tail
ruler
ベストアンサー1
foldr
厳密な組み合わせ関数を無限リストに適用しています。
最小限の例に要約すると、この動作はここで確認できます。
*Main> :t const
const :: a -> b -> a
*Main> :t flip seq
flip seq :: c -> a -> c
*Main> foldr1 const [0..]
0
*Main> foldr1 (flip seq) [0..]
^CInterrupted.
修正方法は、他の回答で説明されているように、interleave
遅延することです。
より具体的には、次のようになります。まず、 を解決しfoldr1
、:
外側のリストのそれぞれを に置き換えますinterleave
。
foldr1 interleave [[0..], [1...], ...]
= interleave [0...] (interleave [1...] (...))
処理を進めるために、最初のinterleave
処理では最初の値を生成する前に 2 番目の引数を評価する必要があります。しかし、その後 2 番目の処理では 2 番目の引数を評価する必要があり、これが繰り返されます。
の遅延定義ではinterleave
、2番目の引数を評価する前に最初の値が生成されます。特に、interleave [1...] (...)
は と評価されます1 : ...
(これにより、最初のinterleave
引数が進むようになります)。前にさらに下にあるものを評価します。