Re: [Haskell] Trying to get a Composite design pattern to work
(Moved to haskell-cafe)
Actually, I'm trying to avoid library functions, so I can learn the language and the functional way of thinking. How would one implement the concatMap function?
The Haskell 98 report gives possible implementations of standard functions: http://haskell.org/onlinereport/standard-prelude.html e.g. foldr :: (a -> b -> b) -> b -> [a] -> b foldr f z [] = z foldr f z (x:xs) = f x (foldr f z xs) map :: (a -> b) -> [a] -> [b] map f [] = [] map f (x:xs) = f x : map f xs concat :: [[a]] -> [a] concat xss = foldr (++) [] xss concatMap :: (a -> [b]) -> [a] -> [b] concatMap f = concat . map f etc. The book Haskell School of Expression (by Paul Hudak) goes over using recursion as a control structure and then shows you how to replace your simple recursion patterns with library functions once you start to see these general patterns. As you start to understand the functional style of iterating over lists, you should begin to see when to use the library functions, and how it will save you time and be more simple and clear than using recursion directly for every function. If you want a place to start, I would challenge you to expand the concatMap definition above with the definitions of concat and map, and then plug in the definition of foldr and see if you can make your own concatMap function. Maybe that will help you understand things better. Hope that helps, Jared. -- http://www.updike.org/~jared/ reverse ")-:"
On 3/13/06, Jared Updike
If you want a place to start, I would challenge you to expand the concatMap definition above with the definitions of concat and map, and then plug in the definition of foldr and see if you can make your own concatMap function. Maybe that will help you understand things better.
MUHAHAHAHA I AM TEH HAXXELL GENEUS. Ahem... How's this? myhead :: [a] -> a myhead (x:xs) = x mytail :: [a] -> [a] mytail (x:xs) = xs mymap :: (a -> b) -> [a] -> [b] mymap fn [] = [] mymap fn (x:xs) = fn x : mymap fn xs myconcat :: [[a]] -> [a] myconcat (x:xs) = x ++ myconcat xs myconcat [] = [] -- For each a in [a], produce a [b] in another list, then concat the -- list. my_concat_map :: (a -> [b]) -> [a] -> [b] my_concat_map fn [] = [] my_concat_map fn xs = myconcat (mymap fn xs) stateslist :: StateNode a -> [a] stateslist(State x) = [x] stateslist (CompositeState xs) = my_concat_map stateslist xs
How's this?
What about ++, in Haskell thats just an ordinary function, yet you are using the library one in this case. The other thing is that the first definition of my_concat_map is entirely redundant, the second one handles both cases anyway. Also, for completeness, you might be interested to find that in some compilers the list is actually defined as: data [] a = [] | (:) a ([] a) This isn't legal Haskell 98, but nhc and Yhc both define a list similarly to this. Thanks Neil
myhead :: [a] -> a myhead (x:xs) = x
mytail :: [a] -> [a] mytail (x:xs) = xs
mymap :: (a -> b) -> [a] -> [b] mymap fn [] = [] mymap fn (x:xs) = fn x : mymap fn xs
myconcat :: [[a]] -> [a] myconcat (x:xs) = x ++ myconcat xs myconcat [] = []
-- For each a in [a], produce a [b] in another list, then concat the -- list. my_concat_map :: (a -> [b]) -> [a] -> [b] my_concat_map fn [] = [] my_concat_map fn xs = myconcat (mymap fn xs)
stateslist :: StateNode a -> [a] stateslist(State x) = [x] stateslist (CompositeState xs) = my_concat_map stateslist xs _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Neil Mitchell wrote:
How's this?
What about ++, in Haskell thats just an ordinary function, yet you are using the library one in this case.
(++) a b = foldr (:) b a or (++) = flip (foldr (:)) so concat = foldr (flip (foldr (:))) [] also map = (\f -> foldr ((:).f) []) thus concatMap = (\f -> (foldr (flip (foldr (:))) []) . (foldr ((:).f) [])) No recursive definitions in sight...all built with foldr -- Chris
Chris Kuklewicz wrote:
Neil Mitchell wrote:
How's this? What about ++, in Haskell thats just an ordinary function, yet you are using the library one in this case.
(++) a b = foldr (:) b a
or
(++) = flip (foldr (:))
so
concat = foldr (flip (foldr (:))) []
also
map = (\f -> foldr ((:).f) [])
thus
concatMap = (\f -> (foldr (flip (foldr (:))) []) . (foldr ((:).f) []))
No recursive definitions in sight...all built with foldr
Of course, I should only need one [] in the optimal definition: concatMap = (\f -> (foldr (flip (foldr (:)).f) [])) Which lambdabot can make "pointless" by eliminating the \f-> concatMap = flip foldr [] . (flip (foldr (:)) .) -- Chris
participants (4)
-
Asfand Yar Qazi -
Chris Kuklewicz -
Jared Updike -
Neil Mitchell