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
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.
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
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)
[length xs - 1, length xs - 2..0]work?reverseanother 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 ofxconsed with the listxsis ..."