This talk is arguably the very best introduction to computational complexity I have ever come across. I highly recommend it.
Archive for December, 2012
Kissinger at 88 is writing brochures for Kissinger Associates. His last book on China is one such work written by the staff at Kissinger Associates. It is designed to curry favor with the Chinese authorities and nothing else.
I know him personally very well, but he is such a deceptive person; he’s a habitual liar and dissembler. Although I’ve spent a lot of time talking to him, I have no insight on him at all. His book ends with a paean to U.S.-Chinese friendship and how every other country has to fit in. I have to review it for the TLS, but I’ve been delaying it by weeks because I don’t know whether it is a case of senility or utter corruption.
I wonder if Kissinger would consider this a compliment. Anyone can be transparent, but obfuscation requires sophistication.
David Samuels, Q&A: Edward Luttwak, Tablet Magazine, Sept. 6, 2011.
Let us suppose that we are given a list of functions. We would like to compose the functions in this list (if they are composable, of course) in the order in which they are arranged in the list, i.e., we would like to create a higher-order function
compose such that
Here is one of many possible implementations in Haskell:
compose :: [(a -> a)] -> (a -> a) compose = foldr (.) (\x -> x)
where we use a right-fold to compute the composition. Note that the identity function is defined anonymously. What happens if we apply
compose to the empty list? We should obtain the identity function. Let us see if this is the case:
compose  = foldr (.) (\x -> x)  = (\x -> x)
Indeed, it is the case: if we apply
compose to the empty list, we obtain the identity function. What is the type of this identity function? We load the two-line script above into GHCi and experiment a bit:
*Main> let id = compose  *Main> :t id id :: a -> a *Main> map id [0..9] [0,1,2,3,4,5,6,7,8,9] *Main> map id ['a'..'z'] "abcdefghijklmnopqrstuvwxyz"
We thus obtain a polymorphic identity function that merely outputs its input, regardless of the type of the input. So far, so good. What happens if we apply
compose to a non-empty list? Here is some more equational reasoning:
compose [f0,f1,f2] = foldr (.) (\x -> x) [f0,f1,f2] = foldr (.) (\x -> x) (f0 : f1 : f2 : ) = f0 . (f1 . (f2 . (\x -> x)))
A couple of days ago, we saw how to compose a function with itself times. This is a special case of composing a list of functions, of course. Using function replicate, we can compose a function
f with itself times in the following manner:
compose (replicate n f) = foldr (.) (\x -> x) (replicate n f)
*Main> let f = (\n -> (n+1) `mod` 64) *Main> let h = compose (replicate 64 f) *Main> map h [0..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, 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]
In the next posts, we will do some interesting things with this