2

我试图围绕haskell如何实现无限列表......这是我的路障：

您有一个 type 列表A，并A实现了Ordtypeclass。您可以像这样描述一系列有序元素（例如，整数）：

[1..6]

这相当于...

Cons 1 (Cons 2 (Cons 3 (Cons 4 (Cons 5 (Cons 6 (Empty))))))

haskell 怎么知道如何构造一个无限列表？haskell 是否能够创建支持的任何数据类型的无限列表Ord？

4

3 回答 3

6

Haskell“创建”了无限列表，因为它在需要之前不会创建任何元素。例如，让我们看一下在 Haskell 中的扩展head [1..]和1在严格语言中的无限循环。

head [1..]

===                                 [expand `head`, literally 
                                     just inline the definition]
case [1..] of
  []        -> error "empty list"
  (x : xs)  -> x

===                                 [evaluate [1..] one step,
                                     check if it matches the case]
case 1:[2..] of
  []        -> error "empty list"
  (x : xs)  -> x

===                                 [it does!]

(1 : [2..]) -> 1

===                                 [fin]

1

[1..]请注意，与大多数从攻击定义而不是攻击开始的语言相比，这是相当落后的head。

您[x..]不能为Ordtypeclass 中的任何类型编写（这只能让我们说出两个事物是大于还是小于另一个），而是为Enumtypeclass 中的任何内容编写为[x..]转换为enumFrom xwhere enumFrom :: Enum a => a -> [a]。

于 2013-07-25T21:30:02.093 回答
4

摆脱句法含糖的[a..b]东西可能会更容易一些，考虑一下 Prelude 中的一个简单函数：

repeat :: a -> [a]
repeat x = x : repeat x

您现在应该忘记评估并开始以声明方式思考，即将上述内容视为数学中的一个函数，可以阅读：

"repeat x" 表示 "x" 与 "repeat x" 一致

是的，“懒惰的评估”就是我们所说的让我们表达这一点的东西，但理想情况下，我们真的很想忘记评估并考虑我们的代码意味着什么。在命令式编程中，您有义务始终考虑评估。

这或多或少是您的[1..]脱糖剂：

enumFrom n = n : enumFrom (succ n)

您可以在@tel 的回答中看到编译器是如何扩展它的。

于 2013-07-25T23:50:53.470 回答
0

对于任何具有面向对象背景的人来说，无限列表的概念应该很容易理解。

诀窍是不要将 Haskell 列表视为数组甚至链表，而是将其视为迭代器对象。迭代器对象是具有两个方法的对象，hasNext并且getNext.

通常，迭代器hasNext会False在有限次数的getNext调用后返回。如果您认为迭代器与“真实”集合（例如数组、哈希映射、文件等）相关联，那肯定是正确的。

但是没有什么本质上会迫使迭代器“有限”。你可以很容易地实现一个无限迭代器。在类似 Haskell 的伪代码中：

object Iterator where
  hasNext _ = True
  getNext = do
    state <- get
    put (state + 1)
    return state

如果你不知道这个迭代器实际上是如何实现的，仅仅通过观察它的行为你会认为它与一个无限的（或至少非常大的）集合相关联。但这只是一个返回连续数字的对象。

另一个类似的类比是 UNIX 中的特殊文件，例如/dev/zero或/dev/random. 如果它们与硬盘上的真实文件相关联，则磁盘必须是无限的。但它们不是——而是内核根据需要生成内容，您可以随心所欲地请求它。

Haskell 的惰性列表的工作方式与此完全相同，除了它们还“缓冲”所有生成的值，以便您可以重复检查它们而无需进行重复评估。

于 2013-07-25T23:39:25.417 回答