Haskell (:) and (++) differences

Question

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

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.

Solution 1

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 x to 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:[].

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].

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):x is invalid. But reverse(xs)++[x] is valid.

Solution 2

: conses an element onto a list.

++ appends two lists.

The former has type

a -> [a] -> [a]

whereas the latter has type

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

Solution 3

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)

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:

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 (:)!!!

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 recursive and 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 -- ys in my example -- accumulates the current result and is passed along as a parameter. Because of the accumulator we are now able to use the cons operator to accumulate the result by appending the head of our initial list each time.

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] []

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.

Kind regards,

EDIT 1:

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

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

EDIT 2:

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

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

2.As dFeuer pointed out: The thunk representing the application of (:) to x and y is semantically identical to x:y but 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.

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

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.

Solution 4

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

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

will return 1 but

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

will return an error Variable not in scope x

To make it easy, think of cons like this

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

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

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

View more solutions