当前位置：文江博客话题详情

函数式编程：什么是“不正确列表”？

发布于 2024-08-15 13:53:33 字数 28 浏览 2 评论 0原文

有人可以解释一下什么是“不正确的列表”吗？

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

十雾 2024-08-22 13:53:33

我认为 @Vijay 的答案是迄今为止最好的答案，我只是打算对其进行 Erlangify。

Erlang 中的对（cons 单元）被写为 [Head|Tail]，nil 被写为 []。对于头部和尾部是什么没有任何限制，但如果您使用尾部链接更多 cons 单元，您将得到一个列表。如果最终的尾部是[]，那么您将得到一个正确的列表。列表有特殊的语法支持，正确的列表

[1|[2|[3|[]]]]

写为

[1,2,3]

，不正确的列表

[1|[2|[3|4]]]

写为，

[1,2,3|4]

这样您就可以看到区别。与正确/不正确的列表进行匹配相应地很容易。因此，用于正确列表的长度函数len：

len([_|T]) -> 1 + len(T);
len([]) -> 0.

我们在其中显式匹配终止[]。如果给定的列表不正确，则会产生错误。虽然返回列表最后一个尾部的函数 last_tail 也可以处理不正确的列表：

last_tail([_|T]) -> last_tail(T);
last_tail(Tail) -> Tail.                 %Will match any tail

请注意，构建列表或对其进行匹配，就像通常使用 [Head|Tail] 所做的那样 不检查尾部是否是列表，因此处理不正确的列表没有问题。尽管您可以用它们做一些很酷的事情，但很少需要不正确的列表。

I think @Vijay's answer is the best one so far and I just intend to Erlangify it.

Pairs (cons cells) in Erlang are written as [Head|Tail] and nil is written as []. There is no restriction as to what the head and tail are but if you use the tail to chain more cons cells you get a list. If the final tail is [] then you get a proper list. There is special syntactic support for lists in that the proper list

[1|[2|[3|[]]]]

is written as

[1,2,3]

and the improper list

[1|[2|[3|4]]]

is written as

[1,2,3|4]

so you can see the difference. Matching against proper/improper lists is correspondingly easy. So a length function len for proper lists:

len([_|T]) -> 1 + len(T);
len([]) -> 0.

where we explicitly match for the terminating []. If given an improper list this will generate an error. While the function last_tail which returns the last tail of a list can handle improper lists as well:

last_tail([_|T]) -> last_tail(T);
last_tail(Tail) -> Tail.                 %Will match any tail

Note that building a list, or matching against it, as you normally do with [Head|Tail] does not check if the tail is list so there is no problem in handling improper lists. There is seldom a need for improper lists, though you can do cool things with them.

回复收藏 0 原文

吐个泡泡 2024-08-22 13:53:33

我认为使用Scheme 更容易解释这一点。

列表是一个以空列表结尾的对链。换句话说，列表以 cdr 为 () 的对结尾。

(a . (b . (c . (d . (e . ()))))) 

;; same as

(a b c d e)

不以空列表结尾的对链称为不正确列表。请注意，不正确的列表不是列表。列表和点符号可以组合起来表示不正确的列表，如以下等效符号所示：

 (a b c . d)
 (a . (b . (c . d)))

导致构造不正确列表的常见错误的示例是：

scheme> (cons 1 (cons 2 3))
(1 2 . 3)

注意 (1 2 . 3) 中的点---这就像 (2 . 3) 中的点，表示一对的 cdr 指向 3，而不是另一对或 '()。也就是说，它是一个不正确的列表，而不仅仅是一个对的列表。它不符合列表的递归定义，因为当我们到达第二对时，它的 cdr 不是列表 - 它是一个整数。

cheme 打印出列表的第一部分，就好像它是一个普通的 cdr 链表一样，但是当它到达末尾时，它不能这样做，所以它使用了“点表示法”。

您通常不需要担心点表示法，因为您应该使用正常列表，而不是不正确的列表。但是，如果您在Scheme 打印出数据结构时看到意外的点，则很可能您使用了 cons 并为其提供了一个非列表作为其第二个参数 - 除了另一对或 () 之外的东西。

Scheme 提供了一个方便的过程来创建适当的列表，称为列表。 list 可以接受任意数量的参数，并按这些元素的顺序构造一个正确的列表。您不必记住提供空列表——list 会以这种方式自动终止列表。

Scheme>(list 1 2 3 4)
(1 2 3 4)

礼貌：方案简介

I think it's easier to explain this using Scheme.

A list is a chain of pairs that end with an empty list. In other words, a list ends with a pair whose cdr is ()

