Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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"
share|improve this question

migrated from stackoverflow.com Jun 10 '12 at 4:08

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

    
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

2 Answers 2

up vote 1 down vote accepted

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 
share|improve this answer
    
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
  ]
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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