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

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