(a . (b . (c . (d . (e . ()))))) 

;; same as

(a b c d e)

A chain of pairs that doesn't end in the empty list is called an improper list. Note that an improper list is not a list. The list and dotted notations can be combined to represent improper lists, as the following equivalent notations show:

 (a b c . d)
 (a . (b . (c . d)))

An example of a usual mistake that leads to the construction of an improper list is:

scheme> (cons 1 (cons 2 3))
(1 2 . 3)

Notice the dot in (1 2 . 3)---that's like the dot in (2 . 3), saying that the cdr of a pair points to 3, not another pair or '(). That is, it's an improper list, not just a list of pairs. It doesn't fit the recursive definition of a list, because when we get to the second pair, its cdr isn't a list--it's an integer.

Scheme printed out the first part of the list as though it were a normal cdr-linked list, but when it got to the end, it couldn't do that, so it used "dot notation."

You generally shouldn't need to worry about dot notation, because you should use normal lists, not improper list. But if you see an unexpected dot when Scheme prints out a data structure, it's a good guess that you used cons and gave it a non-list as its second argument--something besides another pair or ().

Scheme provides a handy procedure that creates proper lists, called list. list can take any number of arguments, and constructs a proper list with those elements in that order. You don't have to remember to supply the empty list---list automatically terminates the list that way.

Scheme>(list 1 2 3 4)
(1 2 3 4)

Courtesy: An Introduction to Scheme

回复收藏 0 原文

东走西顾 2024-08-22 13:53:33

Erlang 中列表的定义在手册中给出 - 特别是第 2.10

节Erlang 对于不正确的列表，你真正需要了解的唯一一件事是如何避免它们，而做到这一点的方法非常简单 - 这一切都取决于你要构建列表的第一个“事物”。以下所有内容都会创建正确的列表：

A = [].
B = [term()].
C = [term(), term(), term()].

在所有这些情况下，语法确保有一个隐藏的“空”尾部与“[]”相匹配结束......

因此，从它们开始，以下操作都会产生一个正确的列表：

X = [term() | A].
Y = [term() | B].
Z = [term() | C].

它们都是将新头添加到正确列表的操作。

有用之处在于，您可以将 X、Y 或 Z 中的每一个输入到如下函数中：

func([], Acc)      -> Acc;
func([H | T], Acc) -> NewAcc = do_something(H),
                      func(T, [NewAcc | Acc]).

它们将遍历列表并当尾部的隐藏空列表只剩下时，终止顶部子句。

当您的基本列表制作不当时，就会出现问题，如下所示：

D = [term1() | term2()]. % term2() is any term except a list

此列表没有隐藏 > 空列表作为终端尾部，它有一个术语...

从这里开始向下是很重要的，正如 Robert Virding 在评论中指出的

那么你如何为它编写一个终端子句呢？

令人愤怒的是，无法通过检查来判断列表是否不正确...打印出该死的东西，它看起来不错...所以你最终创建了一个不正确的基本列表，在上面做了一些事情，将其传递，然后突然kabloowie你在距离错误所在几英里的地方发生了崩溃，你拉着你的头发尖叫。

但是您应该使用透析器为您嗅出这些小野兽。

道歉

在罗伯特的评论之后，我尝试打印出一个不正确的列表，你瞧，很明显：

(arrian@localhost)5>A = [1, 2, 3, 4].
[1,2,3,4]
(arrian@localhost)5> B = [1, 2, 3 | 4].
[1,2,3|4]
(arrian@localhost)6> io:format("A is ~p~nB is ~p~n", [A, B]).
A is [1,2,3,4]
B is [1,2,3|4]

我曾经花了一些时间寻找一个不正确的列表，并说服自己它是不可逆的，好吧Ah ken noo ！

The definition of a list in Erlang is given in the manual - specifically Section 2.10

In Erlang the only thing you really need to know about improper lists is how to avoid them, and the way to do that is very simple - it is all down to the first 'thing' that you are going to build your list on. The following all create proper lists:

A = [].
B = [term()].
C = [term(), term(), term()].

In all these cases the syntax ensures that there is a hidden 'empty' tail which matches to '[]' sort of at the end....

So from them the following operations all produce a proper list:

X = [term() | A].
Y = [term() | B].
Z = [term() | C].

They are all operations which add a new head to a proper list.

What makes is useful is that you can feed each of X, Y or Z into a function like:

func([], Acc)      -> Acc;
func([H | T], Acc) -> NewAcc = do_something(H),
                      func(T, [NewAcc | Acc]).

And they will rip through the list and terminate on the top clause when the hidden empty list at the tail is all that is left.

