Category Archives: Racket

SICP – cap. 2 – Sequenze come interfacce convenzionali – 48 – esercizi

Continuo da qui, copio qui.

Exercise 2.39: Complete the following definitions of reverse (Exercise 2.18 [qui]) in terms of fold-right and fold-left from Exercise 2.38 [post precedente]:

(define (reverse sequence)
  (fold-right 
   (lambda (x y) ⟨??⟩) nil sequence))

(define (reverse sequence)
  (fold-left 
   (lambda (x y) ⟨??⟩) nil sequence))

Le due procedure fold-right e fold-left (anche se si potrebbero utilizzare quelle predefinite in Racket)

(define (fold-right op initial sequence)
   (if (null? sequence)
       initial
       (op (car sequence)
           (fold-right op initial (cdr sequence)))))

(define (fold-left op initial sequence)
  (define (iter result rest)
    (if (null? rest)
        result
        (iter (op result (car rest))
              (cdr rest))))
  (iter initial sequence))

Meglio seguire Bill the Lizard, ecco:

In fold-right the operator is applied to the car of the sequence and the result of a recursive call to fold-right. Just as we did in exercise 2.18, we can reverse the sequence using fold-right by appending the car of the sequence to the reverse of its cdr.

(define (reverse sequence)
   (fold-right (lambda (x y) (append y (list x))) null sequence))

In fold-left the operator is applied to the result sequence and the car of the unused elements in the initial sequence. Since the result sequence starts with an initial value of null, and we’re starting at the end of the sequence and working backwards anyway, we can just cons each element to the end of the result.

(define (reverse sequence)
   (fold-left (lambda (x y) (cons y x)) null sequence))

sicp-ex e Drewiki: tutti come Bill 😁

:mrgreen:

SICP – cap. 2 – Sequenze come interfacce convenzionali – 47 – esercizi

Continuo da qui, copio qui.

Exercise 2.38: The accumulate procedure is also known as fold-right, because it combines the first element of the sequence with the result of combining all the elements to the right. There is also a fold-left, which is similar to fold-right, except that it combines elements working in the opposite direction:

(define (fold-left op initial sequence)
  (define (iter result rest)
    (if (null? rest)
        result
        (iter (op result (car rest))
              (cdr rest))))
  (iter initial sequence))

What are the values of

(fold-right / 1 (list 1 2 3))
(fold-left  / 1 (list 1 2 3))
(fold-right list nil (list 1 2 3))
(fold-left  list nil (list 1 2 3))

Give a property that op should satisfy to guarantee that fold-right and fold-left will produce the same values for any sequence.

Intanto ricopio la procedura accumuate rinominandola fold-right

(define (fold-right op initial sequence)
   (if (null? sequence)
       initial
       (op (car sequence)
           (fold-right op initial (cdr sequence)))))

inoltre in Racket non è definito nil ma null.

Ed ecco:

OK, le due procedure danno risultati diversi. Allora… op dev’essere … proprio come dice Bill the Lizard: The property that will guarantee that fold-right and fold-left will produce the same values for any sequence is commutativity. You may remember the commutative property of both addition and multiplication from algebra. It’s the law that says that: A + B = B + A and A x B = B x A.
Subtraction and division are not commutative operations. The AND and OR operations in Boolean algebra are commutative.


OK anche sicp-ex e Drewiki.

Ripensandoci 😜 Racket ha le due procedure, com’era logico supporre:

Ripensandoci ancora: l’esercizio non è sul Lisp, non è sulla programmazione ma per vedere se l’allievo si applica e ragiona. Cosa che onestamente —ahemmm…– ci sono arrivato solo dopo ore, in viaggio con un caldo da solstizio, afa, condizionatore che non funziona e non si possono abbassare i finestrini. Devo affrontare diversamente SICP, demitizzarlo ma impegnarmi di più; chissà come facevano gli studenti; chissà come fanno adesso 😯

:mrgreen:

SICP – cap. 2 – Sequenze come interfacce convenzionali – 46 – esercizi

Continuo da qui, copio qui.

Exercise 2.37: Suppose we represent vectors v = (v_i) as sequences of numbers, and matrices m = (m_i j) as sequences of vectors (the rows of the matrix). For example, the matrix

is represented as the sequence ((1 2 3 4) (4 5 6 6) (6 7 8 9)). With this representation, we can use sequence operations to concisely express the basic matrix and vector operations. These operations (which are described in any book on matrix algebra) are the following:

We can define the dot product as

(define (dot-product v w)
  (accumulate + 0 (map * v w)))

Fill in the missing expressions in the following procedures for computing the other matrix operations. (The procedure accumulate-n is defined in Exercise 2.36 [post precedente]):

(define (matrix-*-vector m v)
  (map ⟨??⟩ m))

(define (transpose mat)
  (accumulate-n ⟨??⟩ ⟨??⟩ mat))

(define (matrix-*-matrix m n)
  (let ((cols (transpose n)))
    (map ⟨??⟩ m)))

Ricopio le procedure accumulate e accumulate-n

(define (accumulate op initial sequence)
   (if (null? sequence)
       initial
       (op (car sequence)
           (accumulate op initial (cdr sequence)))))

(define (accumulate-n op init seqs)
   (if (null? (car seqs))
       null
       (cons (accumulate op init (map car seqs))
             (accumulate-n op init (map cdr seqs)))))

Applicando accumulate-n ottengo

(define (matrix-*-vector m v)
   (map (lambda (row) (dot-product row v)) m))

transpose è un po’ da pensarci su, vedi Bill (a breve)

(define (transpose mat)
   (accumulate-n cons null mat))

Ancora peggio la moltiplicazione, lo schema dalla Wiki

e –OK, copio Bill– la procedura

(define (matrix-*-matrix m n)
   (let ((cols (transpose n)))
     (map (lambda (row) (matrix-*-vector cols row)) m)))

Raccolgo i codici nel file m2-37.rkt ed ecco

Ho utilizzato il codice di Bill the Lizard, migliore –secondo me– ma OK anche sicp-ex e Drewiki.

:mrgreen:

SICP – cap. 2 – Sequenze come interfacce convenzionali – 45 – esercizi

Continuo da qui, copio qui.

Exercise 2.36: The procedure accumulate-n is similar to accumulate except that it takes as its third argument a sequence of sequences, which are all assumed to have the same number of elements. It applies the designated accumulation procedure to combine all the first elements of the sequences, all the second elements of the sequences, and so on, and returns a sequence of the results. For instance, if s is a sequence containing four sequences, ((1 2 3) (4 5 6) (7 8 9) (10 11 12)), then the value of (accumulate-n + 0 s) should be the sequence (22 26 30). Fill in the missing expressions in the following definition of accumulate-n:

(define (accumulate-n op init seqs)
  (if (null? (car seqs))
      nil
      (cons (accumulate op init ⟨??⟩)
            (accumulate-n op init ⟨??⟩))))

Serve accumulate

(define (accumulate op initial sequence)
   (if (null? sequence)
       initial
       (op (car sequence)
           (accumulate op initial (cdr sequence)))))

L’esercizio è davvero semplice come sembra:

I miei nerds di riferimento: Bill the Lizard, sicp-ex e Drewiki.

:mrgreen:

SICP – cap. 2 – Sequenze come interfacce convenzionali – 44 – esercizi

Continuo da qui, copio qui.

Exercise 2.35: Redefine count-leaves from 2.2.2 [qui] as an accumulation:

(define (count-leaves t)
  (accumulate ⟨??⟩ ⟨??⟩ (map ⟨??⟩ ⟨??⟩)))

La definizione di count-leaves:

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

e quella di accumulate [qui]:

(define (accumulate op initial sequence)
  (if (null? sequence)
      initial
      (op (car sequence)
          (accumulate op 
                      initial 
                      (cdr sequence)))))

Quindi, seguendo Bill the Lizard: The enumerate-tree procedure “flattens out” a tree into a sequence of its leaves. Once we have the tree in the form of a sequence, we just need to define a function for the first argument of map. This function should simply return a 1 for any input. Here’s the complete (but very short) solution.

(define (count-leaves t)
   (accumulate + 0 (map (lambda (x) 1)
                        (enumerate-tree t))))

Al solito una volta vista è semplice e bella. Ma da solo non ci sono arrivato 😡

OK ma senza spiegazione sicp-ex.
Post sintetico anche per Drewiki.

:mrgreen:

SICP – cap. 2 – Sequenze come interfacce convenzionali – 43 – esercizi

Continuo da qui, copio qui.

Exercise 2.34: Evaluating a polynomial in Χ at a given value of Χ can be formulated as an accumulation. We evaluate the polynomial

using a well-known algorithm called Horner’s rule, which structures the computation as

In other words, we start with an, multiply by Χ, add an−1, multiply by Χ, and so on, until we reach a0.

