Category Archives: SICP

SICP – cap. 2 – Sequenze come interfacce convenzionali – 40

Continuo da qui, copio qui.

Sequenze come interfacce convenzionali
In working with compound data, we’ve stressed how data abstraction permits us to design programs without becoming enmeshed in the details of data representations, and how abstraction preserves for us the flexibility to experiment with alternative representations. In this section, we introduce another powerful design principle for working with data structures—the use of conventional interfaces.

In 1.3 [qui] we saw how program abstractions, implemented as higher-order procedures, can capture common patterns in programs that deal with numerical data. Our ability to formulate analogous operations for working with compound data depends crucially on the style in which we manipulate our data structures. Consider, for example, the following procedure, analogous to the count-leaves procedure of 2.2.2 [qui], which takes a tree as argument and computes the sum of the squares of the leaves that are odd:

(define (sum-odd-squares tree)
  (cond ((null? tree) 0)
        ((not (pair? tree))
         (if (odd? tree) (square tree) 0))
        (else (+ (sum-odd-squares 
                  (car tree))
                 (sum-odd-squares 
                  (cdr tree))))))

On the surface, this procedure is very different from the following one, which constructs a list of all the even Fibonacci numbers fib(k) , where k is less than or equal to a given integer n:

(define (even-fibs n)
  (define (next k)
    (if (> k n)
        nil
        (let ((f (fib k)))
          (if (even? f)
              (cons f (next (+ k 1)))
              (next (+ k 1))))))
  (next 0))

even-fibs richiede un po’ d’attenzione, ecco

Despite the fact that these two procedures are structurally very different, a more abstract description of the two computations reveals a great deal of similarity. The first program

  • enumerates the leaves of a tree;
  • filters them, selecting the odd ones;
  • squares each of the selected ones; and
  • accumulates the results using +, starting with 0.

The second program

  • enumerates the integers from 0 to n ;
  • computes the Fibonacci number for each integer;
  • filters them, selecting the even ones; and
  • accumulates the results using cons, starting with the empty list.

A signal-processing engineer would find it natural to conceptualize these processes in terms of signals flowing through a cascade of stages, each of which implements part of the program plan, as shown in Figure 2.7. In sum-odd-squares, we begin with an enumerator, which generates a “signal” consisting of the leaves of a given tree. This signal is passed through a filter, which eliminates all but the odd elements. The resulting signal is in turn passed through a map, which is a “transducer” that applies the square procedure to each element. The output of the map is then fed to an accumulator, which combines the elements using +, starting from an initial 0. The plan for even-fibs is analogous.

Unfortunately, the two procedure definitions above fail to exhibit this signal-flow structure. For instance, if we examine the sum-odd-squares procedure, we find that the enumeration is implemented partly by the null? and pair? tests and partly by the tree-recursive structure of the procedure. Similarly, the accumulation is found partly in the tests and partly in the addition used in the recursion. In general, there are no distinct parts of either procedure that correspond to the elements in the signal-flow description. Our two procedures decompose the computations in a different way, spreading the enumeration over the program and mingling it with the map, the filter, and the accumulation. If we could organize our programs to make the signal-flow structure manifest in the procedures we write, this would increase the conceptual clarity of the resulting code.

Continua, panicosamente 😯

:mrgreen:

SICP – cap. 2 – Mappare con gli alberi – 39 – esercizi

Continuo da qui, copio qui.

Exercise 2.32: We can represent a set as a list of distinct elements, and we can represent the set of all subsets of the set as a list of lists. For example, if the set is (1 2 3), then the set of all subsets is (() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3)). Complete the following definition of a procedure that generates the set of subsets of a set and give a clear explanation of why it works:

(define (subsets s)
  (if (null? s)
      (list nil)
      (let ((rest (subsets (cdr s))))
        (append rest (map <!--?? > rest)))))