The problem comes when your base list has been improperly made, like so:

D = [term1() | term2()]. % term2() is any term except a list

This list doesn't have the hidden empty list as the terminal tail, it has a term...

From here on downwards is mince as Robert Virding pointed out in the comments

So how do you write a terminal clause for it?

What makes it infuriating is that there is no way to see if a list is improper by inspecting it... print the damn thing out it looks good... So you end up creating an improper base list, doing some stuff on it, passing it around, and then suddenly kabloowie you have a crash miles from where the error is and you pull your hair and scream and shout...

But you should be using the dialyzer to sniff these little beasts out for you.

Apologies

Following Robert's comment I tried printing out an improper list and, lo and behold, it is obvious:

(arrian@localhost)5>A = [1, 2, 3, 4].
[1,2,3,4]
(arrian@localhost)5> B = [1, 2, 3 | 4].
[1,2,3|4]
(arrian@localhost)6> io:format("A is ~p~nB is ~p~n", [A, B]).
A is [1,2,3,4]
B is [1,2,3|4]

I had spent some time hunting an improper list once and had convinced myself it was invsible, well Ah ken noo!

回复收藏 0 原文

战皆罪 2024-08-22 13:53:33

要了解什么是不正确列表，您必须首先了解正确列表的定义。

具体来说，列表的“巧妙发现”是，您可以仅使用具有固定数量元素的表单来表示列表，即：

;; a list is either 
;; - empty, or
;; - (cons v l), where v is a value and l is a list.

此“数据定义”（使用“如何设计程序”中的术语）具有各种类型
不错的属性。最好的一点是，如果我们在数据定义的每个“分支”上定义函数的行为或含义，我们就保证不会错过任何一个案例。更重要的是，像这样的结构通常会产生干净的递归解决方案。

经典的“长度”示例：

