Haskell reverse function

6
votes

Very new to Haskell, and trying to create my own reverse function. Wrote this here, but it always returns an empty list [] :

reverse' :: [a] -> [a]
reverse' xs = [xs !! k | k <- [((length xs) - 1)..0]]

Can anyone explain what I'm doing wrong?

Thanks

3
haskellfunctional-programming
does [length xs - 1, length xs - 2..0] work? – גלעד ברקן
If you're not comfortable with recursion yet, before looking at other implementations try defining reverse another way by filling in the following: reverse [] = ... ; reverse (x:xs) = ... and think of it as "the reverse of the empty list is ... and the reverse of x consed with the list xs is ..." – jberryman
Note that it's generally questionable to access lists by index. They are specifically designed so you can easily deconstruct them recursively, from the head element by element, but perform very badly when you request an element at arbitrary position. – leftaroundabout

3 Answers

12
votes

As groovy mentioned, Haskell ranges are mostly incremental - that is, it has no idea how to construct a decreasing list unless you give it some hint. Have a look at a ghci session below:

Prelude> [5..0]
[]
Prelude> [5,4..0]
[5,4,3,2,1,0]

So, you can construct something like this:

foo xs = [(length xs-1), (length xs -2)..0]
rev xs = [xs !! k| k <- foo xs]

which checks out in ghci like this:

Prelude> rev [1..5]
[5,4,3,2,1]

Have a look at Unexpected result while reversing a list and How can I write reverse by foldr efficiently in Haskell? for other ideas on reversing a list.

5
votes

oftentimes it helps to invent some invariant and write down some laws of preservation for it. Here notice that

reverse xs     = reverse xs ++ []
reverse (x:xs) = (reverse xs ++ [x]) ++ []
               = reverse xs ++ ([x] ++ [])
               = reverse xs ++ (x:[])
reverse (x:(y:xs)) =
               = reverse (y:xs) ++ (x:[])
               = reverse xs ++ (y:x:[])
......
reverse (x:(y:...:(z:[])...)) =
               = reverse [] ++ (z:...:y:x:[])

so if we define

reverse xs = rev xs []  where
  rev (x:xs) acc = rev xs (x:acc)
  rev []     acc = acc

we're set. :) I.e., for a call rev a b, the concatenation of reversed a and b is preserved under a transformation of taking a head element from a and prepending it to b, until a is empty and then it's just b. This can even be expressed with the use of higher-order function until following the English description, as 

{-# LANGUAGE TupleSections #-}
reverse = snd . until (null.fst) (\(a,b)-> (tail a,head a:b)) . (, [])

We can also define now e.g. an revappend function, using exactly the same internal function with a little tweak to how we call it:

revappend xs ys = rev xs ys  where
  rev (x:xs) acc = rev xs (x:acc)
  rev []     acc = acc
0
votes

That is my form to create my own reverse function with recursion. this function is very util for not define auxiliar functions.

list = [] reverse [x] = list ++ [x] reverse = list ++ [last l] ++ reverse (init l)