如何在 Haskell 中创建一个无限列表，其中新值消耗所有以前的值

Question

如果我像这样创建一个无限列表：

let t xs = xs ++ [sum(xs)]
let xs = [1,2] : map (t) xs
take 10 xs

我会得到这个结果：

[
[1,2],
[1,2,3],
[1,2,3,6],
[1,2,3,6,12],
[1,2,3,6,12,24],
[1,2,3,6,12,24,48],
[1,2,3,6,12,24,48,96],
[1,2,3,6,12,24,48,96,192],
[1,2,3,6,12,24,48,96,192,384],
[1,2,3,6,12,24,48,96,192,384,768]
]

这与我想要做的非常接近。

当前代码使用上一个值来定义下一个。但是，我想知道一些方法来制作一个无限列表，而不是一个列表列表，它使用所有以前的值来定义新的列表。

所以输出只会是

[1,2,3,6,12,24,48,96,192,384,768,1536,...]

我有第一个元素的定义[1]。

我有一个获取新元素的规则，将之前的所有元素相加。但是，我不能把它放在 Haskell 语法中来创建无限列表。

使用我当前的代码，我可以使用以下命令获取我需要的列表：

xs !! 10
> [1,2,3,6,12,24,48,96,192,384,768,1536]

但是，在我看来，有可能以更有效的方式做到这一点。

一些笔记

我知道，对于这个有意简化的特定示例，我们可以创建一个仅使用最后一个值来定义下一个值的函数。

但是，我正在搜索是否可以将所有先前的值读入无限列表定义。

如果我使用的示例造成了一些混乱，我很抱歉。

这里是另一个示例，无法使用仅读取最后一个值来修复：

isMultipleByList :: Integer -> [Integer] -> Bool
isMultipleByList _ [] = False
isMultipleByList v (x:xs) = if (mod v x == 0)
                        then True
                        else (isMultipleByList v xs)

nextNotMultipleLoop :: Integer -> Integer -> [Integer] -> Integer
nextNotMultipleLoop step v xs = if not (isMultipleByList v xs)
                        then v
                        else nextNotMultipleLoop step (v + step) xs

nextNotMultiple :: [Integer] -> Integer
nextNotMultiple xs  = if xs == [2]
                        then nextNotMultipleLoop 1 (maximum xs) xs
                        else nextNotMultipleLoop 2 (maximum xs) xs


addNextNotMultiple xs = xs ++ [nextNotMultiple xs] 
infinitePrimeList = [2] : map (addNextNotMultiple) infinitePrimeList

take 10 infinitePrimeList
[
[2,3],
[2,3,5],
[2,3,5,7],
[2,3,5,7,11],
[2,3,5,7,11,13],
[2,3,5,7,11,13,17],
[2,3,5,7,11,13,17,19],
[2,3,5,7,11,13,17,19,23],
[2,3,5,7,11,13,17,19,23,29],
[2,3,5,7,11,13,17,19,23,29,31]
]

infinitePrimeList !! 10
[2,3,5,7,11,13,17,19,23,29,31,37]

Answer 1

你可以这样定义它：

xs = 1:2:iterate (*2) 3

例如：

Prelude> take 12 xs
[1,2,3,6,12,24,48,96,192,384,768,1536]

Answer 2

unfoldr 具有很好的灵活性来适应各种“create-a-list-from-initial-conditions”问题，所以我认为值得一提。

对于这个特定的案例来说有点不太优雅，但展示了如何使用 unfoldr。

import Data.List

nextVal as = Just (s,as++[s]) 
  where s = sum as

initList = [1,2]

myList =initList ++ ( unfoldr nextVal initList)

main = putStrLn . show . (take 12) $ myList

屈服

[1,2,3,6,12,24,48,96,192,384,768,1536]

最后。

正如评论中所指出的，当使用 unfoldr. The way I've written it above, the code mimicks the code in the original question. However, this means that the accumulator is updated with as++[s], thus constructing a new list at every iteration. A quick run at https://repl.it/languages/haskell 时应该考虑一下，这表明它变得非常占用内存并且速度很慢。（4.5 秒访问 myList

