Haskell - 从无限列表中获取多个值而不启动列表

Question

我正在研究Project Euler问题40的实现,并且我试图弄清楚如何从Haskell中的列表中取出多个项目而不启动列表.

目前,我有一个champernowne类型列表Integral a => [a],它将返回一个无限的Champernowne常数数字列表,然后我从这个序列中取出第一个,第十个等术语并乘以得到答案.实际代码是:

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

这个实现的问题是(我假设)每次想要获得一个新术语时,Haskell将从序列的开头经过列表.我怎样才能使haskell只经历从元素1到1 000 000的序列,然后将这些术语从中间拉出来？我已经尝试过scanl,希望懒惰的评估可以帮助我,但它没有:

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

只是为了澄清,第一部分代码确实有效,但我正在努力提高我的实现效率.

Answer 1

解决该问题的有效方法是在不构造列表的情况下计算数字.

但是,如果您按照升序给出了所需的索引,则可以通过计算相对偏移量并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 _ [] = []