(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 ")-:" _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
On 3/13/06, Jared Updike <[hidden email]> wrote:
> > 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 _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
> 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 > [hidden email] > http://www.haskell.org/mailman/listinfo/haskell-cafe > Haskell-Cafe mailing list [hidden email] 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 _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
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 _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
Free forum by Nabble | Edit this page |