Haskell reverse function
Solution 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.
Solution 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
Admin
Updated on June 21, 2022Comments
-
Admin over 1 year
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