Saturday, May 29, 2010

On Dickens

He was almost certainly the best-known man in England in the middle of the nineteenth century, and certainly the most loved: his very personal hold on his readers extended from the most distinguished—Queen Victoria, say—to illiterate workers who clubbed together to buy the weekly or monthly parts in which his novels first appeared so that one marginally literate man could read them aloud to his fellows. And this popularity and influence carried to America, Germany, France, and Russia as well. There was universal sorrow when he died. “I never knew an author’s death to cause such general mourning,” wrote Longfellow. “It is no exaggeration to say that this whole country is stricken with grief.”


Source

Brooksley Born

is one of the few good-guys in Simon Johnson's excellent 13 Bankers about how anti-regulation ideology and financial industry power created the financial crisis.  Simultaneously standing up to Greenspan, Rubin, and Summers took great courage.

Friday, May 28, 2010

Links for 5/28/10

  1. Interview with Emanuel Derman, author of the excellent My Life as a Quant.
  2. Painful profile of a student with too much college debt.  I agree with the author that this is the partly the responsibility of financial aid departments.  I think the primary responsibility lies in the lack of a personal finance course taught at the high school level.  In my opinion it is scandalous that there is not such a course required at every high school in America.  It's as if the schools are preparing a polity ready to be duped by high, variable interest credit card and mortgage companies.
  3. Great artistic video about motivational psychology research.  Open source software is a key example.

Thursday, May 27, 2010

13 Bankers

I’m reading Simon Johnson and James Kwak’s 13 Bankers. It gives a really nice account of the history of banking in the US, highlighting the continual tension between bankers and presidents including Jefferson, Jackson, Theodore Roosevelt and Franklin Roosevelt.

Tuesday, May 25, 2010

Great mouse-free search engine

I've been using Duck Duck Go instead of Google for the last week.  I switched because I almost never need to use the mouse.  I highly recommend it.

http://duckduckgo.com/

Sunday, May 23, 2010

Review

A good trashing of Superfreakonomics.

Writing

A nice passage from Robert Frank's The Economic Naturalist's Field Guide:

Daniel Boorstin, the former Librarian of Congress, used to rise at five o'clock each morning and write for two hours before going into the office.  "I write to discover what I think," he explained.  "After all, the bars aren't open that early."  Boorstin's morning sessions were even more valuable than he realized.  Writing not only clarifies what you already know; it is an astonishingly effective way to learn something new.

Friday, May 21, 2010

Polymorphic recursion workaround in SML

I had something like the following formula type in SML.


type world = int
type param = string
type var = string * int

datatype t = Eq of world * world
           | And of t * t
           | Imp of t * t
           | All of param * t
           | Ex of var * t
           | Hole

There are formulas with holes, and I wanted to fill in a hole with another formula.
Since the fill function does the same thing for the binops and the quantifiers, I
lifted the logic out of the main function (binop and quant)

val fill : t * t -> t option =
 fn (inp, x) =>
   let
      val rec find : t -> t option =
       fn Hole => SOME x
       | And t12 => binop And t12
       | Imp t12 => binop Imp t12
       | All xt => quant All xt
       | Ex xt => quant Ex xt
       | Eq _ => NONE
      and binop: (t * t -> t) -> t * t -> t option =
       fn con => fn (t1, t2) =>
                 case find t1 of
                    SOME t => SOME(con(t, t2))
                  | NONE => Option.map (fn t => con(t1, t)) (find t2)
      and quant: ('a * t -> t) -> 'a * t -> t option =
       fn con => fn (x, t) => Option.map (fn t => con(x, t)) (find t)
   in
      find inp
   end

This didn't typecheck because quant was being called with 'a = var and also 'a = param.
Tom Murphy supplied the pretty workaround: quant gets an extra argument which is 
an abstraction of 'find'.  This breaks the mutual dependency, and shows that the function
is not really polymorphic-recursive.

val fill : t * t -> t option =
 fn (inp, x) =>
   let
      val quant : (t -> t option) -> ('a * t -> t) -> 'a * t -> t option =
       fn find => fn con => fn (x, t) => Option.map (fn t => con(x, t)) (find t)
      val rec find : t -> t option =
       fn Hole => SOME x
       | And t12 => binop And t12
       | Imp t12 => binop Imp t12
       | All xt => quant find All xt
       | Ex xt => quant find Ex xt
       | Eq _ => NONE
      and binop : (t * t -> t) -> t * t -> t option =
          fn con => fn (t1, t2) =>
                      case find t1 of
                         SOME t => SOME(con(t, t2))
                       | NONE => Option.map (fn t => con(t1, t)) (find t2)

   in
      find inp
   end


Nice phantom type example

A nice example of phantom types:  forcing lambda terms to be closed.  
Lifted from an email from Neek Krishnaswami.


type void   (* Empty type *)

type 'a debruijn =  (* Debruijn with nested datatypes *)
 | Var of 'a
 | App of 'a debruijn * 'a debruijn
 | Lam of ('a option) debruijn

let omega : void debruijn =  (* Typechecking ensures omega has no free vars *)
 App(Lam(App(Var None, Var None)), Lam(App(Var None, Var None)))



Note that a free variable, for instance, Var None : void option debruijn.  
Neel used the example to describe a polymorphic recursion workaround in ocaml.


(* Suppose we want a size function...

let rec size = function
 | Var _ -> 1
 | App(e,e') -> 1 + size e + size e'
 | Lam e -> 1 + size e

This won't typecheck, we need polymorphic recursion!
*)

(* Caml allows polymorphic record fields, so declare one with the
polymorphism
  we want in debruijn. *)

type 'b sizerec = {fn: 'a. ('a debruijn -> 'b)}

(* Now we can define a recursive function by going through this record *)

let size =
 let rec s =
   {fn = function
      | Var _ -> 1
      | App(e,e') -> 1 + s.fn e + s.fn e'
      | Lam e -> 1 + s.fn e}
 in
 s.fn

Thursday, May 06, 2010

Lunch with Knuth

I got to have lunch with Don Knuth and Frank and his other students today.  He talked about many things, most interesting to me were the organ and ZDDs.

Tuesday, May 04, 2010

The Economic Naturalist: II

Credit cards in grocery stores.

According to a number of recent articles, e.g.

www.nytimes.com/2009/07/16/business/16fees.html

credit card fees cost stores a large amout of money, thus raising costs to the consumer.  The fees seem to be roughly 2-3% of the cost of the purchase.  While I was waiting in line at Whole Foods yesterday, an economic naturalist question came to mind.  Why don't stores offer discounts for users who pay in cash?  If the discount was less than 3%, this would increase the merchant's profit.

The convenience of credit cards is undeniable.  Lowering the price for cash purchases would give customers an incentive to pay in cash, thus increasing the amount of physical currency the store had to deal with.   This would make the store a better target for robbery, and thus raise the price for armored transport and security guards.  However, I think the main reason high throughput stores like grocery stores don't want cash is that it would also increase the amount of time each person was at the grocery line.  (I'm assuming it takes longer to sort cash and make change than to wait for the credit card authorization.)  Any gain from the cash would most likely be lost by the extra time everyone stands in line.  The longer lines would mean the store would have to spend more on employees to keep lines open, or risk frustrating their customers.

Monday, May 03, 2010

Saturday, May 01, 2010