As a learning process I created 'reverse' function in a few different ways. Tinkering with 'reverse' made currying, folds and other stuff easier to understand. Almost natural!

I know these are trivial things for someone who had years of Haskell practice. Try to look at if from the perspective of real beginner. Level zero

Edit: New version is added in the new post.

Questions:

• I don't know names of each recursions. Regular recursion, tail, head, flat...?
• === should be the same but...
• ??? are things I don't know.
• I think my comments are correct, but I'm not 100% sure.
• did I get grouping ok?
• anything you want to add to this list, change,
• any suggestion how to improve this will be most welcome

• revA, revB, revC... are grouping of similar versions of reverse.

• numbers are sub-versions in a group:

• 1 original
• 2 where
• 3 let
• 4 case of
• ' currying, argument free

.
.
. Recursions, level zero

``````

{-  can't be argument free because we need (x:xs) to decompile arg
This is pattern match, pattern can not be curried!
recursion name ???  -}
revA1 [] = []   -- next one is faster, but fails on []  - dave4420
-- revA1 (x:[]) = [x]       -- === revA1 [x] = [x]
revA1 (x:xs) = revA1 xs ++ [x]

{- If we wrap pattern match in function, currying becomes possible: revA2'
help === revA1
recursion name ??? -}
revA2 xs = help xs      -- revA2' = help    -- curried help
where
help [] = []
help (b:bs) = help bs ++ [b]

revA3 xs = let
help [] = []
help (b:bs) = help bs ++ [b]
in help xs

revA3' = let
help [] = []
help (b:bs) = help bs ++ [b]
in help

revA4 y = case y of     -- blufox
[] -> []
(x:xs) -> revA4 xs ++ [x]

--

revB1 xs =  foldl (flip (:)) [] xs

revB1' =  foldl (flip (:)) []   -- foldl takes 3 args. supplying only two args rev2 becomes curried f waiting for third arg

revB2 xs = foldl step [] xs -- === revB2' = foldl step []
where step acc x = x:acc   -- === flip (:)

revB3 xs = let
step acc x = x:acc
in foldl step [] xs

revB3' = let
step acc x = x:acc
in foldl step []

--

--revC1 = foldl (flip (++)) []  -- doesn't work: [] ++ Char

revC1 xs = foldl (\acc x -> [x] ++ acc) [] xs
revC1' = foldl (\acc x -> [x] ++ acc) []

revC2 xs = foldl step [] xs     -- revC2' = foldl step []
where step acc x = [x] ++ acc  -- === (\acc x -> [x] ++ acc)

revC3 xs = let
step acc x = [x] ++ acc
in foldl step [] xs

revC3' = let
step acc x = [x] ++ acc
in foldl step []

--

revD1 xs = foldr step [] xs     -- revD1' = foldr step []
where step x acc = acc ++ [x]  -- === (\x acc -> acc ++ [x])

revD2 xs = foldr (\x acc -> acc ++ [x]) [] xs
revD2' = foldr (\x acc -> acc ++ [x]) []
--

-- don't know how to do it with only (:)
--revE1 xs = foldr step [] xs
-- where step x acc = ??? : ???

revF1 xs = help xs []   -- must have xs param!
where
help [] acc = acc     -- brake recursion
help (b:bs) acc = help bs (b:acc)

-- but if we use flip
revF1' = flip help []
where
help [] acc = acc     -- brake recursion
help (b:bs) acc = help bs (b:acc)

-- or flip params manualy
revF2 xs = help [] xs   -- === revF2' = help []
where
help acc [] = acc
help acc (b:bs) = help (b:acc) bs

revG1 xs = help [] xs   -- revG1' = help []
where
help acc [] = acc
help acc (b:bs) = help ([b]++acc) bs
``````

.
.
.

Test Functions:

``````

functions =
[revA1, revA2, revA3, revA3',
revB1, revB1', revB2, revB3, revB3',
revC1, revC1', revC2, revC3, revC3',
revD1, revD2, revD2',
revF1, revF2,
revG1
]

