首页 文章

如何在Haskell中获取无限列表的最后一项与有限列表连接？

提问于
浏览 次
2

在Haskell中，如何有效地获取与有限列表连接的无限列表的最后一项（？）？

last 不起作用，它显然是从头部迭代，所以以下永远不会完成：

-- let's have a list of all natural numbers,
-- with zero appended
arr = [1..] ++ [0]
-- it was fast! now get the last item, should be easy
res = last arr

EDIT ：我想知道Haskell的内部表示是什么 [1..] ++ [0] ，它最初是"totally unevaluated"？如果它将 internally 表示为两个（未评估的）列表"sequence"， last 函数可以立即获取最后一项的最后一项 .

haskell

3 回答

  • 1

    无论追加操作 ++ 的内部表示是什么，它都必须符合语言定义 .

    Haskell 2010 Language Report specifies：

    （）:: [a] - > [a] - > [a]追加两个列表，即[x1，...，xm] [y1，...，yn] == [x1，... ，xm，y1，...，yn]
    [x1，...，xm] [y1，...] == [x1，...，xm，y1，...]
    如果第一个列表不是有限的，则结果是第一个列表 .

    是的，您可以尝试以不同的方式定义它，就像内存中持有其参数列表的一些真实对象，以特定方式响应不同的请求，如 head 或 last ，旨在获得法律

    last (xs ++ ys) == last ys

    持有但那不是Haskell .

    回复于
  • 5

    对于任何表达式，您通常不能找到“Haskell的内部表示” . Haskell标准没有定义内部表示这样的东西;这取决于编译器选择一个 .

    在一个天真的实现中， [1..] ++ [0] 肯定会被表示为指向两个不同列表的thunk . 但是，无论您弹出多少元素，您都将从第一个无限列表中获取（标准确实保证） . 所以编译器完全可以完全自由地优化 ++ [0] ，因为它可以证明对结果没有任何影响 .

    如果您确实需要存储多个可能无限长度的列表并访问其中多个列表的头部，那么请将其显式化！例如，只使用嵌套列表 [[1..], [0]] .

    回复于
  • 4

    Haskell中的列表是左偏的，所以为了获得列表的最后一个元素，你必须遍历整个脊椎，但lists defined as free monoids是无偏见的，因此

    last $ fromList [1..] `append` fromList [0]

    计算到 0 . 但是这样的清单有自己的problems .

    回复于

相关问题