list Haskell (:) 和 (++) 区别

Haskell (:) and (++) differences

提问by DarthVader

I'm sorry for a question like this. I'm not too sure about the difference of the :and ++operator in Haskell.

对于这样的问题，我很抱歉。我不太确定Haskell 中:and++运算符的区别。

x:y:[] = [x,y]  

also

还

[x] ++ [y] = [x,y]

as for the reverse function which arose this question for me,

至于对我提出这个问题的反向函数，

reverse ::[a]->[a]
reverse [] = []
reverse (x:xs) = reverse(xs)++[x]

Why doesn't the following work?

为什么以下不起作用？

reversex ::[Int]->[Int]
reversex [] = []
reversex (x:xs) = reversex(xs):x:[]

giving a type error.

给出类型错误。

回答by Vincent Ramdhanie

The :operator is known as the "cons" operator and is used to prepend a head element to a list. So []is a list and x:[]is prepending xto the empty list making a the list [x]. If you then cons y:[x]you end up with the list [y, x]which is the same as y:x:[].

该:运算符称为“cons”运算符，用于将头元素添加到列表中。[]列表x:[]也是如此，并x在空列表之前添加列表[x]。如果你然后是缺点，y:[x]你最终[y, x]会得到与y:x:[].

The ++operator is the list concatenation operator which takes two lists as operands and "combine" them into a single list. So if you have the list [x]and the list [y]then you can concatenate them like this: [x]++[y]to get [x, y].

该++运营商列表中连接符这需要两个列表作为操作数和他们“合并”成一个单独的列表。所以如果你有列表[x]和列表，[y]那么你可以像这样连接它们：[x]++[y]得到[x, y]。

Notice that :takes an element and a list while ++takes two lists.

请注意，它:采用一个元素和一个列表，而++采用两个列表。

As for your code that does not work.

至于你的代码不起作用。

reversex ::[Int]->[Int]
reversex [] = []
reversex (x:xs) = reversex(xs):x:[]

The reverse function evaluates to a list. Since the :operator does not take a list as its first argument then reverse(xs):xis invalid. But reverse(xs)++[x]is valid.

reverse 函数计算结果为列表。由于:运算符不将列表作为其第一个参数，reverse(xs):x因此无效。但reverse(xs)++[x]有效。

回答by Brian

: conses an element onto a list.

: conses 一个元素到一个列表中。

++ appends two lists.

++ 附加两个列表。

The former has type

前者有类型

a -> [a] -> [a]

whereas the latter has type

而后者有类型

[a] -> [a] -> [a]

回答by Nima Mousavi

Concatenation with (++)

与 (++) 连接

Maybe I'm thinking to deep into this but, as far as I understand, if you try to concatenate lists using (++)for example:

也许我正在考虑深入研究这一点，但据我所知，如果您尝试使用(++)例如以下方法连接列表：

[1, 2, 3] ++ [4, 5]

(++)has to traverse the complete left list. Taking a look at the code of (++)makes it all the more clear.

(++)必须遍历完整的左列表。看看(++)的代码就更清楚了。

(++) :: [a] -> [a] -> [a]
(++) []     ys = ys
(++) (x:xs) ys = x : xs ++ ys

Thus, it would be desirable to avoid using (++), since with every call reverse(xs)++[x]the list is getting bigger (or smaller depending on the point of view. Anyways, the program simply has to traverse another list with every call)

因此，最好避免使用(++)，因为每次调用 reverse(xs)++[x]列表都会变大（或变小，取决于观点。无论如何，程序只需在每次调用时遍历另一个列表）

Example:

例子：

Lets say I implement reverse as proposed through concatenation.

假设我通过串联实现了反向建议。

reversex ::[Int]->[Int]
reversex [] = []
reversex (x:xs) = reversex(xs)++[x]

Reversing a list [1, 2, 3, 4] would look somewhat like this:

反转列表 [1, 2, 3, 4] 看起来有点像这样：

reversex [1, 2, 3, 4]
reversex [2, 3, 4]               ++ [1]
reversex [3, 4]           ++ [2] ++ [1]
reversex [4]       ++ [3] ++ [2] ++ [1]
reversex [] ++ [4] ++ [3] ++ [2] ++ [1]
         [] ++ [4] ++ [3] ++ [2] ++ [1]
         [4]       ++ [3] ++ [2] ++ [1]
         [4, 3]           ++ [2] ++ [1]
         [4, 3, 2]               ++ [1]
         [4, 3, 2, 1]

Tail Recursion using the cons operator (:)!!!

使用 cons 运算符 (:) 的尾递归！！！