Uhmmm… mica semplice come sembra. Tanto che anche Bill the Lizard rimanda alla Wiki (come faremmo senza la Wiki?), per l’algoritmo.
Non ci sono arrivato da solo, il mio tentativo, soluzione brutale, non funziona, ecco Bill:

This would be a tough problem in other languages, but it’s really terse in Scheme. dice sicp-ex 😯 Riporta poi la stessa soluzione di prima, con spiegazioni aggiuntive, da vedere.
Una spiegazione simile anche con Drewiki.

Sono troppo legato ai programmi imperativi, dal Fortran a Python, mi manca la capacità di astrarre.

:mrgreen:


SICP – cap. 2 – Mappare con gli alberi – 38 – esercizi

Katinka Matson

Continuo da qui, copio qui.

Exercise 2.31: Abstract your answer to Exercise 2.30 [post citato] to produce a procedure tree-map with the property that square-tree could be defined as

(define (square-tree tree) 
  (tree-map square tree))

intanto la square-tree dell’esercizio precedente

(define (square-tree tree)
   (cond ((null? tree) null)
         ((not (pair? tree)) (* tree tree))
         (else (cons (square-tree (car tree))
                     (square-tree (cdr tree))))))

e la procedura square:

(define (square x)
   (* x x))

tree-map deve applicare square a ogni elemento di tree; per cui

(define (tree-map proc tree)
   (cond ((null? tree) null)
          ((not (pair? tree)) (proc tree))
          (else (cons (tree-map proc (car tree))
                      (tree-map proc (cdr tree))))))

Raccolgo square e tree-map nel file tree-map.rkt ed ottengo:

Inizialmente mi sembrava panicosa ma era solo da leggere attentamente, e astrarre 😜 Poi tutto viene automaticamente: è la stessa procedura dell’esercizio precedente —kwasy 😉

Uh! esemplare Bill the Lizard.
Diverse varianti per sicp-ex.
Anche Drewiki ha seguito la via normale.

:mrgreen:

SICP – cap. 2 – Mappare con gli alberi – 37 – esercizi

Continuo da qui, copio qui.

Exercise 2.30: Define a procedure square-tree analogous to the square-list procedure of Exercise 2.21 [qui]. That is, square-tree should behave as follows:

(square-tree
 (list 1
       (list 2 (list 3 4) 5)
       (list 6 7)))
(1 (4 (9 16) 25) (36 49))

Define square-tree both directly (i.e., without using any higher-order procedures) and also by using map and recursion.

Dopo aver visto la soluzione di Bill the Lizard mi sono reso conto che sono ancora molto niubbo; metto la sua soluzione (bt.rkt):

; direct implementation
(define (square-tree-d tree)
   (cond ((null? tree) null)
         ((not (pair? tree)) (* tree tree))
         (else (cons (square-tree-d (car tree))
                     (square-tree-d (cdr tree))))))

; using map and recursion
(define (square-tree-mr tree)
   (map (lambda (sub-tree)
          (if (pair? sub-tree)
              (square-tree-mr sub-tree)
              (* sub-tree sub-tree)))
        tree))

Sì, però hai copiato 👿 — sì 😡

La soluzione di sicp-ex è meno bella, più simile alla mia.
DreWiki è simile a Bill.

Memo per me: devo impegnarmi di più o mi bocciano 😡

:mrgreen:

SICP – cap. 2 – Mappare con gli alberi – 36

Continuo da qui, copio qui.

Just as map is a powerful abstraction for dealing with sequences, map together with recursion is a powerful abstraction for dealing with trees. For instance, the scale-tree procedure, analogous to scale-list of 2.2.1 [qui], takes as arguments a numeric factor and a tree whose leaves are numbers. It returns a tree of the same shape, where each number is multiplied by the factor. The recursive plan for scale-tree is similar to the one for count-leaves:

(define (scale-tree tree factor)

  (cond ((null? tree) nil)
        ((not (pair? tree)) 
         (* tree factor))
        (else
         (cons (scale-tree (car tree) 
                           factor)
               (scale-tree (cdr tree) 
                           factor)))))

