# Re: [racket-users] BST fold function and finding a node

```> On Sep 10, 2017, at 9:10 AM, Fernando Basso <fernandobasso...@gmail.com>
> wrote:
>
> Thanks for the help. I found it amazingly well worded, giving me proper
> insights to reach a solution without giving the solution proper, which I
> happen to believe to be one of the most effective ways to help one learn
> anything. Much appreciated. And indeed, I reworked the code using the four
> steps you have so kindly and eloquently elaborated, and it did make things
> easy.
>
> The check expects all pass now, and I trust I have a working solution, which
> refrain to post here now not being sure whether I should.```
```

> As a side note, I got to know that course because of a friend, and then I
> discovered the book. I intend to finish the course and then study the book as
> seriously as I possibly can. I took a look at some parts of it and figured
> out I lack some basic math background to help me along. For example, in part
> one, composing functions
> <http://www.ccs.neu.edu/home/matthias/HtDP2e/part_one.html#%28part._sec~3acomposing%29>
>  I found this:
>
> Stop! Explain the minus sign before you proceed.
>
> I am really not sure what I am supposed to explain there (probably because my
> poor math background, which I am slowly improving through Khan Academy) and
> am afraid of asking too many dumb questions here lest I annoy the list
> members and take people's time with things that perhaps I would be expected
> to know before reading/studying a book like HtDP/2e.

Plug some numbers into the formula. See what happens. Then try to generalize.
The answer is simple and you don’t need to study math. It’s about how you
choose to represent ‘information’ as ‘data’.

— Matthias

>
> On Friday, September 8, 2017 at 10:21:13 AM UTC-3, Matthias Felleisen wrote:
>
> You may wish to read Chapter 16 in HtDP/2e:
>
>
> http://www.ccs.neu.edu/home/matthias/HtDP2e/part_three.html#%28part._ch~3a3use%29
>
> <http://www.ccs.neu.edu/home/matthias/HtDP2e/part_three.html#%28part._ch~3a3use%29>
>
> It teaches how to re-use an existing abstraction, which is
> what you are having trouble with.
>
>
>  (1) I equipped it with a signature for fold-elt,
>       without which you cannot reuse the function BY DESIGN
>  (2) I noted where you failed to develop a signature
>  (3) I added a total dummy definition for ‘c2’
>  (4) I gave respectable names to the parameters of fold-elt
>
> These questions are challenging w/o the design recipe.
> W/ the recipe, they are quite doable. Stick to it.
>
>
> ;; [String Integer Y -> X] [X Y -> Y] Y Element -> X
> ;; The abstract fold/reduce function for Element.
> (define (fold-elt combine-trees combine-lists identity element)
>   (local [;; signature MISSING
>           (define (fn-for-element e)       ; -> X
>             (combine-trees (elt-name e)    ; String
>                            (elt-data e)    ; Integer
>                            (fn-for-loe (elt-subs e))))
>
>           ;; signature MISSING
>           (define (fn-for-loe loe)    ; -> Y
>             (cond [(empty? loe) identity]
>                   [else
>                    (combine-lists (fn-for-element (first loe))
>                                   (fn-for-loe (rest loe)))]))]
>     (fn-for-element element)))
>
> ;; String Element -> Integer or false
> ;; Search the given tree for an element with the given name,
> ;; produce data if found; false otherwise
> (check-expect (find "F3" F1) #f)
> (check-expect (find "F3" F3) 3)
> (check-expect (find "D4" D4) 0)
> (check-expect (find "D6" D6) 0)
> (check-expect (find "F3" D4) #f)
> (check-expect (find "F1" D4) 1)
> (check-expect (find "F2" D4) 2)
> (check-expect (find "F1" D6) 1)
> (check-expect (find "F3" D6) 3)
>
> (define (find n elt)
>   (local [;; signature missing
>           (define (c1 name data loe)
>             (if (string=? n name) data loe))
>           ;; signature missing
>           (define c2
>             0)]
>     (fold-elt c1 c2 #f elt)))
>
>
>
>> On Sep 8, 2017, at 7:33 AM, Fernando Basso <fernando...@ <>gmail.com
>> <http://gmail.com/>> wrote:
>>
>> I am doing an exercise from EDX course based on H2DP book and am having
>> trouble implementing a `find` function using the abstract function fold-elt.
>> The function should find the element and return its data.
>>
>> -----
>> #lang htdp/isl
>>
>> (define-struct elt (name data subs))
>> ;; Element is (make-elt String Integer ListOfElement)
>> ;; interp. An element in the file system, with name, and EITHER data or subs.
>> ;;         If data is 0, then subs is considered to be list of sub elements.
>> ;;         If data is not 0, then subs is ignored.
>>
>> ;; ListOfElement is one of:
>> ;;  - empty
>> ;;  - (cons Element ListOfElement)
>> ;; interp. A list of file system Elements
>>
>> (define F1 (make-elt "F1" 1 empty))
>> (define F2 (make-elt "F2" 2 empty))
>> (define F3 (make-elt "F3" 3 empty))
>> (define D4 (make-elt "D4" 0 (list F1 F2)))
>> (define D5 (make-elt "D5" 0 (list F3)))
>> (define D6 (make-elt "D6" 0 (list D4 D5)))
>>
>>
>> ;                D6
>> ;              /    \
>> ;             /      \
>> ;            D4      D5
>> ;          /    \     |
>> ;         /      \    |
>> ;        F1      F2   F3
>>
>> ;; The abstract fold/reduce function for Element.
>> (define (fold-elt c1 c2 b e)
>>  (local [(define (fn-for-element e)  ; -> X
>>            (c1 (elt-name e)    ;String
>>                (elt-data e)    ;Integer
>>                (fn-for-loe (elt-subs e))))
>>
>>          (define (fn-for-loe loe)    ; -> Y
>>            (cond [(empty? loe) b]
>>                  [else
>>                   (c2 (fn-for-element (first loe))
>>                       (fn-for-loe (rest loe)))]))]
>>    (fn-for-element e)))
>>
>> ;; String Element -> Integer or false
>> ;; Search the given tree for an element with the given name,
>> ;; produce data if found; false otherwise
>> (check-expect (find "F3" F1) #f)
>> (check-expect (find "F3" F3) 3)
>> (check-expect (find "D4" D4) 0)
>> (check-expect (find "D6" D6) 0)
>> (check-expect (find "F3" D4) #f)
>> (check-expect (find "F1" D4) 1)
>> (check-expect (find "F2" D4) 2)
>> (check-expect (find "F1" D6) 1)
>> (check-expect (find "F3" D6) 3)
>>
>> (define (find n elt)
>>  (local [(define (c1 name data loe)
>>            (if (string=? n name) data loe))]
>>  (fold-elt c1 ??? #f elt)))
>> -----
>>
>> So, what should I do in the place marked with "???"?
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Racket Users" group.
>> To unsubscribe from this group and stop receiving emails from it, send an
>> For more options, visit https://groups.google.com/d/optout
>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Racket Users" group.
> To unsubscribe from this group and stop receiving emails from it, send an