中的第 2000 个元素

只需将累加器更新换成 a:as 即可将速度提高 7 倍。由于相同的列表可以在每一步中重复用作累加器，因此速度更快。但是，累加器列表现在是相反的，因此需要稍微考虑一下。在谓词函数 sum 的情况下，这没有区别，但如果列表的顺序很重要，则必须多考虑一点。

Answer 3

你可以这样想：

您想创建一个列表（称它们为 a），该列表开始于 [1,2]:

a = [1,2] ++ ???

... 并有此属性：a 中的每个下一个元素都是 a 中所有先前元素的总和。所以你可以写

scanl1 (+) a

并得到一个新列表，其中索引为 n 的任何元素都是列表 a 的第 n 个元素的总和。所以，它是[1, 3, 6 ...]。你所需要的只是获取所有元素而不是 first:

tail (scanl1 (+) a)

因此，您可以将 a 定义为：

a = [1,2] ++ tail (scanl1 (+) a)

这种思路你可以通过它的元素应用到定义列表的其他类似问题中。

Answer 4

如果我们已经有了最终结果，计算给定元素的先前元素列表将很容易，只需简单应用 inits 函数即可。

假设我们已经最终结果xs，并用它来计算xs本身：

import Data.List (inits)

main :: IO ()
main = do    
    let is = drop 2 $ inits xs
        xs = 1 : 2 : map sum is
    print $ take 10 xs

这会生成列表

[1,2,3,6,12,24,48,96,192,384]

(注意：这比SergeyKuz1001的解决方案效率低，因为总和每次都是re-calculated。)

Answer 5

这是我的看法。我尽量不创建 O(n) 个额外列表。

explode ∷ Integral i ⇒ (i ->[a] -> a) -> [a] -> [a]
explode fn init = as where
                     as = init ++ [fn i as | i <- [l, l+1..]]
                     l = genericLength init

这个便利函数确实创建了额外的列表（take）。希望它们可以被编译器优化掉。

explode' f = explode (\x as -> f $ take x as)

使用示例：

myList = explode' sum [1,2]

sum' 0 xs = 0
sum' n (x:xs) = x + sum' (n-1) xs
myList2 = explode sum' [1,2]

在我的测试中，这两个函数之间的性能差异很小。 explode' 通常稍微好一些。

Answer 6

from @LudvigH 非常漂亮和清晰。但是，它并没有更快。

我仍在研究基准测试以比较其他选项。

目前，这是我能找到的最佳解决方案：

-------------------------------------------------------------------------------------
-- # infinite sum of the previous using fuse
-------------------------------------------------------------------------------------

recursiveSum xs = [nextValue] ++ (recursiveSum (nextList)) where
      nextValue = sum(xs)
      nextList = xs ++ [nextValue]

initialSumValues = [1]
infiniteSumFuse =  initialSumValues  ++ recursiveSum initialSumValues

-------------------------------------------------------------------------------------
-- # infinite prime list using fuse
-------------------------------------------------------------------------------------

-- calculate the current value based in the current list
-- call the same function with the new combined value
recursivePrimeList xs = [nextValue] ++ (recursivePrimeList (nextList)) where
      nextValue = nextNonMultiple(xs)
      nextList = xs ++ [nextValue]

initialPrimes = [2]
infiniteFusePrimeList =  initialPrimes ++ recursivePrimeList initialPrimes

这种方法速度很快，并且可以很好地利用许多内核。

也许有一些更快的解决方案，但我决定post分享我目前在这个主题上的进展。

Answer 7

一般来说，定义

xs = x1 : zipWith f xs (inits xs)

然后是xs == x1 : f x1 [] : f x2 [x1] : f x3 [x1, x2] : ....，依此类推

Here's 在计算无限素数列表的上下文中使用 inits 的一个示例，将它们配对为

ps = 2 : f p1 [p1] : f p2 [p1,p2] : f p3 [p1,p2,p3] : ...

（在primes5的定义里有）。

如何在 Haskell 中创建一个无限列表，其中新值消耗所有以前的值

How to create a Infinite List in Haskell where the new value consumes all the previous values

haskell

infinite