(scale-tree (list 1 
                  (list 2 (list 3 4) 5) 
                  (list 6 7))
            10)

Ahemmm… in Racket occorre definire –al solito– nil.

Another way to implement scale-tree is to regard the tree as a sequence of sub-trees and use map. We map over the sequence, scaling each sub-tree in turn, and return the list of results. In the base case, where the tree is a leaf, we simply multiply by the factor:

(define (scale-tree tree factor)
  (map (lambda (sub-tree)
         (if (pair? sub-tree)
             (scale-tree sub-tree factor)
             (* sub-tree factor)))
       tree))

Many tree operations can be implemented by similar combinations of sequence operations and recursion.

Chissà cosa  ci  mi aspetta 😊

:mrgreen:

SICP – cap. 2 – Strutture gerarchiche – 35 – esercizi

Continuo da qui, copio qui.

Exercise 2.29: A binary mobile consists of two branches, a left branch and a right branch. Each branch is a rod of a certain length, from which hangs either a weight or another binary mobile. We can represent a binary mobile using compound data by constructing it from two branches (for example, using list):

(define (make-mobile left right)
  (list left right))

A branch is constructed from a length (which must be a number) together with a structure, which may be either a number (representing a simple weight) or another mobile:

(define (make-branch length structure)
  (list length structure))
  • Write the corresponding selectors left-branch and right-branch, which return the branches of a mobile, and branch-length and branch-structure, which return the components of a branch.
  • Using your selectors, define a procedure total-weight that returns the total weight of a mobile.
  • A mobile is said to be balanced if the torque applied by its top-left branch is equal to that applied by its top-right branch (that is, if the length of the left rod multiplied by the weight hanging from that rod is equal to the corresponding product for the right side) and if each of the submobiles hanging off its branches is balanced. Design a predicate that tests whether a binary mobile is balanced.
  • Suppose we change the representation of mobiles so that the constructors are
(define (make-mobile left right)
  (cons left right))

(define (make-branch length structure)
  (cons length structure))

How much do you need to change your programs to convert to the new representation?

Uh… e se… sì, dai 😊 copio tutto Bill the Lizard.

The following constructors are provided, giving us a representation of binary mobiles held together with the list procedure:

(define (make-mobile left right)
  (cons left right))

(define (make-branch length structure)
  (cons length structure))

Our first task is to write the corresponding selectors left-branch and right-branch, which return the branches of a mobile, and branch-length and branch-structure, which return the components of a branch.

(define (left-branch mobile)
   (car mobile))

(define (right-branch mobile)
   (car (cdr mobile)))

(define (branch-length branch)
   (car branch))

(define (branch-structure branch)
   (car (cdr branch)))

Next we need to define a procedure total-weight that returns the weight of an entire mobile. The total weight of a mobile is just the sum of the left branch and the right branch. The weight of a branch is defined recursively if the branch is itself a mobile, or just returned if the branch holds a single weight.

(define (branch-weight branch)
   (if (pair? (branch-structure branch))
       (total-weight (branch-structure branch))
       (branch-structure branch)))

(define (total-weight mobile)
   (+ (branch-weight (left-branch mobile))
      (branch-weight (right-branch mobile))))

Note how branch-weight and total-weight call each other recursively. The recursion reaches a base case when a weight (leaf node) is encountered.

A mobile is said to be balanced if the torque applied by its top-left branch is equal to that applied by its top-right branch (that is, if the length of the left rod multiplied by the weight hanging from that rod is equal to the corresponding product from the right side) and if each of the sub-mobiles hanging off its branches is balanced. Our next task is to design a predicate procedure that tests whether a binary mobile is balanced.

First we’ll need a simple procedure for calculating the torque of a branch from the definition above.

(define (branch-torque branch)
   (* (branch-length branch)
      (branch-weight branch)))

