4

我目前正在实施Project Euler 问题 40，并试图弄清楚如何从 Haskell 中的列表中获取多个项目，而无需重新开始列表。

目前，我有一个champernowne类型列表Integral a => [a]，它将返回一个无限的尚佩诺恩常数数字列表，然后我从这个序列中取出第一个、第十个等项并将它们相乘以获得答案。实际的代码是：

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]

只是为了澄清一下，第一段代码确实有效，但我正在努力改进我的实现以提高效率。

4

2 回答 2

7

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

但是，如果您想要的索引是按升序给出的，您可以通过计算相对偏移量并dropping 适当数量的项目以达到下一个所需索引，而无需从每个 fron 开始

-- 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

你的第二个表达式只是有一个小错误：使用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 回答