[racket] Little Schemer, lat?

Matthias, you write:

  all-true is the same as cannot-find-a-false-on-the-list.

Then I take an inverse:

  all-false is the same as cannot-find-a-true-on-the-list.

But we have (in Racket):

(and) -> #t
(or) -> #f

Something is wrong with the inversion. But what?

Happy new year to all, Jos

-----Original Message-----
From: users [mailto:users-bounces at racket-lang.org] On Behalf Of Matthias
Felleisen
Sent: 03 January 2015 03:12
To: Frank Weytjens
Cc: users Users
Subject: Re: [racket] Little Schemer, lat?


Frank, happy new year. It's good to hear from people like you because TLS is
for you. 

Now I'd like to say that I am unbelievably unhappy about Chapter 2 but I
could not convince Dan to change the book that much. Let's look at lists in
the "How to Design Programs" way, the TLS for adults if you so wish. Here is
the definition: 

A LAT is either
 -- the empty list
or
 -- a LAT l extended with one ATOM. 

And we don't care what an ATOM is. 

This definition is unusual because it refers to itself. You haven't seen
such definitions in your high school courses, and it's best to make sure
this definition generates some LATs (whatever those are). 

* Clearly one thing is a LAT.  T
- he empty list.

* Now suppose we take ATOM1 (whatever atoms are) and extend the empty list
with ATOM1. 
- What do we get? 

* Yes, we get a different LAT. 
- Should we give it a name? 

* Sure, what would you like to call it? 
- LAT1. 

* Great name. What do you think happens if we extend LAT1 with ATOM2? 
- Then we get LAT2, which is like LAT1 but extended with ATOM2. 

And so on. But the key is, we started by simply defining the empty list to
be a LAT. Note how we also don't need any "Scheme" or "Racket" things to
express the ideas. Plain English and an agreement to treat 'extend with' and
'the empty list" as special phrases.

Time to look the second aspect of your question. Here is a definition for
LOB: 

A LOB is either
 -- the empty list
or
 -- a LOB extended with one Boolean. 
A Boolean is either #t or #f. 

* Are these LOBs? 
  the empty list
  the empty list extended with #f
  the empty list extended with #f extended with #t
- Yes they are. 

* Are all Booleans on this list #t
   the empty list extended with #t extended with #t
- They sure are. 

* Are all Booleans on this list #t
   the empty list extended with #t
- Still. 

* Are all Booleans on this list #t
   the empty list
- It all depends on what "are" means. [Famous quote. Who said that?]

* How many options do we have? 
- Two: The answer is either true or false. 

* How do you define the function for answer 1 [true]
- Easy
(define (all-true?-1 lob)
  (cond
    [(null? lob) #t] ;; by definition, right? 
    [else (and (true? (car lob)) (all-true?-1 (cdr lob)))])) ;; <--- this is
now functions should be defined 

* What about answer 2 [false]? 
- Here is a start: 
(define (all-true?-2 lob)
  (cond
    [(null? lob) #f] ;; by definition, right? 
    [else ...]))

* This function works for the empty list but how about lists with one or two
or three ... Booleans? 
- For all those, all-true?-1 gives the correct answer. 
(define (all-true?-2 lob)
  (cond
    [(null? lob) #f] ;; by definition, right? 
    [else (all-true?-1 lob)]))

* How come? 
- Because all-true?-2 makes sure that all-true?-1 never sees the empty list.


* But doesn't all-true?-1 look for the empty list? 
- Yes, but only after it has seen at least one Boolean. 

* Which answer is simpler, elegant, satisfying? 
- The first one. It's a two-line function and it's easily explained. 

* So what is the better choice? 
- It's better to say that all Booleans on the empty list are true, even
though there aren't any. 

* Is this weird? 
- A little bit but it makes everything easy. 

* So let's use this convention from now on. 
- Good. 

That's one explanation for considering it correct to say that the empty list
contains only #t Booleans. Another one: 

  all-true is the same as cannot-find-a-false-on-the-list. 

Can you deal with this explanation? -- Matthias







On Jan 2, 2015, at 5:58 PM, Frank Weytjens wrote:

> Happy new year Racketeers,
> 
> The Little Schemer is my favorite book.
> I have a kind of Sisyphus relationship with it.
> In the preface they advice to not read it, in less then 3 times.
> The jokers! It's more then 3 years I read this book, from time to time.
> Hoping to get further and further, each time.
> I enjoy to start over and over, without completely understanding it.
> Like if: once it 's completely understood, there is no more interesting
stuff on earth. 
> This time i got stuck much earlier, then normal, extremely early.
>  
> (define lat?
>     (lambda (l)
>       (cond 
>             ((null? l) #t)
>             ((atom? (car l)) (lat? (cdr l)))
>             (else #f))))
> 
> An empty list is a list, but is it a lat ?
> If you give an empty list as argument to the lat?-function, the answer 
> is yes. But an atom must be a string of characters or numbers, or even 
> one character, or a combination of special characters as long as it is 
> not an ( or an ). The empty list contains no characters at all, so it 
> can not be a list of atoms. It would be OK, if you recur at least 
> once. But when you feed an empty list, this is not the case. Then the 
> answer of (null? l) should be #f
> 
> Rewriting the function that way, would never give #t as answer
> 
> (define lat?
>     (lambda (l)
>       (cond 
>             ((null? l) #f)
>             ((atom? (car l)) (lat? (cdr l)))
>             (else #f))))
> 
> 
> So an empty list has to be a lat, and it is not.
> Or is it? Then an empty list can be anything.
> 
> 
> Thanks,
> 
> Frank
> ____________________
>  Racket Users list:
>  http://lists.racket-lang.org/users


____________________
  Racket Users list:
  http://lists.racket-lang.org/users