函数式编程：什么是“不正确的列表”？
有人可以解释一下“不正确的清单”是什么吗？
注意 ：谢谢大家！ 所有你们摇滚！
我认为@维杰的答案是迄今为止最好的答案，我只是打算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
请注意，按照通常的方式构build列表或匹配， [Head|Tail]并不检查尾部是否列表，因此在处理不正确的列表时没有问题。 很less有需要不适当的名单，虽然你可以做他们很酷的事情。
我认为使用Scheme解释这个更容易。
列表是以空列表结尾的一对链。 换句话说，一个列表以cdr为（）的一对结束，
(a . (b . (c . (d . (e . ()))))) ;; same as (abcde)
没有在空列表中结束的一对链被称为不正确的列表。 请注意，不正确的列表不是一个列表。 列表和虚线符号可以组合来表示不正确的列表，如以下等同符号所示：
(abc . d) (a . (b . (c . d)))
导致build立不正确列表的常见错误的一个例子是：
scheme> (cons 1 (cons 2 3)) (1 2 . 3)
注意（1 2 3）中的点—就像（2.3）中的点一样，表示一对的cdr指向3，而不是另一对或'（）。 也就是说，这是一个不正确的列表，而不仅仅是一对列表。 它不适合列表的recursion定义，因为当我们到达第二对时，它的cdr不是一个列表 – 它是一个整数。
Scheme打印出列表的第一部分，好像它是一个正常的cdr-linked列表，但是到了最后，它不能这么做，所以它使用了“点符号”。
您通常不需要担心点符号，因为您应该使用正常列表，而不是不正确的列表。 但是当Scheme打印出一个数据结构时，如果你看到一个意外的点，那么猜测你使用了cons，并且给它一个非列表作为它的第二个参数 – 除了另一个对或（）之外的东西。
Scheme提供了一个方便的过程，可以创build名为list的正确列表 。 列表可以使用任意数量的参数，并按照这些顺序构造一个适当的列表。 你不必记得提供空列表—列表自动终止列表的方式。
Scheme>(list 1 2 3 4) (1 2 3 4)
礼貌： 介绍计划
Erlang中的列表定义在手册中给出 – 具体参见 2.10节
在Erlang中，你真正需要知道的关于不恰当列表的唯一方法就是如何避免这些列表，而实现这个目的的方法非常简单 – 这就是你将要build立列表的第一件事情。 以下全部创build正确的列表：
A = []. B = [term()]. C = [term(), term(), term()].
在所有这些情况下， 语法确保有一个隐藏的“空”尾部，与末尾的[[]' sorting相匹配….
所以从他们下面的操作都产生一个适当的列表：
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
这个列表没有 隐藏的空列表作为terminal尾部，它有一个术语…
罗伯特·维尔丁（RobertVerding）在评论中指出：
那么你怎么写一个terminal子句呢？
是什么让人愤怒的是， 没有办法通过检查来查看列表是否不正确…打印该死的东西，看起来不错…所以，最终你会创build一个不正确的基础列表，在它上面做一些事情，通过它周围，然后突然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]
我曾经花了一些时间去寻找一个不合适的名单，并且相信自己这是不可能的，那么啊 ！
要理解不正确的列表是什么，你必须首先理解一个正确列表的定义。
具体来说，列表的“简洁的发现”是，你可以只使用具有固定数量元素的表单来表示列表，即：
;; a list is either ;; - empty, or ;; - (cons vl), where v is a value and l is a list.
这个“数据定义”（使用如何devise程序的条款）具有各种不错的属性。 其中最好的一点是，如果我们在数据定义的每个“分支”上定义一个函数的行为或含义，我们保证不会错过一个例子。 更重要的是，像这样的结构通常会导致很好的清理recursion解决scheme。
经典的“长度”示例：
(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 vl), 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）中，结果就是长度二。 为了明白为什么，假设我考虑了价值观（利弊3）和（利弊4 5）。 结果是（cons（cons 3 4）（cons 4 5）），它可能被解释为包含（cons 3 4）和（cons 4 5）的错误列表， 或者包含（cons 3 4） ，4和5。
在具有更严格的types系统的语言（如Haskell）中，“不适当的列表”的概念并没有多less意义; 你可以把它解释为一个数据types，其基本情况有两件事情，这可能不是你想要的。
我想说一个不正确的列表的含义是，列表的recursion处理将不符合典型的终止条件。
例如，假设你在一个不正确的列表中调用了Erlang中的以下sum ：
sum([H|T]) -> H + sum(T); sum([]) -> 0.
那么它会引发一个exception，因为最后一个尾部不是空的列表，而是一个primefaces。
列表由单元组成，每个单元由两个指针组成。 第一个指向数据元素，第二个指向下一个单元，或者在列表的末尾为零。
如果第二个不指向一个单元格（或零），这个列表是不正确的。 函数式语言很可能会允许您构造单元格，所以您应该能够生成不正确的列表。
在Erlang中（也可能在其他FP语言中），可以通过将2元组存储为不正确的列表来节省一些内存：
2> erts_debug:flat_size({1,2}). 3 3> erts_debug:flat_size([1|2]). 2
我认为它可能是指LISP中的一个“虚线对”，例如最后一个cons cell有一个primefaces的列表，而不是cdr中另一个cons cell或NIL的引用。
编辑
维基百科build议，通告列表也算不当。 看到
http://en.wikipedia.org/wiki/Lisp_(programming_language）;
并search“不当”，并检查脚注。
在Common Lisp中， 不正确的列表被定义为：
- 带有非NIL终止“primefaces”的虚线列表 。
例
(abcd . f)
要么
- 通告清单
例
#1=(1 2 3 . #1#)
在Erlang中，正确的列表是[H|T] 。
H是列表的头， T是列表的其余部分作为另一个列表。
不正确的列表不符合这个定义。
