Reversing a string (or list) recursively

0
votes

I'm trying to write a function in haskell that reverses lists recursively. I wrote a helper function that takes the original list and an empty list then transfers elements from the first one to the other in a LIFO pattern.

Here's what I have:

myreverse :: [a] -> [a]
myreverse list = myflip list []

myflip :: [a] -> [a] -> [a]
myflip list1 newList
    | null list1        = newList
    | otherwise         = myflip (tail list1) ((head list1) : newList)

I know there's a built-in function that does it for me but the requirement is that I only use head, tail, elem and null (No pattern matching either). So my question is: is there a better solution where I only have one function, myreverse, that consumes only one list? (That meets the requirements above, of course)

Thanks!

5
haskell
Yep. And what I have will get me a full mark. I just want to know if there's a more elegant way to do it, given the above requirements. – Sadiq
You are also using (:), but it's not on the list of allowed functions ;-) – pat
Yeah, there's a lot of ways to do it but the constraints make it harder to come up with a nice function. :) – Sadiq
It is not solvable, because none of tail, elem, head and null result in a list that is of same type and at least as long as one of the arguments. But the result must be a list of same type and with same length as the argument. Q.E.D. – Ingo
@sth (:) is a data constructor, not a type constructor. Its type is (:) :: a -> [a] -> [a], so it is logically a function due to its type containing at least one arrow. The wikipedia page on algebraic data types describes a data constructor as being somewhat similar to a function, but then in the next sentence says that it is logically a function. Of course, if we want to have any hope of solving the problem, we have to allow its use! – pat

5 Answers

7
votes

You can try reversing a list using foldl like so:

reverse' :: [a] -> [a]  
reverse' = foldl (\acc x -> x : acc) []
2
votes

So for anyone who might be interested, this is what I ended up writing:

myreverse :: [a] -> [a]
myreverse list = myflip list []
    where myflip list newList = if null list then newList
                                else myflip (tail list) ((head list):newList)

Thanks everyone for your comments and suggestions.

2
votes

save this in reverse.hs file 

 reverseString :: [Char] -> [Char]
 reverseString [] = []
 reverseString (x:xs) = reverseString xs ++ [x]

then run reverseString "abc"

cba

0
votes

This function fulfills your requirements, but is horrible inefficient:

rev xs = if null xs then xs else rev (tail xs) ++ [head xs]

Your solution isn't bad at all. After using pattern matching and making myFlip a local function it wouldn't look ugly. And the technique of using a local function with an accumulator is very common (although not in such easy cases).

0
votes

Aside from the adjustments necessary to meet your additional requirements, your function is equivalent to the way reverse is implemented in GHC. Therefore I'd assume your function is pretty good the way it is.