3
\$\begingroup\$

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"
\$\endgroup\$
4
  • \$\begingroup\$ Let's try Code Review since you appear to have functional code already. \$\endgroup\$ – Michael Myers Jun 10 '12 at 4:08
  • \$\begingroup\$ 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. \$\endgroup\$ – dave4420 Jun 10 '12 at 8:21
  • \$\begingroup\$ @dave4420: Ha, you are absolutely right :) \$\endgroup\$ – CoR Jun 10 '12 at 10:10
  • \$\begingroup\$ @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. \$\endgroup\$ – CoR Jun 10 '12 at 10:24
1
\$\begingroup\$

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 
\$\endgroup\$
1
  • \$\begingroup\$ 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 :) \$\endgroup\$ – CoR Jun 10 '12 at 10:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.