-- return [] of reversed param
tf1 [] param = []
tf1 (x:xs) param = (x param) : tf1 xs param

-- True if all functions return result equal as reverse param
tf2 xs param = foldl step True xs
where
p = reverse param
step acc x = (x param == p) && acc

--tfs :: [t -> t1] -> t -> IO [Double] -- ???
--tfs xs param = foldl' step [] xs
-- where step acc x = time2 (x param) : acc

tf1 functions "some string"
tf2 functions "some string"
``````
-
Let's try Code Review since you appear to have functional code already. –  Michael Myers Jun 10 '12 at 4:08
Because your A functions use `[x]` as the base case instead of `[]`, they result in a pattern match failure when given `[]` as input. You are worrying about speed, but do not forget about correctness. –  dave4420 Jun 10 '12 at 8:21
@dave4420: Ha, you are absolutely right :) –  CoR Jun 10 '12 at 10:10
@All: Should I edit original post to update what I've just learned or create new one? First solution is compact, second will preserve each change. –  CoR Jun 10 '12 at 10:24

migrated from stackoverflow.comJun 10 '12 at 4:08

This question came from our site for professional and enthusiast programmers.

I do not know much about performance of each versions because GHC has various optimizations built in, and I have not kept up to date with them. The best option for checking that is to benchmark the code in question.

``````import Test.HUnit

-- revA1 [] = []
-- is next one faster? - don't know but it is unlikely to be very much different.
revA1 [x] = [x]      -- I prefer this notation
revA1 (x:xs) = revA1 xs ++ [x] -- I didn't understand your comment here.
``````

You can also write it as

``````revA1' y = case y of
[] -> []
(x:xs) -> revA1' xs ++ [x]
``````

this is equivalent to the [x] in your example, but using :

``````revD1 xs = foldr step [] xs
where step x acc = acc ++ ((:) x [])
``````

can use flip here to eliminate xs param

``````revF1= flip help []
where
help [] acc = acc     -- brake recursion
help (b:bs) acc = help bs (b:acc)
``````

Use HUnit to write unit tests and run them

``````tests = TestList [
TestLabel "tA1" testA1,
TestLabel "tD1" testD1,
TestLabel "tF1" testF1
]

testA1 = TestCase \$ assertEqual "aA1" "olleH" (revA1 "Hello")
testD1 = TestCase \$ assertEqual "aD1" "olleH" (revD1 "Hello")
testF1 = TestCase \$ assertEqual "aF1" "olleH" (revF1 "Hello")

-- execute tt to run all tests.
tt = runTestTT tests
``````
-
I thought `revA1 (x:xs) = revA1 xs ++ [x]` can not be written as curried f because you need (x:xs) to decompile argument in `revA1 (x:xs) = ...` The truth is you can not curry pattern match. You need to wrap it in another f. I thought revA2 was just useless wrapper :D It turned out it was an eye opener :) –  CoR Jun 10 '12 at 10:38
Finally can give you +1 :) Reputation 16 :D –  CoR Jun 14 '12 at 10:09
:) thank you... –  rahul Jun 14 '12 at 14:11

I've been playing with this functions a bit more. Here's the latest version if anyone wants to tinker with it. Copy and paste code, load it in ghci and it play :)

``````{-
1 original
2 where
3 let
4 case of

' currying, argument free
t tail recursive
-}

{-  can't be argument free because we need (x:xs) to decompile arg
This is pattern match, pattern can not be curried!

recursion name ???  -}
revA1 [] = []   -- next one is faster, but fails on []  - dave4420
-- revA1 (x:[]) = [x]       -- === revA1 [x] = [x]
revA1 (x:xs) = revA1 xs ++ [x]

{- If we wrap pattern match in function, currying becomes possible: revA2'
help === revA1

recursion name ??? -}
revA2 xs = help xs      -- revA2' = help    -- curried help
where
help [] = []
help (b:bs) = help bs ++ [b]

