htdp: 9.3.2 solution

Krzysiek Adamczyk

unread,

Feb 4, 2010, 7:24:29 AM2/4/10

to

Hello world

I'm trying to learn programming by myself - during those trials
I've stumbled upon htpd and I've stayed with it - it suits me well. I
didn't have any problems until the moment I got to recursion. It's all
about the 9.3.2 exercise, as in the subject. It goes like this
{
(define (contains-doll? a-list-of-symbols)
(cond
[(empty? a-list-of-symbols) false]
[else (cond
[(symbol=? (first a-list-of-symbols) 'doll) true]
[else (contains-doll? (rest a-list-of-symbols))])]))
...
Exercise 9.3.2. Another way of formulating the second cond-clause in
the function contains-doll? is to understand

(contains-doll? (rest a-list-of-symbols))

as a condition that evaluates to either true or false, and to combine
it appropriately with the condition

(symbol=? (first a-list-of-symbols) 'doll)

Reformulate the definition of contains-doll? according to this
observation.
}

I have an idea, but it's a simple one. It changes the second cond to
this:
{
...
[else (cond
[(contains-doll? (rest a-list-of-symbols)) true]
[(symbol=? (first a-list-of-symbols) 'doll) true]
[else false])]))
}
Now my problem is - can it be that simple or is there more to it and I
don't understand it properly?

Jussi Piitulainen

unread,

Feb 4, 2010, 7:43:07 AM2/4/10

to

Krzysiek Adamczyk writes:
...

> ...
> Exercise 9.3.2. Another way of formulating the second cond-clause
> in the function contains-doll? is to understand
>
> (contains-doll? (rest a-list-of-symbols))
>
> as a condition that evaluates to either true or false, and to
> combine it appropriately with the condition
>
> (symbol=? (first a-list-of-symbols) 'doll)
>
> Reformulate the definition of contains-doll? according to this
> observation.
> }
>
> I have an idea, but it's a simple one. It changes the second cond to
> this:
> {
> ...
> [else (cond
> [(contains-doll? (rest a-list-of-symbols)) true]
> [(symbol=? (first a-list-of-symbols) 'doll) true]
> [else false])]))
> }
> Now my problem is - can it be that simple or is there more to it and
> I don't understand it properly?

Has the book dealt with `and' and `or' at the point of exercise? You
can use one of those to combine the two `true' branches of your
solution into one. That _might_ be what the book is suggesting.

You can even write the whole body of the predicate with no `cond' at
all, as (and ... (or ... ...)). I like to do it that way.

Krzysiek Adamczyk

unread,

Feb 4, 2010, 8:02:30 AM2/4/10

to

On Feb 4, 1:43 pm, Jussi Piitulainen <jpiit...@ling.helsinki.fi>
wrote:

Logical operators were introduced earlier and the trick with using
them is in fact a neat one. Thanks!

Pascal J. Bourguignon

unread,

Feb 4, 2010, 2:14:38 PM2/4/10

to

Krzysiek Adamczyk <wdes...@gmail.com> writes:

> Hello world
>
> I'm trying to learn programming by myself - during those trials
> I've stumbled upon htpd and I've stayed with it - it suits me well. I
> didn't have any problems until the moment I got to recursion. It's all
> about the 9.3.2 exercise, as in the subject. It goes like this
> {
> (define (contains-doll? a-list-of-symbols)
> (cond
> [(empty? a-list-of-symbols) false]
> [else (cond
> [(symbol=? (first a-list-of-symbols) 'doll) true]
> [else (contains-doll? (rest a-list-of-symbols))])]))
> ...
> Exercise 9.3.2. Another way of formulating the second cond-clause in
> the function contains-doll? is to understand
>
> (contains-doll? (rest a-list-of-symbols))
>
> as a condition that evaluates to either true or false, and to combine
> it appropriately with the condition
>
> (symbol=? (first a-list-of-symbols) 'doll)
>
> Reformulate the definition of contains-doll? according to this
> observation.
> }

Using or.

> I have an idea, but it's a simple one. It changes the second cond to
> this:
> {
> ...
> [else (cond
> [(contains-doll? (rest a-list-of-symbols)) true]
> [(symbol=? (first a-list-of-symbols) 'doll) true]
> [else false])]))
> }
> Now my problem is - can it be that simple or is there more to it and I
> don't understand it properly?

Notice that by changing the order of the tests here, you are not
changing the result (this is good), but you are changing the time it
takes to get it (you've worsened it a lot).

To see what happen, you can trace the calls to contains-doll?

Depending on the implementation you are using, you may have a trace
operator that would allow you to do that automatically:
(trace contains-doll?)
(contains-doll? '(a doll is my baby))
so that you can try it with either definition.

Another way is to add a display at the beginning of the function:

(define (contains-doll? a-list-of-symbols)
(display (cons 'contains-doll? a-list-of-symbols))
(newline)
...)

Again, try it with both versions.

Finally, when you are using predicates without doing any side effect,
you can easily find a boolean formula, by drawing a truth table:

e = (empty? a-list-of-symbols)
d = (symbol=? (first a-list-of-symbols) 'doll)
r = (contains-doll? (rest a-list-of-symbols))

The watch the lines where the result is true. When there's a false in
a column, take (not <condition>), when there's a true, take
<condition>. Join them all with a (and ...), and join all the
columns with a (or ...):

So: result = (or (and (not e) d r) (and (not e) d (not r)) (and (not e) (not d) r))

Then you can apply some boolean algebra to simplify the formula.

We may factorize (not e):

result = (and (not e) (or (and d r) (and d (not r)) (and (not d) r)))

We may factorize d:

result = (and (not e) (or (and d (or r (not r))) (and (not d) r)))

We may simplify (or r (not r)) = true

result = (and (not e) (or (and d true) (and (not d) r)))

We may simplify (and d true) = d

result = (and (not e) (or d (and (not d) r)))

And finally, (or d (and (not d) r)) = (or d r)

Which can be checked with a truth table:

(karnaugh '(d r)
'(("(or d (and (not d) r))" . (lambda(d r) (or d (and (not d) r))))
("(or d r)" . (lambda(d r) (or d r))))
'("false" . "true")
'("false" . "true"))

therefore:

result = (and (not e) (or d r))

The nice thing about this, is that it can be archieved automatically,
applying simple thoughtless rules.

(karnaugh-solve '(e d r) '(r)
'(( true true true false )
( true true false false )
( true false true false )
( true false false false )
( false true true true )
( false true false true )
( false false true true )
( false false false false ))
'( false . true))
-->
((r . (lambda (e d r) (or (and (not e) d r) (and (not e) d (not r)) (and (not e) (not d) r)))))
;; I didn't implement the simplification of boolean expressions yet ;-)

Finally, in boolean algebra, and and or are commutative, but we have
to be careful with procedures, because some may not be called when a
pre-condition is not realized. In this case, when e is true, that is
when a-list-of-symbol is (), we cannot call first or rest on it. The
order matters, and the scheme operators and and or implement shortcuts
http://www.schemers.org/Documents/Standards/R5RS/HTML/r5rs-Z-H-7.html#%_idx_118
so that we can write directly:

(define (contains-doll? a-list-of-symbols)
(and (not (empty? a-list-of-symbols))
(or (symbol=? (first a-list-of-symbols) 'doll)
(contains-doll? (rest a-list-of-symbols)))))

Notice that we couldn't write:

(define (contains-doll? a-list-of-symbols)
(let ((e (empty? a-list-of-symbols))
(d (symbol=? (first a-list-of-symbols) 'doll))
(r (contains-doll? (rest a-list-of-symbols))))
(and (not e) (or d r))))

because d and r should not be evaluated when e is true. (But if they
were independent conditions, and when the boolean expression is more
complex and refers several times the same condition, it would be a
nice way to write it).

http://darcs.informatimago.com/darcs/public/emacs/pjb-soource.el
--
__Pascal Bourguignon__

Pascal J. Bourguignon

unread,

Feb 4, 2010, 4:47:34 PM2/4/10

to

Krzysiek Adamczyk <wdes...@gmail.com> writes:

> Hello world
>
> I'm trying to learn programming by myself - during those trials
> I've stumbled upon htpd and I've stayed with it - it suits me well. I
> didn't have any problems until the moment I got to recursion. It's all
> about the 9.3.2 exercise, as in the subject. It goes like this
> {
> (define (contains-doll? a-list-of-symbols)
> (cond
> [(empty? a-list-of-symbols) false]
> [else (cond
> [(symbol=? (first a-list-of-symbols) 'doll) true]
> [else (contains-doll? (rest a-list-of-symbols))])]))
> ...
> Exercise 9.3.2. Another way of formulating the second cond-clause in
> the function contains-doll? is to understand
>
> (contains-doll? (rest a-list-of-symbols))
>
> as a condition that evaluates to either true or false, and to combine
> it appropriately with the condition
>
> (symbol=? (first a-list-of-symbols) 'doll)
>
> Reformulate the definition of contains-doll? according to this
> observation.
> }

Using or.

> I have an idea, but it's a simple one. It changes the second cond to
> this:
> {
> ...
> [else (cond
> [(contains-doll? (rest a-list-of-symbols)) true]
> [(symbol=? (first a-list-of-symbols) 'doll) true]
> [else false])]))
> }
> Now my problem is - can it be that simple or is there more to it and I
> don't understand it properly?

Notice that by changing the order of the tests here, you are not

Then watch the lines where the result is true. When there's a false in

We may factorize d:

therefore:

nil

Pascal J. Bourguignon

unread,

Feb 4, 2010, 4:48:16 PM2/4/10

to

Krzysiek Adamczyk <wdes...@gmail.com> writes:

> Hello world
>
> I'm trying to learn programming by myself - during those trials
> I've stumbled upon htpd and I've stayed with it - it suits me well. I
> didn't have any problems until the moment I got to recursion. It's all
> about the 9.3.2 exercise, as in the subject. It goes like this
> {
> (define (contains-doll? a-list-of-symbols)
> (cond
> [(empty? a-list-of-symbols) false]
> [else (cond
> [(symbol=? (first a-list-of-symbols) 'doll) true]
> [else (contains-doll? (rest a-list-of-symbols))])]))
> ...
> Exercise 9.3.2. Another way of formulating the second cond-clause in
> the function contains-doll? is to understand
>
> (contains-doll? (rest a-list-of-symbols))
>
> as a condition that evaluates to either true or false, and to combine
> it appropriately with the condition
>
> (symbol=? (first a-list-of-symbols) 'doll)
>
> Reformulate the definition of contains-doll? according to this
> observation.
> }

Using or.

> I have an idea, but it's a simple one. It changes the second cond to
> this:
> {
> ...
> [else (cond
> [(contains-doll? (rest a-list-of-symbols)) true]
> [(symbol=? (first a-list-of-symbols) 'doll) true]
> [else false])]))
> }
> Now my problem is - can it be that simple or is there more to it and I
> don't understand it properly?

Notice that by changing the order of the tests here, you are not

pinchyfingers

unread,

Feb 10, 2010, 11:48:59 PM2/10/10

to

On Feb 4, 4:48 pm, p...@informatimago.com (Pascal J. Bourguignon)
wrote:

> order matters, and the scheme operators and and or implement shortcutshttp://www.schemers.org/Documents/Standards/R5RS/HTML/r5rs-Z-H-7.html...

> so that we can write directly:
>
> (define (contains-doll? a-list-of-symbols)
> (and (not (empty? a-list-of-symbols))
> (or (symbol=? (first a-list-of-symbols) 'doll)
> (contains-doll? (rest a-list-of-symbols)))))
>
> Notice that we couldn't write:
>
> (define (contains-doll? a-list-of-symbols)
> (let ((e (empty? a-list-of-symbols))
> (d (symbol=? (first a-list-of-symbols) 'doll))
> (r (contains-doll? (rest a-list-of-symbols))))
> (and (not e) (or d r))))
>
> because d and r should not be evaluated when e is true. (But if they
> were independent conditions, and when the boolean expression is more
> complex and refers several times the same condition, it would be a
> nice way to write it).
>
> http://darcs.informatimago.com/darcs/public/emacs/pjb-soource.el
> --
> __Pascal Bourguignon__

Thanks so much for the detailed help.