## 5 Answers

Reset to default

# Trending sort

**Trending** sort is based off of the default sorting method — by highest score — but it boosts votes that have happened recently, helping to surface more up-to-date answers.

It falls back to sorting by highest score if no posts are trending.

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.

0

: conses an element onto a list.

++ appends two lists.

The former has type

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

whereas the latter has type

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

1

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

11

`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
```

you can change a little and get the right result.

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

63