Haskell recursions, level zero

Question

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

How to read the code:

• 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"

Answer 1

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.

Here are my updates,

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