Note: According to Knuth 1981, this rule was formulated by W. G. Horner early in the nineteenth century, but the method was actually used by Newton over a hundred years earlier. Horner’s rule evaluates the polynomial using fewer additions and multiplications than does the straightforward method of first computing anΧn, then adding an−1Χn−1, and so on. In fact, it is possible to prove that any algorithm for evaluating arbitrary polynomials must use at least as many additions and multiplications as does Horner’s rule, and thus Horner’s rule is an optimal algorithm for polynomial evaluation. This was proved (for the number of additions) by A. M. Ostrowski in a 1954 paper that essentially founded the modern study of optimal algorithms. The analogous statement for multiplications was proved by V. Y. Pan in 1966. The book by Borodin and Munro (1975). The Computational Complexity of Algebraic and Numeric Problems provides an overview of these and other results about optimal algorithms.

Fill in the following template to produce a procedure that evaluates a polynomial using Horner’s rule. Assume that the coefficients of the polynomial are arranged in a sequence, from a0 through an.

(define 
  (horner-eval x coefficient-sequence)
  (accumulate 
   (lambda (this-coeff higher-terms)
     ⟨??⟩)
   0
   coefficient-sequence))

For example, to compute 1 + 3 x + 5 x 3 + x 5 at x = 2 you would evaluate

(horner-eval 2 (list 1 3 0 5 0 1))

Copio Bill the Lizard che al solito spiega molto bene l’esercizio 🚀 😎

(define (horner-eval x coefficient-sequence)
   (accumulate (lambda (this-coeff higher-terms)
                 (+ (* x higher-terms) this-coeff))
               0
               coefficient-sequence))

serve accumulate come precedentemente definita

(define (accumulate op initial sequence)
   (if (null? sequence)
       initial
       (op (car sequence)
           (accumulate op initial (cdr sequence)))))

Meno chiara la soluzione di sicp-ex; interessante (ma dovrei studiarla meglio) la risposta di Drewiki.

:mrgreen:

SICP – cap. 2 – Sequenze come interfacce convenzionali – 42 – esercizi

Continuo da qui, copio qui.

Exercise 2.33: Fill in the missing expressions to complete the following definitions of some basic list-manipulation operations as accumulations:

(define (map p sequence)
  (accumulate (lambda (x y) ⟨??⟩) 
              nil sequence))

(define (append seq1 seq2)
  (accumulate cons ⟨??⟩ ⟨??⟩))

(define (length sequence)
  (accumulate ⟨??⟩ 0 sequence))

accumulate è stata definita nel post precedente, così

(define (accumulate op initial sequence)
  (if (null? sequence)
      initial
      (op (car sequence)
          (accumulate op 
                      initial 
                      (cdr sequence)))))

e può essere usata così

per cui è proprio quello che serve

map
prevede una procedura da applicare a tutti gli elementi della lista passata come secondo parametro, come nel terzo degli esempi di accumulate, per cui

append
proprio come viene subito da pensare, basta il cons delle due sequenze. Anzi no, c’è un quirk (come spega bene Bill), l’ordine delle sequenze dev’essere invertito

length
sembrava facile e invece (mai fidarsi del profs) accumulate opera sugli elementi della sequenza. Mi sono arreso –confesso– e ho copiato Bill:  How do we get it to just return the length of the sequence? We can do that by simply giving it an operation that will ignore each element of the sequence, and just increment the accumulated value.

I nerds di rifermento: Bill the Lizard, sicp-ex e Drewiki.
length è uguale per tutti; chissà se sono entanglate? 😉

Una nota per me: con la versione 6.9 di Racket in modalità interattiva la libreria xrepl viene caricata automaticamente per cui l’alias da me usato diventa un po’ ridondante ma l’abitudine…

:mrgreen:

SICP – cap. 2 – Operazioni in sequenza – 41

Continuo da qui, copio qui.

The key to organizing programs so as to more clearly reflect the signal-flow structure is to concentrate on the “signals” that flow from one stage in the process to the next. If we represent these signals as lists, then we can use list operations to implement the processing at each of the stages. For instance, we can implement the mapping stages of the signal-flow diagrams using the map procedure from 2.2.1 [qui]:

Filtering a sequence to select only those elements that satisfy a given predicate is accomplished by

(define (filter predicate sequence)
  (cond ((null? sequence) nil)
        ((predicate (car sequence))
         (cons (car sequence)
               (filter predicate 
                       (cdr sequence))))
        (else  (filter predicate 
                       (cdr sequence)))))

