3

次のHaskellコードを記述して、n番目の要素が1..nを2進数として記述した場合の1の数であるリストを作成しました（ちなみに、オイラー391に関連しています）。

buildList :: a -> (a -> a) -> [a]
buildList start f = start : buildList (f start) f

differences :: [[Int]]
differences = buildList [0] (\x -> x ++ map (+1) x)

sequenceK' :: Int -> [Int]
sequenceK' n = tail $ scanl (+) 0 (last $ take n differences)

その結果、sequenceK' n2 ^（n-1）個の要素のリストが表示されます。

この質問には2つの部分があります。

head $ sequenceK' na）計算にかかる時間がnとともに増加するのはなぜですか？--ghcの怠惰のため、私は時間がほぼ一定のままであると予想します。

b）このリストの無限バージョンを定義して、渡されたパラメーターの値を気にすることなく、次のようなことができるようtakeにすることは可能ですか？takeWhilesequenceK'

4

1 に答える 1

5

a）呼び出しているのでlast $ take n differences、より多くの作業を行う必要がnあります。

b）はい、可能です。最も考えられていない解決策は、それぞれの特定の深さで見られる最も初期の要素を取得することです。

*Main> take 20 . map head . transpose $ differences
[0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3]

より良い解決策は、意味のあるビットのみを生成することです。これは、次の同等性を観察することで実行できます。

differences' = 1 : (differences' >>= \x -> [x, x+1])

実際には、おそらく推測できるように、これはわずかにずれています。

*Main> take 20 differences'
[1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3]

0しかし、それは正面にタックするだけで簡単に修正できます。

于 2012-09-04T01:32:53.453 に答える