Scheme - How to think?

Author

How to think?

bobueland@yahoo.com

2006-01-18, 7:05 pm

Look at this simple problem

Problem: Write a procedure (every? pred lst) that returns #f if any
element of lst fails to satisfy pred, and returns #t otherwise.
> (every? number? '(a b c 3 e))
#f
> (every? number? '(1 2 3 5 4))
#t

Now, I'm not after the solution primarily but the process of thinking
when solving such a problem. I tried to record my own thinking process
which turned out to be in six steps. Now I'm newbie when it comes to
Scheme, so my thinking is probably not the most effective or beautiful.
Can you give me some guidance how to think when solving this problem
(or these kind of problems) in Scheme?

Bob

---
My current thinking process

Step 1: The simplest case is when the lst is empty. What should the
result be? It should be true, so:

(define (every? pred lst)
(cond ((null? lst) #t)))

; Test
(every? number? ()) ==> #t

Step 2: Suppose now that lst is (8) and that pred is number?. The
result should be true, so

(define (every? pred lst)
(cond ((null? lst) #t)
((pred (car lst)) #t)))

; Test
(every? number? ()) ==> #t
(every? number? '(8)) ==> #f

Step 3: Suppose now that lst is (a) and that pred is number?. The
result should be false, so

(define (every? pred lst)
(cond ((null? lst) #t)
((pred (car lst)) #t)
(else #f)))

; Test
(every? number? ()) ==> #t
(every? number? '(8)) ==> #t
(every? number? '(a)) ==> #f

Step 4: Suppose now that lst is (8 3) and that pred is number?. The
result should be true, so
(define (every? pred lst)
(cond ((null? lst) #t)
((pred (car lst)) (and #t (every? pred (cdr lst))))
(else #f)))

This looks like a complete solution! Let me test it
; Test
(every? number? ()) ==> #t
(every? number? '(8)) ==> #t
(every? number? '('a)) ==> #f
(every? number? '(a b c 3 e)) ==> #f
(every? number? '(1 2 3 5 4)) ==> #t
(every? symbol? '(a foo)) ==> #t

It works!

Step 5: Is it any way to simplify the solution?
(and #t boolean) = boolean
Hence simplify to

(define (every? pred lst)
(cond ((null? lst) #t)
((pred (car lst)) (every? pred (cdr lst))))
(else #f)))

Test again. It works!

Step 6. This problem involved traversing a list. I first made the
program work for empty list, then for a list with one element, and then
for two elements and the solution fell out from itself.
Maybe I could use similar pattern for "traversing a list" kind of
problems?

Jens Axel Søgaard

2006-01-18, 7:05 pm

bobueland@yahoo.com wrote:
> Look at this simple problem
>
> Problem: Write a procedure (every? pred lst) that returns #f if any
> element of lst fails to satisfy pred, and returns #t otherwise.
>
>
> #f
>
>
> #t
>
> Now, I'm not after the solution primarily but the process of thinking
> when solving such a problem. I tried to record my own thinking process
> which turned out to be in six steps. Now I'm newbie when it comes to
> Scheme, so my thinking is probably not the most effective or beautiful.
> Can you give me some guidance how to think when solving this problem
> (or these kind of problems) in Scheme?

The corner stone of "How To Design Programs" is "How to think".

<http://www.htdp.org/2003-09-26/Book...tml#node_chap_9>

> My current thinking process
>
> Step 1: The simplest case is when the lst is empty. What should the
> result be? It should be true, so:
>
> (define (every? pred lst)
> (cond ((null? lst) #t)))
>
> ; Test
> (every? number? ()) ==> #t
>
> Step 2: Suppose now that lst is (8) and that pred is number?. The
> result should be true, so
>
> (define (every? pred lst)
> (cond ((null? lst) #t)
> ((pred (car lst)) #t)))
>
> ; Test
> (every? number? ()) ==> #t
> (every? number? '(8)) ==> #f
>
> Step 3: Suppose now that lst is (a) and that pred is number?. The
> result should be false, so
>
> (define (every? pred lst)
> (cond ((null? lst) #t)
> ((pred (car lst)) #t)
> (else #f)))
>
> ; Test
> (every? number? ()) ==> #t
> (every? number? '(8)) ==> #t
> (every? number? '(a)) ==> #f
>
> Step 4: Suppose now that lst is (8 3) and that pred is number?. The
> result should be true, so
> (define (every? pred lst)
> (cond ((null? lst) #t)
> ((pred (car lst)) (and #t (every? pred (cdr lst))))
> (else #f)))
>
> This looks like a complete solution! Let me test it
> ; Test
> (every? number? ()) ==> #t
> (every? number? '(8)) ==> #t
> (every? number? '('a)) ==> #f
> (every? number? '(a b c 3 e)) ==> #f
> (every? number? '(1 2 3 5 4)) ==> #t
> (every? symbol? '(a foo)) ==> #t
>
> It works!
>
> Step 5: Is it any way to simplify the solution?
> (and #t boolean) = boolean
> Hence simplify to
>
> (define (every? pred lst)
> (cond ((null? lst) #t)
> ((pred (car lst)) (every? pred (cdr lst))))
> (else #f)))
>
> Test again. It works!
>
> Step 6. This problem involved traversing a list. I first made the
> program work for empty list, then for a list with one element, and then
> for two elements and the solution fell out from itself.
> Maybe I could use similar pattern for "traversing a list" kind of
> problems?

Your way of thinking is already quite systematic. And you are
right, it makes programming much easier to learn the patterns.

--
Jens Axel Søgaard

Lauri Alanko

2006-01-18, 7:05 pm

In article <1137620831.352134.115110@g44g2000cwa.googlegroups.com>,
<bobueland@yahoo.com> wrote:
> (every? number? ()) ==> #t

Superduperminor nit: () should be quoted. Practically all
implementations are pretty lenient about this, though.

> Hence simplify to
>
> (define (every? pred lst)
> (cond ((null? lst) #t)
> ((pred (car lst)) (every? pred (cdr lst))))
> (else #f)))

This may or may not be helpful, but note that:

(cond (t1 e1) (t2 e2) (else e3)) = (if t1 e1 (if t2 e2 e3))
(if t #t e) = (or t e) (provided that t returns a boolean)
(if t e #f) = (and t e)

Hence you may rewrite your cond expression as:

(or (null? lst)
(and (pred (car lst))
(every? pred (cdr lst))))

Whether this is clearer or not is purely a matter of taste.
Personally, I appreciate the brevity.

> Maybe I could use similar pattern for "traversing a list" kind of
> problems?

And maybe you could turn this pattern into a function?

You're doing just fine.

Lauri

Greg Buchholz

2006-01-18, 7:05 pm

bobueland@yahoo.com

2006-01-18, 7:05 pm

Greg Buchholz wrote:
>http://srfi.schemers.org/srfi-1/srfi-1.html

Thanks for this link. Many examples making it easy to understand!

Jens Axel Søgaard

2006-01-18, 7:05 pm

Jens Axel Søgaard wrote:
> bobueland@yahoo.com wrote:
>
>
>
> The corner stone of "How To Design Programs" is "How to think".
>
> <http://www.htdp.org/2003-09-26/Book...tml#node_chap_9>

Let us try to follow their design recipe.

;;; DATA ANALYSIS AND DESIGN

; A LIST-OF-ELEMENTS is either a
; (cons x xs)
; or
; ()
; where x is an element
; and xs is a list-of-elements.

;;; CONTRACT, PURPOSE AND HEADER

;; every? : (element -> boolean) list-of-elements -> boolean
; return true if all elements of the list fullfill the predicate

;;; EXAMPLES

; (every? number? '()) ==> #t
; (every? number? (cons 8 '()) ==> #t
; (every? number? (cons "foo" '()) ==> #f
; (every? number? (cons "foo" (cons 3 (cons 4 '())))) ==> #f
; (every? number? (cons 1 (cons 3 (cons 4 '())))) ==> #t
; (every? symbol? (cons 'a (cons 'foo '())) ==> #t

;;; TEMPLATE for functions for list-of-elements (loe)

; there are two kinds of lists:

(define (fun-for-loe xs)
(cond
[(null? xs) ...]
[(pair? xs) ...]))

; when xs is a pair, it has two parts:

(define (fun-for-loe xs)
(cond
[(null? xs) ...]
[(pair? xs) ... (car xs) ... (cdr xs) ...]))

; since the (cdr xs) is the self referentiel part of
; the data definition, we need a recursive call

(define (fun-for-loe xs)
(cond
[(null? xs) ...]
[(pair? xs) ... (car xs) ... (fun-for-loe (cdr xs)) ...]))

;;; BODY

; Now we use our template for functions on list-of-elements to
; to write every? . Note that we need an extra argument for
; the predicate, so we add pred to the recursive call.

(define (every? pred xs)
(cond
[(null? xs) ...]
[(pair? xs) ... (car xs) ... (every? pred (cdr xs)) ...]))

; our example (every? number? '()) ==> #t gives what to fill
; in the first clause

(define (every? pred xs)
(cond
[(null? xs) '()]
[(pair? xs) ... (car xs) ... (every? pred (cdr xs)) ...]))

; Now (and not before) comes the creative part. We need to
; figure out how to combine (car xs) and (every? pred (cdr xs))
; in order to the purpose to be correct

; return true if all elements of the list fullfill the predicate

; All elements... That must be mean that both the first element and all
; the rest of the elements should fulfill the predicate.

;; every? : (element -> boolean) list-of-elements -> boolean
; return true if all elements of the list fullfill the predicate
(define (every? pred xs)
(cond
[(null? xs) '()]
[(pair? xs) (and (pred (car xs))
(every? pred (cdr xs)))]))

; TESTING

; Now one runs the examples and sees whether they work.

--
Jens Axel Søgaard

Jérémie Lumbroso

2006-01-18, 7:05 pm

You can make it look a bit better, since the predicate returns #t or
#f, you do not need to explicitly return #f (you just let the predicate
do its job):

(define (every? pred L)
(or (not (pair? L))
(and (pred (car L)) (every? pred (cdr L)))))

The steps you describe will never fail you and is, IMHO, how everybody
reasons.

- J=E9r=E9mie

Jens Axel Søgaard

2006-01-18, 7:05 pm

> (define (every? pred xs)
> (cond
> [(null? xs) '()]
> [(pair? xs) ... (car xs) ... (every? pred (cdr xs)) ...]))

Oops. I wrote '() in stead of #t.

> ; Now (and not before) comes the creative part. We need to
> ; figure out how to combine (car xs) and (every? pred (cdr xs))
> ; in order to the purpose to be correct
>
> ; return true if all elements of the list fullfill the predicate
>
> ; All elements... That must be mean that both the first element and all
> ; the rest of the elements should fulfill the predicate.
>
>
> ;; every? : (element -> boolean) list-of-elements -> boolean
> ; return true if all elements of the list fullfill the predicate
> (define (every? pred xs)
> (cond
> [(null? xs) #t]
> [(pair? xs) (and (pred (car xs))
> (every? pred (cdr xs)))]))
>
> ; TESTING
>
> ; Now one runs the examples and sees whether they work.

Do as I say, not as I do ...

--
Jens Axel Søgaard

Joe Marshall

2006-01-19, 4:08 am

bobueland@yahoo.com wrote:
> (define (every? pred lst)
> (cond ((null? lst) #t)
> ((pred (car lst)) (every? pred (cdr lst))))
> (else #f)))
>
> Test again. It works!

Just a quick point. This is a fine solution (and it is the one that is
usually taught), but I dislike the way people are taught to use `NULL?'
as the base case when traversing a list. Although an empty list is
NULL?, things that are not NULL? are not necessarily lists.
So rather than test if you have the base case, try testing if you
haven't reached the end:

(Another minor gripe. Yes, you can accidentally shadow `list' in
Scheme, but is it really such a burden to look to see if you actually
do? If you don't then there is no issue with an argument called
`list'.)

(define (every? pred list)
(cond ((pair? list) (and (pred (car list)) (every? pred (cdr list))))
((null? list) #t)
(else (error "Argument was not a proper list."))))

An advantage of writing the code this way is that you allow the
compiler to be more clever. In the first example, we test for NULL?,
but we cannot take CAR and CDR without further testing for PAIR? (This
is an implied test.) By explicitly testing for PAIR?, the compiler can
deduce that the variable list must be bound to a pair if the test
succeeds and therefore no further check need be done to take the CAR
and CDR. (This will have a measurable effect for an optimizing Scheme
compiler.)

Brian Harvey

2006-01-19, 4:08 am

bobueland@yahoo.com writes:
>Step 1: The simplest case is when the lst is empty. What should the
>result be?

Unless the problem is easy enough that I see the solution at once, I generally
leave the base case for last. (Of course the test comes first in the text of
the finished program, but I write it last, through the miracle of emacs. :-)

For one thing, sometimes it turns out that the recursion requires a list of
length 2, so a list of length 1 has to be a base case. (Merge sort and
partition sort are examples.)

Or (as in the towers of Hanoi thread just recently) I may not be sure until
after seeing the rest of the program whether my base case should be 1 or 0.

>Step 2: Suppose now that lst is (8) and that pred is number?. The
>result should be true, so
> [...]
>Step 4: Suppose now that lst is (8 3) and that pred is number?. The
>result should be true, so
> [...]
>Step 5: Is it any way to simplify the solution?

Your chain of thought must have had some steps you aren't telling us about.
In step 2 (and step 3, which doesn't change this) you have what's actually
an incorrect program. Your test case in step 4 *doesn't* actually show the
incorrectness of it; the step-2 program gives the correct answer by accident.
And yet supposedly it was thinking about that example that got you to fix
the program. So the thinking you did in step 4 must, it seems to me, have
taken into account lists such as (8 a) that do invalidate the original code.

In step 2, did you actually think the program was correct? Or were you
thinking "I know this is wrong, but I'll fix it later"?

bobueland@yahoo.com

2006-01-19, 4:08 am

Brian Harvey wrote:
> bobueland@yahoo.com writes:
>
> I generally leave the base case for last.
>
No this wouldn't worked for me. It requires confidence which I didn't
have. So I was forced to take one small step and see that it worked.
(As I see it now I basically used induction and I had to prove case n=0
before moving to n+1 assuming that it worked for n.)

> Your chain of thought must have had some steps you aren't telling us about.
I tried first to write a program without thinking in systematic way,
but it didn't work, so I said to myself. "Wait, go back to step zero
and try to simplify the problem to something that you're sure you could
handle".

> In step 2, did you actually think the program was correct? Or were you
> thinking "I know this is wrong, but I'll fix it later"?
It was the latter case, I knew it was't generally correct but I was
satisfied that it was giving the right answer for just the special case
I was considering.

I see problem solving (not just in math and programming, but in life in
general) as moving from a point A (what I have from the beginning) to a
point Z (the solution that I want to arrive at). (Points A and Z are
points in an abstract "solution space"). There is not normally a
straight path from A to Z unless it's a trivial problem. Often I'm
satisfied if I can find a way to go from A to a point B which is nearer
to Z then A is, becuase that means that I'm nearer the solution then I
was before. From B I try to go to a point C, and so on (A -> B -> .. ->
Z). Sometimes it's easier to go the other way round Z -> Y -> .. ->
A). Actually in general there is not a simple list of points but rather
a tree, becuse of forking)

In our original problem, what was the point B. It was the empty list. I
said to myself: "OK, this is a to hard problem, but could I solve it
for a special case. And that special case was the empty list. Then I
made up the point C, which was the list (8), and so on. I was rather
surprised when the solution fell out of itself after solving the
problem for a list of just two elements. Now looking back I ask myself,
why did the solution fell out so easy?

It must be due to the fact that a list is a special kind of structure.
<list> ::= () | (<element> <list> )
This describes a set of rules (a grammar). Here we have two rules. The
first rule says that the empty list is a list, and the second says that
if e is an element and L is a list then (e L) is a list. So the reason
my attempt ended luckily is probably due to the fact that it followed
the grammar. I basically made an induction based on the structure of a
list. That's why the solution fell out by considering a list with two
elements. So in general you can say that you should structure your
program after the structure of your 'data'.

Neil Cerutti

2006-01-26, 7:04 pm

On 2006-01-19, bobueland@yahoo.com <bobueland@yahoo.com> wrote:
> Brian Harvey wrote:
>
> It was the latter case, I knew it was't generally correct but I
> was satisfied that it was giving the right answer for just the
> special case I was considering.

You might want to adopt a slightly different approach to your
intermediate testing. Name your intermediate results so that you
know their domain.

Now, I would start thinking about a one-element list instead of
an empty one, but that's because I read Brian Harvey's book. ;-)
Seriously, it sometimes requires insight gained by writing the
other cases to know what the base case is.

Step 1:

(define (every-1? pred seq)
(pred (car seq)))

Testing:

(every-1? number? '(1))
#t

(every-1? number? '(c))
#f

So far so good.

Step 2:

Next, a two element list. The important part here is that I must
write it to take advantage of my previous function, every-1?.

(define (every-2? pred seq)
(and (pred (car seq)) (every-1? pred (cdr seq)))

More testing:

(every-2? number? '(1 2))
#t

(every-2? number? '(1 a))
#f

(every-2? number? '(a 1))
#f

(every-2? number? '(a b))
#f

As it turns out, the recursive case is now solved. I can see that
every-2? will generalize to any length list.

(define (every? pred seq)
(and (pred (car seq))
(every? pred (cdr seq)))

The only remaining problem is that it terminates with an error.
Prompting me to finally think about the base case.

It's so much nicer when null can be the base case, so lets start
by trying that. (every? pred '()) ought to be #t. Yay! In some
cases, a null argument wouldn't be defined, so you'd have to come
up with some other base case.

(define (every? pred seq)
(or (not (pair? seq))
(and (pred (car seq))
(every? pred (cdr seq)))))

Testing reveals that my function works.

Analysis reveals it's got linear space complexity, using the
substitution model:

(every? number? '(1 2 3))
-->
(or #f (and #t (every? pred '(2 3))))
-->
(or #f (and #t (or #f (and #t (every? pred '(3))))))
-->
(or #f (and #t (or #f (and #t (or #f (and #t (every? pred '())))))))
-->
(or #f (and #t (or #f (and #t (or #f (and #t #t))))))
-->
.....
-->
#t

Transforming it to a tail-recursive version would be a good idea
someday. To do that, I need to prevent the cascading (or #f (and
....) calls. What state do the and/or calls require to obviate
them? Just the #t or #f result so far. I can stop as soon as I
see any false result.

(define (every? pred seq)
(define (every-do? seq so-far)
(if (or (not (pair? seq))
(not so-far))
so-far
(every-do? (cdr seq) (pred (car seq)))))
(every-do? seq #t))

Note that I no longer needed to pass the predicate into the
recursion, either.

The function now uses constant space:

(every? number? '(1 2 3))
-->
(every-do? '(1 2 3) #t)
-->
(every-do? '(2 3) #t)
-->
(every-do? '(3) #t)
-->
(every-do? '() #t)
-->
#t

--
Neil Cerutti

Sponsored Links