For example,

ho usato filter predefinito in Racket ma non ditelo a nessuno, nèh!

Accumulations can be implemented by

(define (accumulate op initial sequence)
  (if (null? sequence)
      initial
      (op (car sequence)
          (accumulate op 
                      initial 
                      (cdr sequence)))))

, il solito nil, con Racket dovrei ricordarmi di usare null.

All that remains to implement signal-flow diagrams is to enumerate the sequence of elements to be processed. For even-fibs, we need to generate the sequence of integers in a given range, which we can do as follows:

(define (enumerate-interval low high)
  (if (> low high)
      nil
      (cons low 
            (enumerate-interval 
             (+ low 1) 
             high))))

To enumerate the leaves of a tree, we can use (Note:  This is, in fact, precisely the fringe procedure from Exercise 2.28 [qui]. Here we’ve renamed it to emphasize that it is part of a family of general sequence-manipulation procedures.):

(define (enumerate-tree tree)
  (cond ((null? tree) nil)
        ((not (pair? tree)) (list tree))
        (else (append 
               (enumerate-tree (car tree))
               (enumerate-tree (cdr tree))))))

Now we can reformulate sum-odd-squares and even-fibs [post precedente] as in the signal-flow diagrams. For sum-odd-squares, we enumerate the sequence of leaves of the tree, filter this to keep only the odd numbers in the sequence, square each element, and sum the results:

(define (sum-odd-squares tree)
  (accumulate 
   +
   0
   (map square
        (filter odd?
                (enumerate-tree tree)))))

For even-fibs, we enumerate the integers from 0 to n, generate the Fibonacci number for each of these integers, filter the resulting sequence to keep only the even elements, and accumulate the results into a list:

(define (even-fibs n)
  (accumulate 
   cons
   nil
   (filter even?
           (map fib
                (enumerate-interval 0 n)))))

The value of expressing programs as sequence operations is that this helps us make program designs that are modular, that is, designs that are constructed by combining relatively independent pieces. We can encourage modular design by providing a library of standard components together with a conventional interface for connecting the components in flexible ways.

Modular construction is a powerful strategy for controlling complexity in engineering design. In real signal-processing applications, for example, designers regularly build systems by cascading elements selected from standardized families of filters and transducers. Similarly, sequence operations provide a library of standard program elements that we can mix and match. For instance, we can reuse pieces from the sum-odd-squares and even-fibs procedures in a program that constructs a list of the squares of the first n + 1 Fibonacci numbers:

(define (list-fib-squares n)
  (accumulate 
   cons
   nil
   (map square
        (map fib
             (enumerate-interval 0 n)))))

We can rearrange the pieces and use them in computing the product of the squares of the odd integers in a sequence:

(define 
  (product-of-squares-of-odd-elements
   sequence)
  (accumulate 
   *
   1
   (map square (filter odd? sequence))))

We can also formulate conventional data-processing applications in terms of sequence operations. Suppose we have a sequence of personnel records and we want to find the salary of the highest-paid programmer. Assume that we have a selector salary that returns the salary of a record, and a predicate programmer? that tests if a record is for a programmer. Then we can write

(define 
  (salary-of-highest-paid-programmer
   records)
  (accumulate 
   max
   0
   (map salary
        (filter programmer? records))))

These examples give just a hint of the vast range of operations that can be expressed as sequence operations.

Note: Richard Waters (1979) developed a program that automatically analyzes traditional Fortran programs, viewing them in terms of maps, filters, and accumulations. He found that fully 90 percent of the code in the Fortran Scientific Subroutine Package fits neatly into this paradigm. One of the reasons for the success of Lisp as a programming language is that lists provide a standard medium for expressing ordered collections so that they can be manipulated using higher-order operations. The programming language APL owes much of its power and appeal to a similar choice. In APL all data are represented as arrays, and there is a universal and convenient set of generic operators for all sorts of array operations.

Sequences, implemented here as lists, serve as a conventional interface that permits us to combine processing modules. Additionally, when we uniformly represent structures as sequences, we have localized the data-structure dependencies in our programs to a small number of sequence operations. By changing these, we can experiment with alternative representations of sequences, while leaving the overall design of our programs intact. We will exploit this capability  in 3.5  [prossimamente], when we generalize the sequence-processing paradigm to admit infinite sequences.

:mrgreen:

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: