Haskell reverse function

Question

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

Answer 1

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.

Answer 2

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