[Haskell-beginners] function nesting again
Felipe Lessa
felipe.lessa at gmail.com
Thu Jan 28 06:52:39 EST 2010
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.
More information about the Beginners
mailing list