Suppose we are given an endofunction . Let us introduce a new function , where , which we define recursively as follows
compose :: (a -> a) -> Integer -> (a -> a) compose f 0 = (\x -> x) compose f k = f . (compose f (k-1))
where the identity function is defined anonymously. If you happen to dislike anonymity in your functions, here is another implementation:
compose :: (a -> a) -> Integer -> (a -> a) compose f 0 = identity compose f k = f . (compose f (k-1)) identity :: a -> a identity x = x
compose f n = foldr (.) id (replicate n f)
id = (\x -> x). Beautiful, isn’t it? If this one-liner does not convert you to Haskell, then nothing will.
Let , and let function be defined by
This function corresponds to a cyclic shift. Therefore, we expect to have . Let and . We load the script above into GHCi, and voilà, we have the session:
*Main> let ns = [0..63] *Main> let f = (\n -> (n+1) `mod` 64) *Main> map f ns [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16, 17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32, 33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48, 49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,0]
So far, so good! Let us take a look at and :
*Main> let g = compose f 32 *Main> let h = compose f 64 *Main> map g ns [32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47, 48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63, 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15, 16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31] *Main> map h ns [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15, 16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31, 32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47, 48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63]
Indeed, as we expected, we have .
Everything in this post is elementary. But now that the elements are solid, we can dare to attempt more sophisticated things. Like what? Like composing lists of (distinct) functions. I am thinking of permutations. I am thinking of perfect shuffles.