Category Archives: Racket

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:

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

Continuo da qui, copio qui.

Exercise 2.24: Suppose we evaluate the expression (list 1 (list 2 (list 3 4))). Give the result printed by the interpreter, the corresponding box-and-pointer structure, and the interpretation of this as a tree (as in Figure 2.6).

Dovrebbe essere semplice, per comodità ricopio le figure:

L’espressione viene valutata così:

e quindi

Le Corbusier schizzava malissimo (cit.), me too 😎
Ecco Bill the Lizard e sicp-ex.
Ma oggi vince DreWiki: I’m too lazy to do the graphs for the other two parts.

:mrgreen:

SICP – cap. 2 – Strutture gerarchiche – 29

Continuo da qui, copio qui.

The representation of sequences in terms of lists generalizes naturally to represent sequences whose elements may themselves be sequences. For example, we can regard the object ((1 2) 3 4) constructed by

(cons (list 1 2) (list 3 4))

as a list of three items, the first of which is itself a list, (1 2). Indeed, this is suggested by the form in which the result is printed by the interpreter. Figure 2.5 shows the representation of this structure in terms of pairs.

Another way to think of sequences whose elements are sequences is as trees. The elements of the sequence are the branches of the tree, and elements that are themselves sequences are subtrees. Figure 2.6 shows the structure in Figure 2.5 viewed as a tree.

Recursion is a natural tool for dealing with tree structures, since we can often reduce operations on trees to operations on their branches, which reduce in turn to operations on the branches of the branches, and so on, until we reach the leaves of the tree. As an example, compare the length procedure of 2.2.1 [qui] with the count-leaves procedure, which returns the total number of leaves of a tree:

ahemmm count-leaves –facciamo finta di averla già 😉

To implement count-leaves, recall the recursive plan for computing length:

  • Length of a list x is 1 plus length of the cdr of x.
  • Length of the empty list is 0.

count-leaves is similar. The value for the empty list is the same:

  • count-leaves of the empty list is 0.

But in the reduction step, where we strip off the car of the list, we must take into account that the car may itself be a tree whose leaves we need to count. Thus, the appropriate reduction step is

count-leaves of a tree x is count-leaves of the car of x plus count-leaves of the cdr of x.

Finally, by taking cars we reach actual leaves, so we need another base case:

  • count-leaves of a leaf is 1.

To aid in writing recursive procedures on trees, Scheme provides the primitive predicate pair?, which tests whether its argument is a pair. Here is the complete procedure:

(define (count-leaves x)
  (cond ((null? x) 0)  
        ((not (pair? x)) 1)
        (else (+ (count-leaves (car x))
                 (count-leaves (cdr x))))))

Note: The order of the first two clauses in the cond matters, since the empty list satisfies null? and also is not a pair.

Uh! e pensare che sembrava una cosa difficilissima 😯

:mrgreen:

SICP – cap. 2 – Mappare liste – esercizi – 28

Continuo da qui, con questo esercizio.

Exercise 2.23: The procedure for-each is similar to map. It takes as arguments a procedure and a list of elements. However, rather than forming a list of the results, for-each just applies the procedure to each of the elements in turn, from left to right. The values returned by applying the procedure to the elements are not used at all—for-each is used with procedures that perform an action, such as printing. For example,

for-each 
 (lambda (x) (newline) (display x))
 (list 57 321 88))

57
321
88

The value returned by the call to for-each (not illustrated above) can be something arbitrary, such as true. Give an implementation of for-each.

Forse i prof mi stanno tirando un –NO, ecco il mio compito (file es2.23.rkt):

