时间戳

首页 > 解决方案 > 使用 seq 实现无限列表以提高 Haskell 中的时间复杂度

haskell - 使用 seq 实现无限列表以提高 Haskell 中的时间复杂度

问题描述

我不太明白 seq 究竟是如何工作的，以及如何使用 seq 来实现一个函数。所以作为一个练习，如果我想实现一个生成以数字 a 开头的列表的函数。

例如，我正在使用以下功能

countup n = n : countup (n+1)

并尝试将 [1, 2, 3, 4 ...] （从 1 开始，只需递增 1 并添加到列表中）作为无限惰性列表。我该怎么做？

更新：

我正在尝试使 (take k (countup 0)) 使用 O(1) 空间。这里，取函数如下：

take k (x:xl) = 
    if k==0
    then x
    else take (k-1) xl

标签： haskellseq

解决方案

countup n = n : countup (n+1)

列表的每个元素都创建为一个 thunk previousElement + 1。因此，如果您take是第 1000000 个或其他任何元素，那将是一个非常大的 thunk (...(n + 1)... + 1)，其中包含约 1000000 个暂停。即使:-cell 可以在生成后立即进行 GC（因此遍历列表脊本身需要O(1)空间），但元素本身会复制列表的结构，因此take k (countup n)仍然需要O(k)空间。

:如果评估单元格也会评估元素，我们希望它。我们可以做到这一点

countup n = seq n $ n : countup (n + 1)

现在，在评估 时seq n $ n : countup (n + 1)，seq将导致和都 被评估。评估后者什么都不做（它已经被评估了），评估前者执行任何 thunked 加法，以便s 永远不会建立。有了这个定义，占用空间（或者，真的）。nn : countup (n + 1)+ 1take k (countup n)O(1)O(log(n + k))

我们也可以将改进后的函数写为

countup !n = n : countup (n + 1)

推荐阅读