revA3 xs = let
help [] = []
help (b:bs) = help bs ++ [b]
in help xs

revA3' = let
help [] = []
help (b:bs) = help bs ++ [b]
in help

-- looks like a pattern match in revA1      -  blufox
revA4 y = case y of
[] -> []
(x:xs) -> revA4 xs ++ [x]

---------------------------------------

revB1t xs =  foldl (flip (:)) [] xs

revB1t' =  foldl (flip (:)) []  -- foldl takes 3 args. supplying only two args rev2 becomes curried f waiting for third arg

revB2t xs = foldl step [] xs    -- === revB2' = foldl step []
where step acc x = x:acc  -- === flip (:)

revB3t xs = let
step acc x = x:acc
in foldl step [] xs

revB3t' = let
step acc x = x:acc
in foldl step []

---------------------------------------

--revC1 = foldl (flip (++)) []  -- doesn't work: [] ++ Char

revC1t xs = foldl (\acc x -> [x] ++ acc) [] xs
revC1t' = foldl (\acc x -> [x] ++ acc) []

revC2t xs = foldl step [] xs        -- revC2' = foldl step []
where step acc x = [x] ++ acc -- === (\acc x -> [x] ++ acc)

revC3t xs = let
step acc x = [x] ++ acc
in foldl step [] xs

revC3t' = let
step acc x = [x] ++ acc
in foldl step []

---------------------------------------

revD1 xs = foldr (\x acc -> acc ++ [x]) [] xs
revD1' = foldr (\x acc -> acc ++ [x]) []

revD2 xs = foldr step [] xs     -- revD2' = foldr step []
where step x acc = acc ++ [x] -- === (\x acc -> acc ++ [x])

revD3 xs = let
step x acc = acc ++ [x]   -- === (\x acc -> acc ++ [x])
in foldr step [] xs

revD3' = let
step x acc = acc ++ [x]
in foldr step []

---------------------------------------

{-

don't know how to do it with (:) but not ++
is it even possible?

revE1 xs = foldr step [] xs
where step x acc = ??? : ???

-}

---------------------------------------

revF1t xs = help xs []  -- must have xs param!
where
help [] acc = acc       -- brake recursion
help (b:bs) acc = help bs (b:acc)

-- but if we use flip
revF1t' = flip help []
where
help [] acc = acc
help (b:bs) acc = help bs (b:acc)

-- or flip params manualy
revF2t xs = help [] xs  -- === revF2' = help []
where
help acc [] = acc
help acc (b:bs) = help (b:acc) bs

revF3t xs = let
help acc [] = acc
help acc (b:bs) = help (b:acc) bs
in help [] xs

revF3t' = let
help acc [] = acc
help acc (b:bs) = help (b:acc) bs
in help []

revF24t xs = help xs []
where
help xs acc = case xs of
[] -> acc
(b:bs) -> help bs (b:acc) -- help (b:acc) bs -- hangs indefinetely

---------------------------------------

revG2t xs = help [] xs  -- revG2' = help []
where
help acc [] = acc
help acc (b:bs) = help ([b]++acc) bs

revG24t xs = help [] xs -- revG24' = help []
where
help acc xs = case xs of
[] -> acc
(b:bs) -> help ([b]++acc) bs

revG3t xs = let     -- regG3' = let ... in help []
help acc [] = acc
help acc (b:bs) = help ([b] ++ acc) bs
in help [] xs

revG34t xs = let        -- regG34' = let ... in help []
help acc xs = case xs of
[] -> acc
(b:bs) -> help ([b] ++ acc) bs
in help [] xs

---------------------------------------

-- list of functions
fs = [
revA1, revA2, revA3, revA3', revA4,
revB1t, revB1t', revB2t, revB3t, revB3t',
revC1t, revC1t', revC2t, revC3t, revC3t',
revD1, revD1', revD2, revD3, revD3',
revF1t, revF1t', revF2t, revF3t, revF3t', revF24t,
revG2t, revG24t, revG3t, revG34t
]
``````
-