From: MenTaLguY <mental@...>
Date: 2007-06-08T02:12:26+09:00
Subject: Re: [SOLUTION][QUIZ] FizzBuzz (#126) [solution #2]

On Thu, 7 Jun 2007 20:45:04 +0900, Brad Phelan <bradphelan@xtargets.com> wrote:
> Thanks for the pointers. I don't have too much time today to think about
> this ( public holiday and I'm going out in the sun ) but I know when
> I do I'll want to know the concept here behind lists.

Lists are linked lists made of pairs, as in Lisp.  Since we chose to represent true and false as two-argument functions which return their first or second argument, respectively, we can take advantage of this to describe a pair as a function which takes true or false as an argument to select an element of the pair.

Such a pair can be created by a function like:

 MAKE_PAIR = LAMBDA2 { |first, second| LAMBDA { |which| which[first][second] } }
 
And functions for extracting the first or second value from a pair constructed by MAKE_PAIR can be written like this:

 FIRST = LAMBDA { |pair| pair[TRUE_] }
 SECOND = LAMBDA { |pair| pair[FALSE_] }

My definitions for CONS, CAR, and CDR in fizzbuzz were a little more involved, because I also needed to be able to  represent an empty list (and test for it).  So, what I did is roughly equivalent to:

 NIL_ = MAKE_PAIR[nil][TRUE_]
 CONS = LAMBDA2 { |head, tail| MAKE_PAIR[MAKE_PAIR[head, tail]][FALSE_] }
 CAR = LAMBDA { |cell| FIRST[FIRST[cell]] }
 CDR = LAMBDA { |cell| SECOND[FIRST[cell]] }
 NULL_P = LAMBDA { |cell| SECOND[cell] }

A tagged data structure, basically, with a flag indicating whether a cell is a null list or not.

-mental