(define (length l)
  (cond [(empty? l) 0]
        [else (+ 1 (length (rest l))]))

当然，Haskell 中的一切都更漂亮：

length []    = 0
length (f:r) = 1 + length r

那么，这与不正确的列表有什么关系呢？

那么，不正确的列表会使用此数据定义：

;; an improper list is either
;; - a value, or
;; - (cons v l), where v is a value and l is an improper list

问题是此定义会导致歧义。特别是，第一种情况和第二种情况重叠。假设我这样为不正确的列表定义“长度”：

(define (length l)
  (cond [(cons? l) (+ 1 (length (rest l)))]
        [else 1]))

问题是我破坏了一个很好的属性，即如果我采用两个值并将它们放入不正确的列表中（cons ab），则结果的长度为二。要了解原因，假设我考虑值 (cons 3 4) 和 (cons 4 5)。结果是 (cons (cons 3 4) (cons 4 5))，它可以被解释为包含 (cons 3 4) 和 (cons 4 5) 的不正确列表，或者作为包含 (cons 3 4)、4 和 5 的不正确列表。

在具有更严格类型系统的语言中（例如 Haskell），“不正确列表”的概念没有多大意义;您可以将其解释为一种数据类型，其基本情况包含两个内容，这可能也不是您想要的。

To understand what an improper list is, you must first understand the definition of a proper list.

Specifically, the "neat discovery" of lists is that you can represent a list using only forms with a fixed number of elements, viz:

;; a list is either 
;; - empty, or
;; - (cons v l), where v is a value and l is a list.

This "data definition" (using the terms of How To Design Programs) has all kinds of
nice properties. One of the nicest is that if we define the behavior or meaning of a function on each "branch" of the data definition, we're guaranteed not to miss a case. More significantly, structures like this generally lead to nice clean recursive solutions.

The classic "length" example:

(define (length l)
  (cond [(empty? l) 0]
        [else (+ 1 (length (rest l))]))

Of course, everything's prettier in Haskell:

length []    = 0
length (f:r) = 1 + length r

So, what does this have to do with improper lists?

Well, an improper list uses this data definition, instead:

;; an improper list is either
;; - a value, or
;; - (cons v l), where v is a value and l is an improper list

The problem is that this definition leads to ambiguity. In particular, the first and second cases overlap. Suppose I define "length" for an improper list thusly:

(define (length l)
  (cond [(cons? l) (+ 1 (length (rest l)))]
        [else 1]))

The problem is that I've destroyed the nice property that if I take two values and put them into an improper list with (cons a b), the result has length two. To see why, suppose I consider the values (cons 3 4) and (cons 4 5). The result is (cons (cons 3 4) (cons 4 5)), which may be interpreted either as the improper list containing (cons 3 4) and (cons 4 5), or as the improper list containing (cons 3 4), 4, and 5.

In a language with a more restrictive type system (e.g. Haskell), the notion of an "improper list" doesn't make quite as much sense; you could interpret it as a datatype whose base case has two things in it, which is probably not what you want, either.

回复收藏 0 原文

清晰传感 2024-08-22 13:53:33

我认为它可能指的是 LISP 中的“点对”，例如一个列表，其最终 cons 单元有一个原子，而不是 cdr 中对另一个 cons 单元或 NIL 的引用。

编辑

维基百科建议循环列表也被视为不当。请参阅

http://en.wikipedia.org/wiki/Lisp_(programming_language)

并搜索“不正确”并检查脚注。

回复收藏 0 原文

与君绝 2024-08-22 13:53:33

我想说，不正确列表的含义是列表的递归处理将与典型的终止条件不匹配。

例如，假设您在 Erlang 中对不正确的列表调用以下 sum：

sum([H|T]) -> H + sum(T);
sum([]) -> 0.

那么它将引发异常，因为最后一个尾部不是空列表，而是一个原子。

I would say the implication of an improper list is that a recursive treatment of the list will not match the typical termination condition.

For example, say you call the following sum, in Erlang, on an improper list:

sum([H|T]) -> H + sum(T);
sum([]) -> 0.

Then it will raise an exception since the last tail is not the empty list, but an atom.

回复收藏 0 原文

离笑几人歌 2024-08-22 13:53:33

在 Common Lisp 中，不正确的列表被定义为：

具有非 NIL 终止“原子”的点分列表。

示例

  (a b c d . f)

或

循环列表

示例

  #1=(1 2 3 . #1#)

In Common Lisp improper lists are defined as:

dotted lists that have a non-NIL terminating 'atom'.

Example

  (a b c d . f)

circular lists

Example

  #1=(1 2 3 . #1#)

回复收藏 0 原文

烙印 2024-08-22 13:53:33

列表由单元组成，每个单元由两个指针组成。第一个指向数据元素，第二个指向下一个单元格，或者在列表末尾为零。

如果第二个不指向单元格（或为零），则该列表不正确。函数式语言很可能允许您构建单元格，因此您应该能够生成不正确的列表。

在 Erlang 中（也可能在其他 FP 语言中），您可以通过将 2 元组存储为不正确的列表来节省一些内存：

2> erts_debug:flat_size({1,2}).
3
3> erts_debug:flat_size([1|2]).
2

A list is made up of cells, each cell consisting of two pointers. First one pointing to the data element, second one to the next cell, or nil at the end of the list.

If the second one does not point to a cell (or nil), the list is improper. Functional languages will most probably allow you to construct cells, so you should be able to generate improper lists.

In Erlang (and probably in other FP languages as well) you can save some memory by storing your 2-tuples as improper lists:

2> erts_debug:flat_size({1,2}).
3
3> erts_debug:flat_size([1|2]).
2

回复收藏 0 原文

扬花落满肩 2024-08-22 13:53:33

在erlang中，真正的列表是单链表。不正确的列表是最后一个节点不是真正的列表节点的单链表。

正确的列表

[1, 2, 3] 就像

不正确的列表

[1, 2 | 3] 就像

回复收藏 0 原文

对岸观火 2024-08-22 13:53:33

在 Erlang 中，一个正确的列表是 [H|T] 的列表。

H 是列表的头部，T 是列表的其余部分作为另一个列表。

不正确的列表不符合此定义。

回复收藏 0 原文

~没有更多了~

关于作者

北陌

暂无简介

0 文章

0 评论

23 人气

关注发私信

友情链接

文江博客

函数式编程：什么是“不正确列表”？

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

评论（10）

从这里开始向下是很重要的，正如 Robert Virding 在评论中指出的

道歉

From here on downwards is mince as Robert Virding pointed out in the comments

Apologies

正确的列表

不正确的列表

A proper list

An improper list

关于作者

相关话题

热门标签

推荐作者

謌踐踏愛綪

开始看清了

高速公鹿

alipaysp_PLnULTzf66

热情消退

白色月光

友情链接

函数式编程：什么是“不正确列表”？

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

评论（10）

从这里开始向下是很重要的，正如 Robert Virding 在评论中指出的

道歉

From here on downwards is mince as Robert Virding pointed out in the comments

Apologies

正确的列表

不正确的列表

A proper list

An improper list

关于作者

相关话题

热门标签

推荐作者

謌踐踏愛綪

开始看清了

高速公鹿

alipaysp_PLnULTzf66

热情消退

白色月光

友情链接

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。