CODEWITHSUNDEEP
haskell
Sadiq
Sadiq

Reputation: 2289

Reversing a string (or list) recursively

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!

Upvotes: 0

Views: 14047

Answers (5)

mykey
mykey

Reputation: 2273

save this in reverse.hs file 

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

then run reverseString "abc"

cba

Upvotes: 2

Sadiq
Sadiq

Reputation: 2289

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.

Upvotes: 2

sth
sth

Reputation: 229754

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.

Upvotes: 1

Landei
Landei

Reputation: 54584

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).

Upvotes: 0

Derek Kwok
Derek Kwok

Reputation: 13068

You can try reversing a list using foldl like so:

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

Upvotes: 7

Related Questions