如何在不进入无限循环的情况下修改 Haskell 列表？

Question

我正在 Haskell 中编写一段代码，其中有一行代码执行如下操作：

addElement :: [a] -> a -> [a]
addElement list elem = list ++ [elem]

我需要（或者至少，我认为如此）这样的函数，以便在我正在实现的图形数据结构的顶点列表中添加新顶点。现在，我可以按如下方式调用此函数

newlist = addElement oldlist elem

一切顺利。但是，如果我写

mylist = addElement mylist elem

然后在调用终止后尝试对 mylist 做任何事情（确实如此），我进入了一个无限循环，如果我理解正确的话，这是由于 Haskell 的惰性评估或排序（如果我做对了，mylist 会扩展到 addElement (addElement ... elem) elem？）。

这当然不利于我的特定实现，因为出于我的目的，我现在每次需要向列表添加元素时都必须创建新列表。那么如何制作一个按我想要的方式工作的元素添加函数呢？

Answer 1

首先mylist = addElement mylist elem是等式，不是赋值。它是 not 评估一次：因为 Haskell 是一种声明性语言，你 不能改变变量 ：一旦你给它一个值，它将始终具有该值。

您的等式将因此得出：

mylist = addElement mylist elem
       = addElement (addElement mylist elem) elem
       = addElement (... (addElement mylist elem) ...) elem

你明白了。

不过，您不需要每次都构建一个完整的新列表：您可以简单地使用(h:t) 追加到头部:

addElement :: [a] -> a -> [a]
addElement t h = (h:t)

这将在 O(1) 中构建一个 "new" 列表，将旧列表重新用作尾部。前面说过元素会加到最前面。

另一种解决问题的方法是使用差异列表。这里的列表表示为：

type DiffList a = a -> [a]

空列表是：

emptyDiffList :: DiffList a
emptyDiffList = \x -> x

在那种情况下，您 ground 差异列表：

groundDiffList :: DiffList a -> [a]
groundDiffList x = x []

您可以将元素添加到列表的末尾：

addElement :: DiffList a -> a -> DiffList a
addElement l el = \x -> l (el:x)

然而你总是需要为"new list"创建一个新变量：你不能突然给mylist另一个值（你可以当然使用递归，但在那种情况下，它们在技术上是两个不同的变量：caller 的 mylist 和 callee 的 mylist ).

How do I modify a Haskell list without entering an infinite loop?