HtDP: Questions on excersises

[hWnd]

I can't solve excersise 14.1.3.

That's what I could invent:

(define (count-persons a-ftn)
(cond
[(empty? a-ftn) 0]
[(else (+ 1
(count-persons (child-father a-ftn))
(count-persons (child-mother a-ftn)))]))

... but it seems to be wrong! ?

(sry, but I'm writing from a pda)

p.s. Why I can't reply to a thread with PIE & Minimo?!

[Pascal Bourguignon]

"hWnd" <geo...@smilyanov.net> writes:

> I can't solve excersise 14.1.3.
>
> That's what I could invent:
>
> (define (count-persons a-ftn)
> (cond
> [(empty? a-ftn) 0]
> [(else (+ 1
> (count-persons (child-father a-ftn))
> (count-persons (child-mother a-ftn)))]))
>
> ... but it seems to be wrong! ?

What makes you think it's wrong?

The only case it could be wrong is if there's some consanguinity in
the family tree...

Then you could write something like:

(define (count-persons a-ftn)
(define (collect-persons a-fnt collection)
(if (empty? a-fnt)
collection
(collect-persons (child-father a-fnt)
(collect-persons (child-mother a-fnt)
(cons a-fnt collection)))))
(length (delete-duplicates (collect-persons a-fnt '()))))

--
__Pascal Bourguignon__ http://www.informatimago.com/

The world will now reboot. don't bother saving your artefacts.

[hWnd]

Consider the following:
;;---
(define-struct child (father mother name date eyes))

(define Carl (make-child empty empty 'Carl 2000 'green))
(define Bettina (make-child empty empty 'Bettina 2000 'green))

(define Fred (make-child Carl Bettina 'Fred 2000 'blue))
(define Eva (make-child Carl Bettina 'Eva 2000 'yellow))

(define Gustav (make-child Fred Eva 'Gustav 2001 'yellow))

;;14.1.3
;;count-persons: ftn -> number
;;produces the number of people in the ftn

(define (count-persons a-ftn)
(cond
[(empty? a-ftn) 0]

[else (+ 1

(count-persons (child-father a-ftn))
(count-persons (child-mother a-ftn)))]))

(count-persons Gustav) ;;-- returns 7???
;;---

Why 7 instead of 5?

[Pascal Bourguignon]

"hWnd" <geo...@smilyanov.net> writes:

I explained it to you in my previous post!
Because this familly is depraved! :-)
I also explained in my previous post how you could obtain the correct count.
I even gave you an implementation!

What more do you want?

Does Gustav have a mother-grand-father? Yes, Carl.
Does Gustav have a father-grand-father? Yes, Carl.
Does Gustav have a mother-grand-mother? Yes, Bettina.
Does Gustav have a father-grand-mother? Yes, Bettina.
Does Gustav have a mother? Yes, Eva.
Does Gustav have a father? Yes, Fred.
Plus Gustav.
Total = 7

--
__Pascal Bourguignon__ http://www.informatimago.com/

"Specifications are for the weak and timid!"

[Abdulaziz Ghuloum]

Because Gustav's parents are brother and sister?

Aziz,,,

[hWnd]

I got it, the problem is that HtDP has not introduced such techniques,
yet. And why depraved -- doesn't it resemble a real-world family tree?
Maybe I haven't understood what's a "legal" ftn is (according to the
book)?

Anyway, what about the next excersise? That's the template (and maybe
part of the solution) I could invent:

;;14.1.4
;;average-age: ftn number -> number
;;produces the average age of all people in a family tree
(define (average-age ftn now)
(cond
[(empty? ftn) 0]
[else
(+ (average-age (child-father ftn) now)
(average-age (child-mother ftn) now)
(- now (child-date ftn)))]))

;;(average-age Gustav 2006) ;;-- returns 41???

[hWnd]

>>Because Gustav's parents are brother and sister?

Whoops, yes :-))

So, let's change the defs:

(define Carl (make-child empty empty 'Carl 2000 'green))
(define Bettina (make-child empty empty 'Bettina 2000 'green))

(define Fred (make-child Carl Bettina 'Fred 2000 'blue))

(define Pamela (make-child empty empty 'Pamela 2000 'yellow))

(define Gustav (make-child Fred Pamela 'Gustav 2001 'yellow))

Now average-age applied to Gustav returns 29 (4*6+1*5). How to calc the
average of this?

[Pascal Bourguignon]

"hWnd" <geo...@smilyanov.net> writes:
> I got it, the problem is that HtDP has not introduced such techniques,
> yet. And why depraved -- doesn't it resemble a real-world family tree?
> Maybe I haven't understood what's a "legal" ftn is (according to the
> book)?

You can also write it as:

(define (collect-persons a-fnt collection)
(if (empty? a-fnt)
collection
(collect-persons (child-father a-fnt)
(collect-persons (child-mother a-fnt)
(cons a-fnt collection)))))

(define (count-persons a-ftn)

(length (delete-duplicates (collect-persons a-fnt '()))))

There, there's nothing HtDP hasn't introduced yet.

> Anyway, what about the next excersise? That's the template (and maybe
> part of the solution) I could invent:
>
> ;;14.1.4
> ;;average-age: ftn number -> number
> ;;produces the average age of all people in a family tree
> (define (average-age ftn now)
> (cond
> [(empty? ftn) 0]
> [else
> (+ (average-age (child-father ftn) now)
> (average-age (child-mother ftn) now)
> (- now (child-date ftn)))]))
>
> ;;(average-age Gustav 2006) ;;-- returns 41???

Same problem, same solution.

You can rename the function and introduce a new one that you'll be
using over and over:

(define (collect-duplicate-persons ftree collection)
(if (empty? ftree)
collection
(collect-duplicate-persons
(child-father ftree)
(collect-duplicate-persons (child-mother ftree)
(cons ftree collection)))))

(define (collect-unique-persons ftree)
(delete-duplicates (collect-duplicate-persons ftree '()) equal?))

(define (count-persons ftree)
(length (collect-unique-persons ftree)))

(define (child-age x y)
(- y (child-date x)))

(define (average-age ftree year)
(let ((persons (collect-unique-persons ftree)))
(/ (reduce + (map (lambda (p) (child-age p year)) persons) 0)
(length persons))))

Perhaps delete-duplicates and reduce is not in your library. Then you
can just add them:

(define (contains? element list equal?)
(cond ((null? list) #f)
((equal? element (car list)) #t)
(else (contains? element (cdr list) equal?))))

(define (delete-duplicates-i list uniques equal?)
(cond ((null? list)
uniques)
((contains? (car list) uniques equal?)
(delete-duplicates-i (cdr list) uniques equal?))
(else
(delete-duplicates-i (cdr list) (cons (car list) uniques) equal?))))

(define (delete-duplicates list equal?)
(delete-duplicates-i list '() equal?))

(define (reduce f l i)
(if (null? l)
i
(f (car l) (reduce f (cdr l) i))))

--
__Pascal Bourguignon__ http://www.informatimago.com/

In a World without Walls and Fences,
who needs Windows and Gates?

[Pascal Bourguignon]

"hWnd" <geo...@smilyanov.net> writes:

Yes, that's the question! How do you compute an average?

--
__Pascal Bourguignon__ http://www.informatimago.com/

Until real software engineering is developed, the next best practice
is to develop with a dynamic system that has extreme late binding in
all aspects. The first system to really do this in an important way
is Lisp. -- Alan Kay

[hWnd]

Pascal, thank you very much for your assistance -- but to be honest
these fancy functions are of little help for me: (a) I don't understand
some (key) parts and (b) HtDP hasn't introduced the concepts you
utilize (for now), and most important -- they want a single function,
not a set of auxiliary functions.

-- Georgi

[hWnd]

Excersise 14.2.3
(http://www.htdp.org/2002-09-22/Book/curriculum-Z-H-19.html#%_sec_14.2):

---
(define-struct node (ssn name left right))

(define Foo (make-node 123 'Foo empty empty))
(define Bar (make-node 345 'Bar empty empty))

(define Gazonk (make-node 567 'Gazonk Foo Bar))

(define Quux (make-node 789 'Quux Gazonk empty))

;;14.2.3
(define (inorder BT)
(cond
[(empty? BT) empty]
[else (cons (node-ssn BT) (append
(inorder (node-left BT))
(inorder (node-right BT))))]))

(inorder Quux) ;returns (list 789 567 123 345)

---

Is it ok?

What's the most optimal way to read/use/understand HtDP? I don't have
access to the solutions; is it fine to ask here for comments and
evaluations (for every second excersise :-))?