Now we can use the same mutual recursion pattern we used to find the total weight of a mobile to write procedures to determine if a mobile and its branches are balanced.

(define (branch-balanced? branch)
   (if (pair? (branch-structure branch))
       (balanced? (branch-structure branch))
       true))

(define (balanced? mobile)
   (and (= (branch-torque (left-branch mobile))
           (branch-torque (right-branch mobile)))
        (branch-balanced? (left-branch mobile))
        (branch-balanced? (right-branch mobile))))

Raccolgo tutto il codice nel file bm.rkt.

Before we go on to the last step, this would be a good spot to test what we’ve done so far. The simplest mobile we can make has two branches with simple weights. Let’s define two of those (one balanced and one unbalanced) and run a few simple tests.

Now we can create a more complicated mobile by combining the two above.

For one last test case, let’s try to make a balanced mobile that has mobile a above on a rod of length 10 on the left branch, and a weight of 5 on the right branch. What would the length of the rod on the right need to be in order to balance the entire mobile?

The torque on the left is the total weight of mobile a multiplied by the length, so 6 x 10 gives us a torque of 60. In order to balance the mobile we need the same torque on the right. Since the right side weight is only 5, we’d need a rod of length 60 / 5 = 12 on the right for the mobile to be balanced.

Finally, we’re asked how much we’d need to change our programs if the original constructors were changed to the following:

(define (make-mobile left right)
   (cons left right))

(define (make-branch length structure)
   (cons length structure))

The only difference is the use of cons to glue the pieces of the mobile and its branches together instead of list. Since only the constructor and accessor procedures know anything about the underlying structure of a mobile, only the accessors would need to change. In this case only the right-branch and branch-structure procedures are affected.

(define (right-branch mobile)
   (cdr mobile))

(define (branch-structure branch)
   (cdr branch))

This is a great benefit of layering abstractions.

You can test out this new implementation using the same mobiles we defined above.

😁 OK, Bill è promosso (cum laude), io espulso. Ma era davvero impegnativo.

Anche sicp-ex è OK come pure Drewiki.

Dov’è il cappello dell’asino? (tutto per me, sigh!).

:mrgreen:

SICP – cap. 2 – Strutture gerarchiche – 34 – esercizi

Continuo da qui, copio qui.

Exercise 2.28: Write a procedure fringe that takes as argument a tree (represented as a list) and returns a list whose elements are all the leaves of the tree arranged in left-to-right order. For example,

(define x 
  (list (list 1 2) (list 3 4)))

(fringe x)
(1 2 3 4)

(fringe (list x x))
(1 2 3 4 1 2 3 4)

Questo esercizio l’ho risolto (kwasy) mentalmente 😎
Cioè no, non esattamente ma dopo averlo letto attentamente mi sono messo a fare altro, ripensandoci nei momenti di pausa. Pare funzioni.
non è difficile, fringe dev’essere ricorsiva da applicare al cdr della lista. E anche al car se questo è una  lista  pair.

append è una procedurea built-in di Racket (e Scheme), non serve usare quella precedentemente definita dai prof. Il mio codice è OK ma quello di Bill the Lizard è più bello, questo: (fringe.rkt):

(define (fringe tree)
  (cond ((null? tree) null)
        ((not (pair? tree)) (list tree))
        (else (append (fringe (car tree))
                      (fringe (cdr tree))))))

sicp-ex ha diverse versioni, una mooolto simile alla mia 😊
Quasi lo stesso per Drewiki 😊

Forse l’esercizio era troppo semplice; o forse il pensarci su per un po’ funziona 😜

:mrgreen:

SICP – cap. 2 – Strutture gerarchiche – 33 – esercizi

Continuo da qui, copio qui.

Exercise 2.27: Modify your reverse procedure of Exercise 2.18 [qui] to produce a deep-reverse procedure that takes a list as argument and returns as its value the list with its elements reversed and with all sublists deep-reversed as well. For example,

