4

I'm currently working on an implementation of Project Euler problem 40 and am trying to figure out how to take multiple items from a list in Haskell without starting the list over.

Currently, I have a list champernowne of type Integral a => [a] which will return an infinite list of the digits of Champernowne's constant, then I take the first, tenth, etc. terms off of this sequence and multiply them to get the answer. The actual code for this is:

ans = (product . map (champernowne !!)) [0, 9, 99, 999, 9999, 99999]

The problem with this implementation is (I'm assuming) that Haskell will go through the list from the beginning of the sequence each time that it wants to get a new term. How can I make it so that haskell only goes through the sequence from elements 1 to 1 000 000 and then pulls the terms out of the middle? I've already tried scanl in hope that the lazy evaluation would aid me, but it did not:

ans = (product . head . scanl (flip drop) champernowne) [10, 90, 900, 9000, 90000]

Just to clarify, the first bit of code does work, but I'm trying to improve my implementation to be a bit more efficient.

4

2 に答える 2

7

この問題を解決する効率的な方法は、リストを作成せずに数字を計算することです。

ただし、目的のインデックスが昇順で指定されている場合は、相対オフセットを計算しdrop、適切な数の項目を ping して次の目的のインデックスに到達することにより、それぞれのフロントから開始することなくそれを取得できます。

-- supposes the list of indices in ascending order
indices :: [a] -> [Int] -> [a]
indices xs is = go xs offsets
  where
    offsets = zipWith (-) is (0:is)
    go ys (k:ks) = case drop k ys of
                     z:zs -> z : go (z:zs) ks
                     _    -> []
    go _ [] = []
于 2012-12-24T21:59:20.003 に答える
1

2 番目の式にわずかな誤りがあります。map head代わりに使用してくださいhead。

map (list !!) xs   -- [0, 9, 99, 999, 9999, 99999] ==

map head . tail . scanl (flip drop) list $ zipWith (-) xs (0:xs)
                   -- [9, 90, 900, 9000, 90000]
于 2012-12-29T13:17:23.657 に答える