Re: [Haskell] Trying to get a Composite design pattern to work

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

Re: [Haskell] Trying to get a Composite design pattern to work

Jared Updike
(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
Reply | Threaded
Open this post in threaded view
|

Re: [Haskell] Trying to get a Composite design pattern to work

Asfand Yar Qazi-7
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
Reply | Threaded
Open this post in threaded view
|

Re: Re: [Haskell] Trying to get a Composite design pattern to work

Neil Mitchell
> 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
Reply | Threaded
Open this post in threaded view
|

Re: Re: [Haskell] Trying to get a Composite design pattern to work

haskell-2
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
Reply | Threaded
Open this post in threaded view
|

Re: Re: [Haskell] Trying to get a Composite design pattern to work

haskell-2
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