function nesting again

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

function nesting again

Zbigniew Stanasiuk
Hallo all,

I have two functions f and g of one arguments:

f :: (Num a) => [a] -> [a]
g :: (Num a) => [a] -> [a]

I can do composition (f .f .f.) [a] or (g .g .g.) [a] for a few repeated
functions.
And what about if I want to nest f, say, many many times?

The matter is more complicated (from my prespective :-) ) if I would like to
get  e.g.:
the composition (g .f .g. g.f .f) [a]
if t == 0 then f else g  
and having the list [1,0,1,1,0,0]  as a pattern to construct above composition.

How to make above, generally for arbitrary length ???

Reply | Threaded
Open this post in threaded view
|

function nesting again

Magnus Therning
On Thu, Jan 28, 2010 at 11:18, Zbigniew Stanasiuk <[hidden email]> wrote:

> Hallo all,
>
> I have two functions f and g of one arguments:
>
> f :: (Num a) => [a] -> [a]
> g :: (Num a) => [a] -> [a]
>
> I can do composition (f .f .f.) [a] or (g .g .g.) [a] for a few repeated
> functions.
> And what about if I want to nest f, say, many many times?
>
> The matter is more complicated (from my prespective :-) ) if I would like to
> get ?e.g.:
> the composition (g .f .g. g.f .f) [a]
> if t == 0 then f else g
> and having the list [1,0,1,1,0,0] ?as a pattern to construct above composition.
>
> How to make above, generally for arbitrary length ???

I believe what you want is a fold over a list of functions, where this
list has been created by mapping the if-statement above of a list of
Bools (I know you used 0,1 above, but True,False is a better choice in
my opinion).  So, in other words, something like this:

composeFnG l = foldl (.) id $ map chooseForG l
    where
        chooseForG b = if b then f else g

or a bit shorter

composeFnG = foldl (.) id . map (\ b -> if b then f else g)

/M

--
Magnus Therning                        (OpenPGP: 0xAB4DFBA4)
magnus?therning?org          Jabber: magnus?therning?org
http://therning.org/magnus         identi.ca|twitter: magthe
Reply | Threaded
Open this post in threaded view
|

function nesting again

Felipe Lessa
In reply to this post by Zbigniew Stanasiuk
On Thu, Jan 28, 2010 at 11:18:12AM +0000, Zbigniew Stanasiuk wrote:

> Hallo all,
>
> I have two functions f and g of one arguments:
>
> f :: (Num a) => [a] -> [a]
> g :: (Num a) => [a] -> [a]
>
> I can do composition (f .f .f.) [a] or (g .g .g.) [a] for a few repeated
> functions.
> And what about if I want to nest f, say, many many times?

Use this:

  iterate :: (t -> t) -> t -> [t]

For example

  Prelude> take 10 $ iterate (*2) 1
  [1,2,4,8,16,32,64,128,256,512]

That means that if you want to nest your function 'x' times, then
you just take the x-th element of the list.

  Prelude> let x = 10 in iterate (*2) 1 !! x
  1024

> The matter is more complicated (from my prespective :-) ) if I would like to
> get  e.g.:
> the composition (g .f .g. g.f .f) [a]
> if t == 0 then f else g
> and having the list [1,0,1,1,0,0]  as a pattern to construct above composition.
>
> How to make above, generally for arbitrary length ???

You could roll on your own functions, for example

  composition :: [t -> t] -> t -> t
  composition = foldr (.) id

  composition' :: [t -> t] -> [Int] -> t -> t
  composition' fs is = composition [fs !! i | i <- is]

Note that you would them as

  composition [g, f, g, g, f, f]

or

  composition' [f, g] [1, 0, 1, 1, 0, 0]

You could also write 'composition' as

  import Data.Monoid

  composition :: [t -> t] -> t -> t
  composition = appEndo . mconcat . map Endo

'map Endo' just puts everything in the Endo monoid, while
'appEndo' takes the result from the monoid.  In other words,
'composition' is the same as a concatenation in the Endo monoid.
It may be defined as:

  newtype Endo a = Endo {appEndo :: a -> a}

  instance Monoid (Endo a) where
    mempty                    = Endo id
    mappend (Endo f) (Endo g) = Endo (f.g)

Do you see the pattern? :)

HTH,

--
Felipe.
Reply | Threaded
Open this post in threaded view
|

Re: function nesting again

Zbigniew Stanasiuk
In reply to this post by Zbigniew Stanasiuk
Zbigniew Stanasiuk <zbigergofun <at> gmail.com> writes:

>
> Hallo all,
>
> I have two functions f and g of one arguments:
>
> f :: (Num a) => [a] -> [a]
> g :: (Num a) => [a] -> [a]
>
Big thanks to Magnus and Filipe for smart and practical solutions of my
problem. Up to now I didn't touch monoids although intuitively it seems
very elegant.

Best regards,
Zbig




Reply | Threaded
Open this post in threaded view
|

function nesting again

Daniel Fischer-4
In reply to this post by Magnus Therning
Am Donnerstag 28 Januar 2010 12:40:16 schrieb Magnus Therning:
> On Thu, Jan 28, 2010 at 11:18, Zbigniew Stanasiuk <[hidden email]>
wrote:

> > Hallo all,
> >
> > I have two functions f and g of one arguments:
> >
> > f :: (Num a) => [a] -> [a]
> > g :: (Num a) => [a] -> [a]
> >
> > I can do composition (f .f .f.) [a] or (g .g .g.) [a] for a few
> > repeated functions.
> > And what about if I want to nest f, say, many many times?
> >
> > The matter is more complicated (from my prespective :-) ) if I would
> > like to get ?e.g.:
> > the composition (g .f .g. g.f .f) [a]
> > if t == 0 then f else g
> > and having the list [1,0,1,1,0,0] ?as a pattern to construct above
> > composition.
> >
> > How to make above, generally for arbitrary length ???
>
> I believe what you want is a fold over a list of functions, where this
> list has been created by mapping the if-statement above of a list of
> Bools (I know you used 0,1 above, but True,False is a better choice in
> my opinion).  So, in other words, something like this:
>
> composeFnG l = foldl (.) id $ map chooseForG l
>     where
>         chooseForG b = if b then f else g
>
> or a bit shorter
>
> composeFnG = foldl (.) id . map (\ b -> if b then f else g)
>
> /M

Better use foldr, at least if f and (or) g are lazy.