Sipser on P versus NP

On October 3, 2006 Michael Sipser was at Harvard to give the following lecture on the P versus NP problem:

This talk is arguably the very best introduction to computational complexity I have ever come across. I highly recommend it.

Luttwak on Kissinger

Edward Luttwak on Henry Kissinger:

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.

__________

Source:

David Samuels, Q&A: Edward Luttwak, Tablet Magazine, Sept. 6, 2011.

Function composition via folding

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)

as suggested by Reid Barton. Let us now repeat the experiment we did perform a couple of days ago, but using the new compose:

*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 compose.