(define x 
  (list (list 1 2) (list 3 4)))

x
((1 2) (3 4))

(reverse x)
((3 4) (1 2))

(deep-reverse x)
((4 3) (2 1))

L’esercizio 2.18 non è che l’abbia affrontato bene, anzi tutt’altro 😡
Ma la soluzione (copiata) è bellissima:

Intanto ecco

funziona per le liste flat, come ovvio 😎
Esiste il predicato list? ma chissà se si può usare? Non mi sembra che se ne sia parlato ma sono anche distratto perché mi occupo di SICP solo di tanto in tanto, purtroppo. C’è pair? e di questo se ne è parlato a lezione.

Sì, si può (deve?) usare pair? 😁
Poi –solo per me– pair? differisce da list? e se sì in cosa? Da indagare 😊

La soluzione di Bill the Lizard è esemplare; la faccio mia 😜 (file dep-rev.rkt):

(define (reverse items)
  (if (null? items)
     items
     (append (reverse (cdr items)) (list (car items)))))

(define (deep-reverse items)
  (cond ((null? items) null)
        ((pair? (car items))
         (append (deep-reverse (cdr items))
                 (list (deep-reverse (car items)))))
        (else
         (append (deep-reverse (cdr items))
                 (list (car items))))))

Ho usato la procedura append di Racket; in alternativa a quella definita dai profs.

sicp-ex ha diverse varianti, di cui una brevissima, da testare:


OK 🚀 ottima, anche se da costruire con carta e matita (e gomma) per capire come funziona.
Non tutte le soluzioni lì proposte funzionano, controllare sempre per casi diversi da quelli proposti dai profs.

Buona anche la versione di DreWiki.

:mrgreen:

SICP – cap. 2 – Strutture gerarchiche – 32 – esercizi

Continuo da qui, copio qui.

Exercise 2.26: Suppose we define x and y to be two lists:

(define x (list 1 2 3))
(define y (list 4 5 6))

What result is printed by the interpreter in response to evaluating each of the following expressions:

(append x y)
(cons x y)
(list x y)

Esercizio atipico; verifica se siamo stati attenti alle lezioni precedenti. Davvero mi sarebbe piaciuto tantissimo seguire questo corso in classe, quando ero giovane. Cioè allora non c’era ma non è una scusa sufficiente 😜
Senza aprire la REPL (davvero, parola di Giovane Marmotta (emerita)):

(1 2 3 4 5 6)
((1 2 3) 4 5 6)
((1 2 3) (4 5 6))

Verifico

Vedo i miei nerds.
Bill the Lizard spiega bene:
The append procedure takes the elements from two lists and produces a new list. When given two lists as parameters, the cons procedure returns a list whose first element is the first parameter list and whose remaining elements are the elements of the second list (we saw this at the beginning of section 2.2.1 Representing Sequences [qui]). Finally the list procedure simply wraps its parameters in a new list without doing any merge or append operations on them. The returned list just has two lists as its elements.
Bill rockz! 🚀, gli altri nerds questa volta di meno, allora manco li cito 😯

:mrgreen:

SICP – cap. 2 – Strutture gerarchiche – 31 – esercizi

Continuo da qui, copio qui.

Exercise 2.25: Give combinations of cars and cdrs that will pick 7 from each of the following lists:

(1 3 (5 7) 9)
((7))
(1 (2 (3 (4 (5 (6 7))))))

Uhmmm…. spiazzante 😯 cioè so farlo (un po’ per tentativi per la terza) ma non so se è quello che mi viene chiesto; comunque ecco

Adesso corro a vedere i miei nerds di riferimento.

Bill the Lizard, sicp-ex e Drewiki. , OK –a parte che mi sono semplificato il compito usando quote globalmente per le liste date. Il problema mio è che applico cose che per SICP sono il futuro; sono troppo vecchio 😡

:mrgreen: