Haskell(:)和(++)的差异

Question

我很抱歉这样的问题.我不是太肯定的区别:,并++在Haskell运营商.

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

也

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

至于为我提出这个问题的反向功能,

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

以下为什么不工作？

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

给出类型错误.

Answer 1

的:操作者被称为"缺点"运算符和用于将头部元件预先考虑到的列表.所以[]是一个列表,x:[]并且前面是列表x的空列表[x].如果你这样做,y:[x]你最终会得到与之[y, x]相同的列表y:x:[].

该++运营商列表中连接符这需要两个列表作为操作数和他们"合并"成一个单独的列表.因此,如果您有列表[x]和列表,[y]那么您可以将它们连接起来:[x]++[y]to get [x, y].

请注意,:在++获取两个列表时采用元素和列表.

至于你的代码不起作用.

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

反向函数评估为列表.由于:运算符不将列表作为其第一个参数,reverse(xs):x因此无效.但是reverse(xs)++[x]有效.

Answer 2

:将一个元素包含在列表中.

++附加两个列表.

前者有类型

a -> [a] -> [a]

而后者有类型

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

Answer 3

与(++)连接

也许我正在考虑深入研究这一点,但据我所知,如果你尝试使用(++)例如连接列表:

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

(++)必须遍历完整的左侧列表.看一下(++)的代码会让它变得更加清晰.

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

因此,希望避免使用(++),因为每次调用时 reverse(xs)++[x]列表都会变大(或者根据视点而变小.无论如何,程序只需要在每次调用时遍历另一个列表)

例:

假设我通过连接实现了反向操作.

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

反转列表[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]

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

处理调用堆栈的一种方法是添加累加器.(并不总是可以只添加一个累加器.但是大多数处理的递归函数都是原始递归的,因此可以转换成尾递归函数.)

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

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

这里有一点需要注意.

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

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

亲切的问候,

编辑1:

尼斯是否会为那些感兴趣的人指出一些非常好的答案链接:

• 为什么差异列表比常规连接更有效？
• Haskell foldl'表现不佳(++)

编辑2:

好.感谢dFeuer和他的更正,我想我更了解Haskell.

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

2.As dFeuer指出,形实转换表示的应用(:),以x及y在语义上等同于x:y但需要更多的存储器.所以这对于cons运算符(和惰性构造函数)来说是特殊的,并且不需要以任何方式强制执行.

3.如果我使用非常相似的函数sumUp列表的整数,通过BangPatterns或seq函数进行严格的评估将防止堆栈如果使用得当而增长得太大.例如:

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

注意y前面的爆炸声.我在ghci中尝试了它,它需要更少的内存.