One method to deal with call stacks is by adding an accumulator. (it's not always possible to just add an accumulator. But most of the recursive functions one deals with are primitive recursiveand can thus be transformed into tail recursive functions.)

处理调用堆栈的一种方法是添加累加器。（并不总是可以只添加一个累加器。但是处理的大多数递归函数都是原始递归，因此可以转换为尾递归函数。）

With the the help of the accumulator it is possible to make this example work, using the cons operator (:). The accumulator -- ysin my example -- accumulates the current result and is passed along as a parameter. Because of the accumulator we are now able to use the consoperator to accumulate the result by appending the head of our initial list each time.

在累加器的帮助下，可以使用 cons 运算符使这个示例工作(:)。累加器——ys在我的例子中——累加当前结果并作为参数传递。由于累加器，我们现在可以使用cons运算符通过每次附加初始列表的头部来累加结果。

reverse' :: (Ord a) => [a] -> [a] -> [a]
reverse' (x:xs) ys = reverse' xs (x:ys)
reverse' [] ys     = ys

There is one thing to note here.

这里有一点需要注意。

The accumulator is an extra argument. I don't know if Haskell provides default parameters, but in this case it would be nice, because you would always call this function with an empty list as the accumulator like so: reverse' [1, 2, 3, 4] []

累加器是一个额外的参数。我不知道 Haskell 是否提供默认参数，但在这种情况下它会很好，因为你总是会用一个空列表作为累加器调用这个函数，如下所示：reverse' [1, 2, 3, 4] []

There is plenty of literature about tail recursion and I'm sure there are a lot of similar questions on StackExchange / StackOverflow. Please correct me if you find any mistakes.

有很多关于尾递归的文献，我相信在StackExchange / StackOverflow上也有很多类似的问题 。如果您发现任何错误，请纠正我。

Kind regards,

亲切的问候，

EDIT 1:

编辑 1：

Will Ness pointed out some links to really good answers for those of you who are interested:

Will Ness 为感兴趣的人指出了一些非常好的答案的链接：

• Why are difference lists more efficient than regular concatenation?
• Haskell foldl' poor performance with (++)

• 为什么差异列表比常规串联更有效？
• Haskell foldl' 性能不佳（++）

EDIT 2:

编辑 2：

Ok. Thanks to dFeuer and his corrections I think I understand Haskell a little bit better.

好的。感谢 dFeuer 和他的更正，我想我对 Haskell 有了更好的了解。

1.The $!is beyond my understanding. In all my tests it seemed to make things worse.

1.$!这超出了我的理解。在我所有的测试中，它似乎让事情变得更糟。

2.As dFeuer pointed out: The thunk representing the application of (:)to xand yis semantically identical to x:ybut takes more memory. So this is special to the cons operator (and lazy constructors) and there is no need to force things in any way.

2.正如dFeuer所指出的：代表(:)tox和应用的thunk在y语义上是相同的，x:y但需要更多的内存。所以这对于 cons 运算符（和惰性构造函数）来说是特殊的，并且不需要以任何方式强制执行。

3.If I instead sumUp Integers of a list using a very similar function, strict evaluation through BangPatterns or the seqfunction will prevent the stack from growing too large if used appropriately. e.g.:

3.如果我改为使用非常相似的函数对列表的整数求和，通过 BangPatterns 或seq函数进行严格评估，如果使用得当，将防止堆栈增长过大。例如：

sumUp' :: (Num a, Ord a) => [a] -> a -> a
sumUp' (x:xs) !y = reverse' xs (x + y)
sumUp' [] y      = y

Notice the bang in front of y. I tried it out in ghci and it takes less memory.

注意 y 前面的 bang。我在 ghci 中尝试过，它占用的内存更少。

回答by Clite Tailor

constends to be a type constructor than an operator. the example here is :can be use in let..in..expresion but ++is not

cons往往是类型构造函数而不是运算符。这里的例子:可以在let..in..表达式中使用，但++不是

let x : xs = [1, 2, 3] in x -- known as type deconstructing

will return 1 but

将返回 1 但

let [x] ++ [y, z] = [1, 2, 3] in x

will return an error Variable not in scope x

会返回错误 Variable not in scope x

To make it easy, think of conslike this

为了方便起见，可以cons这样想

data List a = Cons a (List a) -- is equvalent with `data [a] = a:[a]`

https://en.wikibooks.org/wiki/Haskell/Other_data_structures

https://en.wikibooks.org/wiki/Haskell/Other_data_structures

Additionally, if you want to reverse an array using cons. Here is an example, the knowledge is taken from Prolog

此外，如果您想使用 cons 反转数组。这里举个例子，知识取自Prolog

import Data.Function

reversex1 [] = []
reversex1 arr = reversex arr []

reversex [] arr = arr
reversex (x:xs) ys = reversex xs (x:ys)

main = do
    reversex1 [1..10] & print

回答by Yan Ding

you can change a little and get the right result.

你可以稍微改变一下，得到正确的结果。

reversex ::[Int]->[Int] # comment this line
reversex [] = []
reversex (x:xs) = reversex(xs) ++ x : []