Haskell inverse function

Question

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

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

Can someone explain what I'm doing wrong?

thanks

Answer 1

As groovy mentioned, Haskell's ranges are mostly incremental - that is, he has no idea how to create a shrinking list if you don't give him any hint. Take a look at the ghci session below:

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

So you can build something like this:

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

which checks in ghci as follows:

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

Take a look at the Unexpected result when rearranging the list and How can I write reverse foldr efficiently in Haskell? for other ideas about changing the list.

Answer 2

often it helps to come up with some kind of invariant and write down some conservation laws for it. Note here 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:[]) 

therefore if we define

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

we are configured. :) That is, to call rev ab concatenation of the inverse of a and b preserved when we transform the taking of the head element from a and adding it to b until a is empty and then it's just b . This can even be expressed using a higher order until function in accordance with the English description, since

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

We can also define now, for example. a revappend using the same internal function with a little tweaking as we call it:

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

Answer 3

This is my form for creating my own inverse function with recursion. this function is very convenient for defining auxiliary functions.

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