(define nil '())

(define (my-print item)
  (display item)
  (newline))
  
(define (for-each fx lst)
  (define (iter things answer)
    (if (null? things)
        answer
        (iter (cdr things)
          (fx (car things)))))
    (iter lst nil))

OK (secondo me); adesso vedo i soliti nerds.

Bill the Lizard ha una versione più compatta e bella, rockz 🚀
sicp-ex è ancora meglio 🚀; diverse versioni di cui l’ultima cortissima (usa map):

Drewiki è diverso e usa let, non ancora visto.

In conclusione: risolta ma potevo fare meglio. Giustificazione (?): l’ho sviluppata mentalmente, pensando agli esercizi precedenti. Ma forse non è male non fossilizzarsi, verificare se vi sono altre vie 😊

:mrgreen:

SICP – cap. 2 – Mappare liste – esercizi – 27

Continuo da qui con gli esercizi, qui.

Exercise 2.22: Louis Reasoner tries to rewrite the first square-list procedure of Exercise 2.21 so that it evolves an iterative process

(define (square-list items)

  (define (iter things answer)
    (if (null? things)
        answer
        (iter (cdr things)
              (cons (square (car things))
                    answer))))
  (iter items nil))

Unfortunately, defining square-list this way produces the answer list in the reverse order of the one desired. Why?

Louis then tries to fix his bug by interchanging the arguments to cons:

(define (square-list items)
  (define (iter things answer)
    (if (null? things)
        answer
        (iter (cdr things)
              (cons answer
                    (square 
                     (car things))))))
  (iter items nil))

This doesn’t work either. Explain.

Intanto verifico, fidarsi è bene ma… 😊
La prima parte:

OK, il motivo è noto, vedi reverse dell’esercizio 2.18, qui.

La seconda parte:

Questa volta il problema è la cons:

ma, oltre a usare ' per list ho fatto ricorso a append non ancora definita dai prof.

Cosa fanno i nerds di riferimento?

Bill the Lizard produce la versione corretta –“would only require a small change“– della seconda versione:

(define (square-list items)
   (define (iter things answer)
     (if (null? things)
         answer
         (iter (cdr things)
               (append answer
                       (list (square (car things)))))))
   (iter items null))

ma anche lui usa append; mi viene il dubbio che fosse già stata definita, un giorno che mi sono distratto 😜
sicp-ex è molto sbrigativo,  Drewiki è identico a Bill (per la seconda parte).

:mrgreen:

SICP – cap. 2 – Mappare liste – esercizi – 26

Continuo da qui; adesso esercizio, qui.

Exercise 2.21: The procedure square-list takes a list of numbers as argument and returns a list of the squares of those numbers.

(square-list (list 1 2 3 4))
(1 4 9 16)

Here are two different definitions of square-list. Complete both of them by filling in the missing expressions:

(define (square-list items)
  (if (null? items)
      nil
      (cons ⟨??⟩ ⟨??⟩)))

(define (square-list items)
  (map ⟨??⟩ ⟨??⟩))

Non so se devo preoccuparmi 😜 ma mi sembra davvero solo ripetere quello già visto; provo, prima parte:

La versione con map, usando la map definita precedentemente:

nuovamente ho solo copiato quanto detto a lezione; perpluto 😜

Meglio controllare i nerds di riferimento: Bill the Lizard.

Sì 🚀  è OK. Bella l’osservazione che [i]n the second implementation we only need to think about the procedure that we want to apply to each element of the list and map takes care of the rest.

sicp-ex aggiunge ancora un’ulteriore versione più semplice, usando square 😄

È anche la soluzione proposta da Drewiki 😄; copiano? chi? 😄

:mrgreen:

SICP – cap. 2 – Mappare liste – 25

Continuo da qui, copiando qui.

One extremely useful operation is to apply some transformation to each element in a list and generate the list of results. For instance, the following procedure scales each number in a list by a given factor:

nil l’ho definito, non c’è in Racket.

We can abstract this general idea and capture it as a common pattern expressed as a higher-order procedure, just as in 1.3 [qui]. The higher-order procedure here is called map. map takes as arguments a procedure of one argument and a list, and returns a list of the results produced by applying the procedure to each element in the list (Scheme standardly provides a map procedure that is more general than the one described here):

Now we can give a new definition of scale-list in terms of map:

map is an important construct, not only because it captures a common pattern, but because it establishes a higher level of abstraction in dealing with lists. In the original definition of scale-list, the recursive structure of the program draws attention to the element-by-element processing of the list. Defining scale-list in terms of map suppresses that level of detail and emphasizes that scaling transforms a list of elements to a list of results.
The difference between the two definitions is not that the computer is performing a different process (it isn’t) but that we think about the process differently.
In effect, map helps establish an abstraction barrier that isolates the implementation of procedures that transform lists from the details of how the elements of the list are extracted and combined. Like the barriers shown in Figure 2.1, this abstraction gives us the flexibility to change the low-level details of how sequences are implemented, while preserving the conceptual framework of operations that transform sequences to sequences. Section 2.2.3 [prossimamente] expands on this use of sequences as a framework for organizing programs.

:mrgreen:

SICP – cap. 2 – Dati gerarchici e closure – esercizi – 24

Continuo da qui, sono qui.

Exercise 2.20: The procedures +, *, and list take arbitrary numbers of arguments. One way to define such procedures is to use define with dotted-tail notation. In a procedure definition, a parameter list that has a dot before the last parameter name indicates that, when the procedure is called, the initial parameters (if any) will have as values the initial arguments, as usual, but the final parameter’s value will be a list of any remaining arguments. For instance, given the definition

(define (f x y . z) ⟨body⟩)

the procedure f can be called with two or more arguments. If we evaluate

(f 1 2 3 4 5 6)

then in the body of f, x will be 1, y will be 2, and z will be the list (3 4 5 6). Given the definition

(define (g . w) ⟨body⟩)

the procedure g can be called with zero or more arguments. If we evaluate

(g 1 2 3 4 5 6)

then in the body of g, w will be the list (1 2 3 4 5 6).

Note:  To define f and g using lambda we would write
(define f (lambda (x y . z) ⟨body⟩))
(define g (lambda w ⟨body⟩))

Use this notation to write a procedure same-parity that takes one or more integers and returns a list of all the arguments that have the same even-odd parity as the first argument. For example,

(same-parity 1 2 3 4 5 6 7)
(1 3 5 7)

(same-parity 2 3 4 5 6 7)
(2 4 6)

Forse SICP è troppo impegnativo per me; o forse devo sviscerare il senso del testo. Ho provato a vedere se Racket (nella REPL) ha la dot-tail notation  e pare di no  NO, c’è, vedi più avanti. Allora cosa devo fare? Chissà se Bill the Lizard

OK, devo costruire la procedeura same-parity come se la notazione ci fosse.

Ma aspetta: la cosa non mi convince, provo a indagare

o, meglio ancora

e ovviamente

L’esercizio non era comunque semplice, vedi sicp-ex e Drewiki.

OK, adesso lo pubblico? devo essere onesto e raccontare quello che faccio o riportare la ricostruzione finale? Siccome il blog è mio e lo leggo solo io (kwasy) la prima opzione mi sembra quella giusta 😜

Ovviamente devo impegnarmi di più: i post di SICP sono impegnativi. Molto 👽

:mrgreen: