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"
[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\$