Capítulo 1 :

A Linguagem Scheme

1.1 : Notação Pré-fixada

1. 2+3
2. 8/2
3. 4
4. 4.2 + 3.8
5. 2 × 4+3
6. 2+4 × 3
7. (2+4) × 3
8. 9 × (5-2)
9. sin 3.1415
10. 1+2+3
11. 1+2+3+4+5+6+7+8+9
12. 1 × 2 × 3 × 4 × 5 × 6 × 7 × 8 × 9
13. (1+2+3+4+5) - 6
14. (2+4) × (3+5)
15. (9-5) × (8-3)
16. (9/3) + (3*2)
17. sin 4.5 + cos 3.7
18. log 4.5 + log 3.2

1. (+ 3 2)
2. (- 9 5)
3. (+ 5 (/ 8 2))
4. (* 3.1 (+ 2 5.4))
5. (sin 3.14)
6. (* 2 -0.7 5)
7. (* (+ 3 4) 2)
8. (+ 4 (* 5 (/ 15 3)))
9. (+ (* (/ 15 3) 5) 4.5)
10. (* (+ 2 3) (+ 4 5))
11. (+ (/ 27 3) (* 3 2))
12. (* (+ 5 (+ 2 3)) 4)
13. (* (+ (+ 2 3) 4) (sin 5))
14. (/ (* (+ 8 a) (- b 4)) 2)
15. (/ (* (+ (- (+ 7 6) 5) 4) 3) 2)
16. (sin (* 2 x))
17. (+ (sin x) (cos x))
18. (sin (+ x (cos x)))

1. 4 ÷ 2
2. 5 ÷ 2
3. 1 ÷ 2
4. 1 mod 2
5. 20 mod 3
6. (5/2)-(5 ÷ 2)
7. (1345 ÷ 17) × 17 + (1345 mod 17)

1.2 : Um pouco de Sintaxe

Tudo que escrevemos em Scheme é chamado genericamente de expressão S, ou mais simplesmente expressão. As expressões que escrevemos em Scheme podem ser classificadas em dois tipos: átomos e listas. Os átomos podem ser de três tipos (por enquanto): numerais, por exemplo 4, -3.56; textos (strings, em inglês), que são sempre escritos entre aspas, como "Um exemplo de texto"; e símbolos, por exemplo a, define, nil?, +. Uma lista, por sua vez, é uma sequência de expressões entre parênteses, separadas por espaços; por exemplo (+ 3 4), (define a (+ 3 x)), (3 4 5), (display "alo mundo") e ((3 4) (2 3) () ((9) +)).

Exercício 1.4: Quais dos exemplos a seguir não são expressões sintaticamente corretas? Por quê?

1. (a b
2. ()
3. (((a)))
4. a b
5. (a b) c
6. (a b (c))
7. "(a b"
8. a b)
9. (((a b) c) (d))

Na sintaxe de numerais, vale a pena observar o uso do ponto decimal (como em inglês), ao invés da vírgula, e a possibilidade de usar notação científica para números muito grandes ou muito pequenos. Com essa notação, um valor como 3.5 × 10^{- 7} pode ser escrito como 3.5e-7.

Em geral, espaços entre os diversos símbolos de uma expressão só são relevantes para separar um símbolo de outro. Assim, as expressões abaixo são equivalentes:

(a b (c)) ( a b ( c) )

enquanto essas não são:

(a b (c)) (ab (c))

pois a b é interpretado como dois símbolos seguidos, enquanto ab é considerado como um único símbolo. Neste texto, apenas por convenção, vamos usar apenas um único espaço entre duas expressões seguidas; assim, escreveremos (a b (c d)), e não ( a b( c d ) ). Qualquer expressão pode ser quebrada em várias linhas; para o interpretador, uma mudança de linha equivale a um espaço em branco. Em geral, o uso de quebras de linha pode ajudar na leitura de expresões mais complexas.

Finalmente, podemos comentar expressões. Por enquanto, como estamos usando a linguagem apenas como uma calculadora, comentários não têm muita utilidade. Mas mais adiante, quando passarmos a definir funções mais complexas, comentários passam a ser uma importante forma de colocarmos explicações adicionais. Um comentário é qualquer texto colocado em uma linha após um ponto-e-vírgula (`;'), e é totalmente ignorado pelo interpretador.

1.3 : Um pouco de Semântica

• Um numeral resulta no número correspondente. Por exemplo, 4 resulta em 4.
• Um texto resulta no próprio texto. Por exemplo, "Luiz Silva" resulta em "Luiz Silva".
• Um símbolo resulta no valor associado a ele no ambiente, através de um define ou let (que iremos tratar em breve).
• O valor de uma lista já é um pouco mais complicado. Primeiro calculamos o valor de cada elemento da lista. O valor do primeiro elemento deve ser uma função, que será aplicada aos outros valores. A lista é então substituída (reescrita) pelo resultado da função.

(+ (* 8 -5) 7.3 (* 2 7.3)) (+ -40 7.3 (* 2 7.3))

(+ (* 8 -5) 7.3 (* 2 7.3)) (+ (* 8 -5) 7.3 14.6)

1. (quote a)
2. (quote (+ 3 5))
3. (+ 3 5)
4. (quote (sin (+ 3.45 (* 5.65 23.4))))
5. (quote (mesa cadeira piso))
6. (quote 4.5)

1. 'a
2. '(a b c)
3. '(a 'b c)
4. '(a (b) (c d))
5. '(* (+ 3 2) (- 9 8))

1.4 : Definições

{n₁ v₁,n₂ v₂,..., n_n v_n}

      (define aro 28)
      (define arco (+ (* aro 3) 5))

{aro 28, arco 89}

1. (define pi 3.1415927)
2. (define raio 24.56)
3. (define area (* pi (* raio raio)))
4. (define nome "Maria Clara")
5. (define a +)

Uma outra forma de darmos nomes a valores é com a construção let. Essa construção permite darmos nomes locais a valores. Ao contrário de um define, que define nomes globais, esses nomes só são válidos dentro da expressão onde eles são definidos, não interferindo com outras partes de um programa. A sintaxe geral de um let é:

      (let ([nome1 exp1]
              ...
            [nomen expn])
              corpo)

observação: na construção acima, e em algumas outras construções ao longo do texto, iremos usar colchetes [...] no lugar de parênteses (...), de modo a deixar mais claro sua estrutura. Entretanto, em qualquer uso real esses colchetes devem ser substituídos por parênteses.

Quando executamos um let, primeiro todas as expressões exp_i são calculadas, e associadas aos respectivos nomes, criando um ambiente local. Em seguida, o corpo é calculado, trocando-se cada ocorrência de nome_i pelo valor correspondente no ambiente.

---

Exemplo 1.3: Para calcularmos o valor da expressão

      (let ([x (+ 9 8)]     ;lembre-se: trocar [...] por (...)
            [y (sin 10)])
         (+ (* x y) y))

executamos

(let ((x (+ 9 8)) (y (sin 10))) (+ (* x y) y))
soma e seno
(let ((x 17) (y -0.544021)) (+ (* x y) y))
corpo do let
(+ (* x y) y) {x 17,y -0.544021}
ambiente local
(+ (* 17 -0.544021) -0.544021)
aritmética
-9.79238 resultado final

A notação

(+ (* x y) y) {x 17,y -0.544021}

usada no traço acima, significa que a expressão (+ (* x y) y) deve ser executada no ambiente local {x 17,y -0.544021}.

---

É importante lembrar que as variáveis definidas em um let só podem ser usadas no corpo do let; em particular, uma variável não pode ser usada na definição de outra variável, como na expressão abaixo:

      ; código incorreto!
      (let ((x (sin 10))
            (y (* x (+ x 10))))
           (- x y))

Se necessário, tais situações podem ser tratadas com lets aninhados, como no exemplo abaixo.

---

Exemplo 1.4: O corpo de um let pode conter outra expressão let, como no caso abaixo:

      (let ((x (sin 10)))
           (let ((y (* x (+ x 10))))
             (- x y)))

O traço dessa expressão segue a mesma regra do let:

(let ((x (sin 10))) (let ((y (* x (+ x 10)))) (- x y)))
seno
(let ((x -0.544)) (let ((y (* x (+ x 10)))) (- x y)))
corpo do 1^o let
(let ((y (* x (+ x 10)))) (- x y)) {x -0.544}
valor de x
(let ((y (* -0.544 (+ -0.544 10)))) (- -0.544 y))
aritmética
(let ((y -5.14425)) (- -0.544 y))
corpo do let
(- -0.544 y) {y -5.14425}
valor de y
(- -0.544 -5.14425)
aritmética
4.60023

---

Os principais usos da construção let são na simplificação de expressões muito complexas e para colocar em evidência sub-expressões comuns. Por exemplo, considere a expressão

(- (sin (+ a (* b c))) (cos (+ a (* b c))))

Com esse código, não só escrevemos duas vezes a sub-expressão (+ a (* b c)), como fazemos o computador calculá-la duas vezes. Se reescrevermos a expressão como

(let ((x (+ a (* b c)))) (- (sin x) (cos x)))

eliminamos os dois problemas.

Exercício 1.8: Calcule o valor das expressões abaixo:

1. (let ((x 10) (y 5)) (* (+ x y) (- x y)))
2. (let ((x (sin 5))) (* x x))
3. (+ 10 (let ((x (sin 5))) (* x x)))
4. (let ((x 10)) (let ((y (+ x 5))) (* x y)))

5.       (let ((delta (- (* b b) (* 4 a c)))
               (dois-a (* 2 a)))
                 (/ (+ (- b) (sqrt delta)) dois-a))
   

   assumindo que a, b e c estejam definidos como -1, 1 e 2 respectivamente.

{x 5, y 10}

1. (+ x (let ((x (sin 5))) (* x x)))
2. (- (let ((x (sin 5))) (* x y)) x)

1.5 : Listas

(cons 3 '(4 5)) (3 4 5)

(cons (cons 4 (cons 5 '())) (cons 2 '())) ((4 5) 2)

1. (cons 2 '())
2. (cons 1 (cons 2 '()))
3. (cons 1 (cons 2 (cons 3 '())))
4. (cons 'China '(Uruguai Grecia))
5. (cons '() '())
6. (cons '() '(a b c))
7. (cons '(a b c) '(d))
8. (let ((x 'Paris) (y '(Roma Berlin))) (cons x y))
9. (let ((x 'Paris) (y '(Roma Berlin))) (cons 'x y))
10. (let ((n '())) (cons (cons 3 n) n))
11. (cons 2 (let ((x '())) (cons x x)))
12. (let ((x '(y z))) (cons 'x x))

1. (2 4)
2. ((2 4))
3. (((2 4)))
4. ((2 4) (3 5))

(car (cons a b)) a

(cdr (cons a b)) b

(cons (car x) (cdr x)) x

1. (car '(a b))
2. (cdr '(a b))
3. (car '(a))
4. (car '((a)))
5. (cdr '(a))
6. (cdr '((a)))
7. (let ((l '(lua sol marte))) (cdr l))
8. (let ((l '(lua sol marte))) (car (cdr l)))
9. (let ((l '(lua sol marte))) (car (cdr (cdr l))))
10. (let ((lista '((a1 b1) (a2 b2) (a3 b3)))) (car (cdr (car lista))))

(car (cdr l)) (cadr l)

(car (car l)) (caar l)

(cdr (car l)) (cdar l)

((car (car (car l)))) (caaar l)

1. extrair a de l;
2. extrair b de l;
3. extrair c de l;
4. extrair e de l;
5. extrair f de l;
6. extrair g de l.

1.6 : Definindo Funções

1. dobro(x) = 2x
2. quadrado(x) = x²
3. incrementa(x) = x+1
4. decrementa(x) = x-1
5. f(x,y) = x+y (adição)
6. f(x) = 3 (função constante)
7. f(x,y) = 10 (função constante com dois parâmetros)
8. uma função que retorne a área da circunferência para um dado raio;
9. uma função que retorne o perímetro da circunferência para um dado raio;
10. f(x,y) = 2x + 5y
11. f(x,y,z) = 10x + 5y - z
12. f(x) = (sin x)² + (cos x)²
13. 
14. uma função que retorne o segundo elemento de uma dada lista;
15. uma função que retorne o terceiro elemento de uma dada lista;
16. uma função que receba uma lista de números e retorne a soma do primeiro com o segundo elemento;
17. uma função que receba dois valores e retorne uma lista com esses valores;
18. uma função que calcule a raiz de uma equação de 2^o grau:
    
    (dica: use let para calcular o valor intermediário delta = b² - 4ac.)

Assim como em matemática, cada função em Scheme é limitada a um determinado domínio; não podemos aplicar qualquer função a qualquer valor. Por exemplo, chamadas como (sin '(a b)) ou (car 4), se executadas, irão resultar em situações de erro. Da mesma forma, as funções em Scheme tem um contra-domínio, que é o conjunto de valores que a função pode retornar. Por exemplo, o contra-domínio da função cons é o conjunto de todas as listas. As condições que os argumentos de uma função têm que satisfazer para que a função opere corretamente são chamadas de pré-condições da função. Por exemplo, a pré-condição de (sin x) é que x seja um número real, ou seja, x . Já a pré-condição da função dada no exercício

      (define f
        (lambda (x y)
            ... ))

      (define (f x y)
            ... )

1.7 : Semântica de Funções

{x 72, y 3}

(/ (+ x y) 2) {x 72, y 3}

(let ([n1 e1] ... [nn en]) corpo) ((lambda (n1 ... nn) corpo) e1 ... en)

1. ((lambda (x y) 10) 3 (* 8 3))
2. ((lambda (x y) (let ((z x)) (+ z y))) 15 23)
3. ((lambda (x) (* x x)) (let ((x 2)) (+ x 4)))
4. (((lambda (x) (lambda (y) (- x y))) 4) 5)

1.8 : Predicados

x y

x y

x Y

x y

1. (null? '(a))
2. (null? '())
3. (null? '(()))
4. (let ((l '(()))) (null? (car l)))
5. (let ((x (* 8 5))) (= x 40))
6. (let ((x 'abobora)) (equal? x 'abobora))
7. ((lambda (x) (equal? x "Jose")) "Jose")
8. ((lambda (x y) (= x y)) 1 1.0)

• number? Testa se um dado valor é um número.
• symbol? Testa se um dado valor é um símbolo.
• list? Testa se um dado valor é uma lista.
• even? Testa se um dado número inteiro é par.
• odd? Testa se um dado número inteiro é ímpar.
• positive? Testa se um dado número é maior que 0.
• zero? Testa se um dado número é igual a 0.

      (define divide?
        (lambda (x y)
          (zero? (remainder x y))))

1. um predicado para verificar se um número é múltiplo de 3;
2. um predicado para verificar se um número é maior que 5;
3. um predicado para verificar se um número é maior ou igual a 5;
4. um predicado para verificar se um número não é maior ou igual a 5;
5. um predicado para verificar se um número é menor que .

1.9 : Condicionais

x 0

      (define f
        (lambda (x)
          (if (>= x 0) x (- x))))

(if '#t b c) b

(if '#f b c) c

A função abaixo retorna o sinal de um número: -1 se ele é negativo, 0 se ele é 0, e +1 se ele é positivo:

      (define sig
        (lambda (x)
          (if (< x 0)
              -1
              (if (> x 0) 1 0))))

O traço da chamada (sig 3) pode ser escrito como abaixo:

(sig 3)
definição de sig
((lambda (x) (if (< x 0) -1 (if (> x 0) 1 0))) 3)
lambda, com {x 3}
(if (< 3 0) -1 (if (> 3 0) 1 0))
comparação
(if '#f -1 (if (> 3 0) 1 0))
regra do if
(if (> 3 0) 1 0)
comparação
(if '#t 1 0)
regra do if
1

---

Exercício 1.19:

      (cond [c1 e1]
            [c2 e2]
              ...
            [cn en]
            [else e])

      (define sig
        (lambda (x)
          (cond
            [(< x 0) -1]    ;lembre-se: trocar [...] por (...)
            [(> x 0)  1]
            [else     0])))

(cond ('#t e) ...) e

(cond ('#f e) (c e') ...) (cond (c e') ...)

(cond (else e)) e

(if a b c) (cond (a b) (else c))

(cond (c1 v1) (c2 v2) (else v)) (if c1 v1 (if c2 v2 v))

(if '#f b c) c

(cond ('#f b) (else c)) (cond (else c)) c

(if '#t b c) b

(cond ('#t b) (else c)) b

(and #f a) #f

(and #t a) a

(or #f a) a

(or #t a) #t

(and a b) (if a b #f)

(or a b) (if a #t b)

(not a) (if a #f #t)

(if (not a) b c) (if a c b)

1. número está no intervalo [3, 50];
2. número está no intervalo [3,30);
3. número está fora do intervalo [3,30);
4. número é par maior que 10;
5. número é impar entre 5 e 15;
6. lista tem pelo menos dois elementos;
7. os dois primeiros elementos de uma dada lista são iguais.

Exercício 1.22: Reescreva os predicados do exercício anterior sem usar and, or, ou not. Troque-os por ifs ou conds.

Exercício 1.23: Reescreva os predicados abaixo, sem usar o operador not:

1. (not (< x 0))
2. (not (>= x y))
3. (not (and (> x 5) (<= x 10)))
4. (not (or (<= x 5) (> x 10)))

   Figura 1.1: Tabela (fictícia) de imposto de renda devido.

Capítulo 2 :

Recursão

      (define fat
        (lambda (n)
          (if (zero? n)
              1
              (* n (fat (- n 1))))))

      (define comp
        (lambda (l)
          (if (null? l)
              0
              (+ 1 (comp (cdr l))))))

(if (null? '(a b c)) 0 (+ 1 (comp (cdr '(a b c)))))

(+ 1 (comp '(b c)))

(+ 1 (if (null? '(b c)) 0 (+ 1 (comp (cdr '(b c))))))

(+ 1 (+ 1 (comp '(c))))

(+ 1 (+ 1 (if (null? '(c)) 0 (+ 1 (comp (cdr '(c)))))))

(+ 1 (+ 1 (+ 1 (comp '()))))

(+ 1 (+ 1 (+ 1 (if (null? '()) 0 (+ 1 (comp (cdr '())))))))

(+ 1 (+ 1 (+ 1 0)))

(+ 1 (+ 1 1))

(+ 1 2)

3

Para definirmos uma função recursivamente, devemos tentar identificar quatro ítens: 1) qual o caso base, 2) qual o valor da função no caso base, 3) como é a chamada recursiva, e 4) como transformar o valor da chamada recursiva no valor final da função. Em geral, o último item é o único que pode apresentar alguma dificuldade. No exemplo do fatorial, o caso base é sobre 0, e o valor da função nesse caso é 0! = 1; o caso recursivo é sobre n-1, e para transformarmos (n-1)! em n! basta multiplicarmos o primeiro valor por n. No exemplo do comprimento da lista, o caso base é sobre a lista vazia, cujo comprimento é 0; o caso recursivo é sobre o cdr da lista, e para transformarmos o comprimento do cdr no comprimento da lista, temos apenas que somar 1.

---

Exemplo 2.1: Considere uma função que retorne uma lista de 1s com um dado comprimento; por exemplo:

(lista-1 4) (1 1 1 1)

Note que, ao contrário de comp, que tem como domínio listas e como contra-domínio os naturais, essa função tem como domínio os naturais e como contra-domínio listas. Vamos tentar identificar os quatro ítens descritos acima. Como a função recebe um número natural, o candidato óbvio para o caso base é 0; uma lista de 1s com comprimento 0 é exatamente a lista vazia, isto é,

(lista-1 0) ()

O caso recursivo também não é difícil, sendo a aplicação da função sobre n-1. Finalmente, se temos uma lista com n-1 1s, como transformá-la em uma lista com n 1s? Basta colocar mais um 1 na frente, com cons. Juntando tudo temos:

      (define lista-1
        (lambda (n)
          (if (zero? n)
              '()
              (cons 1 (lista-1 (- n 1))))))

---

Um erro bastante comum em definições recursivas é tratarmos como caso base um caso que, na realidade, ainda poderia ser tratado normalmente. Por exemplo, a função lista-1 definida acima poderia ser definida como:

      (define lista-1
        (lambda (n)
          (if (= n 1)
              '(1)
              (cons 1 (lista-1 (- n 1))))))

O que há de errado com essa definição? Em primeiro lugar, a função não funciona mais para n=0, que é um valor perfeitamente válido para o comprimento de uma lista. Em segundo lugar, esse caso base é algo artificial; por que não definirmos então o caso base para n=2, ou mesmo 3? Várias funções têm seu comportamento naturalmente estendido para `valores limite' como 0 ou a lista vazia, e não há porque a implementação não tratar tais casos. Exemplos comuns são soma de 0 termos (que é 0, elemento neutro da soma), produto de 0 fatores (que é 1, elemento neutro do produto), x<sup>0</sup> = 1 (podemos pensar em x<sup>0</sup> como um produto de 0 fatores), 0! = 1 (idem), etc. Por outro lado, algumas poucas funções realmente não são bem definidas para tais valores, e neste caso devemos ajustar nosso caso base. Um exemplo típico é o maior elemento de uma lista; não existe um `maior elemento' em uma lista vazia (mais matematicamente, podemos dizer que a operação máximo não tem elemento neutro).

Exercício 2.1: Defina as funções abaixo; lembre-se de primeiro tentar identificar os quatro ítens descritos acima.

1. e2(n) = 2ⁿ (sendo n um número natural)
2. exp(x,n) = xⁿ
3. 
4. f(n) = sin 1 + sin 2 + ^... + sin n
5. sf(n) = 1!+2!+ ^... +n! (dica: use a função fat definida anteriormente.)
6. f(n) = sin 1 + cos 2 + sin 3 + cos 4 + ^... + (sin | cos ) n (dica: use o predicado even? para decidir entre seno e cosseno.)

Exercício 2.2: Defina as funções abaixo; como os parâmetros são listas, em geral o caso base será sobre a lista vazia. Quando o resultado da função for uma lista, tente usar cons para construí-lo.

1. uma função que retorne a soma dos elementos de uma lista de números;
2. uma função que conte quantas vezes um dado elemento aparece em uma lista;
3. um predicado para verificar se um dado elemento está presente em uma lista;⁶
4. uma função maximo que retorne o maior elemento de uma lista de números; (dica: use a função pré-definida max, que retorna o maior entre dois números dados.)
5. um predicado para verificar se todos os números de uma dada lista são pares;
6. uma função que receba uma lista de números, e retorne uma lista com os números incrementados de 1; por exemplo:
   (f '(1 4 6 2)) (2 5 7 3)

7. uma função que receba uma lista de números inteiros, e retorne uma lista contendo somente os números da lista dada que sejam pares; por exemplo:
   (pares '(4 3 2 10 4 5)) (4 2 10 4)
   (dica: use o predicado pré-definido even? para testar se um número é par.)
8. uma função que concatene duas listas;⁷ por exemplo:
   (concatena '(a b c) '(d e)) (a b c d e)

(substitui 'rato 'gato '(um rato maior que outro rato)) (um gato maior que outro gato)

(ordena '(5 4 10 9 3 2 8)) (2 3 4 5 8 9 10)

      (define ordena
        (lambda (l)
          (if (null? l)
              '()
              ... (ordena (cdr l)) ...)))

      (define ordena
        (lambda (l)
          (if (null? l)
              '()
              (insere (car l) (ordena (cdr l))))))

      (define insere
        (lambda (n l)
          (cond
            ((null? l) (cons n '()))
              ...)))

            ((<= n (car l)) (cons n l))

      (define insere
        (lambda (n l)
          (cond
            ((null? l) (cons n '()))
            ((<= n (car l)) (cons n l))
            (else (cons (car l) (insere n (cdr l)))))))

(inverte '(a b c d e)) (e d c b a)

1. uma função que retorne o n-ésimo elemento de uma dada lista, onde n é um parâmetro da função; por exemplo:
   (n-esimo 3 '(a b c d e f)) c
   Assuma que n é menor ou igual que o comprimento da lista.
2. uma função que substitua o valor do n-ésimo elemento de uma lista; por exemplo:
   (muda-n-esimo '(a b c d e f) 3 'novo) (a b novo d e f)

3. uma função que retorne os n primeiros elementos de uma lista (um prefixo da lista); por exemplo:
   (primeiros 5 '(a b c d e f g h i j)) (a b c d e)
   Assuma que n é menor ou igual ao comprimento da lista.
4. uma função que retorne os n últimos elementos de uma lista (um sufixo da lista). (dica: ao invés de recursão, procure apenas combinar as funções que você já tem.)
5. dadas duas listas de números com comprimentos iguais, retornar a lista das somas; por exemplo:
   (soma-listas '(1 3 8) '(2 1 2)) (3 4 10)

6. generalize a função anterior para o caso de uma das listas ser menor que a outra;
7. um predicado que verifique se duas listas de números são iguais; por exemplo:
   (igual '(3 4 5) '(3 4 5)) #t
   (igual '(3 4 5) '(4 5)) #f

2.1 : Recursão Final

      (define n-esimo
        (lambda (n l)
          (if (= n 1)   ; primeiro elemento?
              (car l)
              (n-esimo (- n 1) (cdr l)))))

      (define soma
        (lambda (l a)
          (if (null? l)
              a
              (soma (cdr l) (+ a (car l))))))

Uma maneira de escrevermos uma função para inverter uma lista é mostrada abaixo:

      (define inverte (lambda (l a)
        (if (null? l)
            a
            (inverte (cdr l) (cons (car l) a)))))

Que pode ser usada da seguinte forma:

(inverte '(3 4 5) '()) (5 4 3)

Note que criamos um parâmetro extra (a, no caso acima) que começa com a lista vazia e vai acumulando o resultado ao longo da recursão. Quando chegamos no caso base, a resposta final está nesse acumulador. Observando o traço dessa função, é fácil ver o padrão característico da recursão final: Por exemplo, para inverter a lista '(a b c) teremos:

(inverte '(a b c) '())

(inverte (cdr '(a b c)) (cons (car '(a b c) '())))

(inverte '(b c) '(a))

(inverte '(c) '(b a))

(inverte '() '(c b a))
caso base
(c b a) resultado final

Novamente o segundo parâmetro acumula o resultado, de modo que ao chegar no caso base seu valor é o resutado final da função.

---

Quando a recursão final necessita de parâmetros extras, é comum definirmos uma função auxiliar para fazer a recursão final, com os parâmetros extras, e definir a função `principal' apenas como uma interface que fornece os valores iniciais adequados para a função auxiliar. Desta forma, a função principal não precisa ser chamada com os parâmetros extras. Seguindo essa idéia, a função inverte seria definida como:

      (define inverte-aux (lambda (l a)
        (if (null? l)
            a
            (inverte-aux (cdr l) (cons (car l) a)))))


      (define inverte (lambda (l) (inverte-aux l '())))

Temos aqui mais um exemplo de abstração: com esse método, quem usa a função pode abstrair (e portanto, não se preocupar com) a possível existência de parâmetros extras na função.

Exercício 2.6: (Re)escreva as funções abaixo usando recursão final:

1. fat(n) = n!
2. exp(x,n) = xⁿ (sendo n um número natural)
3. 
4. f(n) = sin 1 + sin 2 + ^... + sin n
5. sf(n) = 1!+2!+ ^... +n! (dica: use a função fat definida anteriormente.)
6. uma função comp que retorne o comprimento de uma lista
7. uma função conta que retorne o número de vezes que um dado símbolo aparece em uma lista.
8. uma função maximo que retorne o maior elemento de uma lista de números.
9. uma função pos que retorne em que posição um elemento ocorre em uma lista (ou '() se ele não estiver presente na lista). Por exemplo,
   (pos 'melao '(abacaxi melao banana pera)) 2
   (pos 'uva '(abacaxi melao banana pera)) ()

10. uma função que retorne uma lista crescente de números com um dado comprimento; por exemplo:
    (ld 5) (1 2 3 4 5)

Exercício 2.7: Escreva uma função para calcular

usando recursão final. (dica: use três acumuladores: um para o somatório, outro para o fatorial, e o terceiro para a exponenciação.)

Exercício 2.8: A série de Fibonacci é definida como

0, 1, 1, 2, 3, 5, 8, 13, 21, ...

onde cada termo é a soma dos dois termos anteriores, isto é,

1. Escreva uma função recursiva fib que calcule o n-ésimo termo da série de Fibonacci. Não use recursão final; baseie sua função na equação acima.
2. Você tem alguma esperança de calcular (fib 40) com sua função? Por que? (Veja quanto tempo sua função demora para calcular (fib n), para n pouco maior que 20).
3. Reescreva a função fib usando recursão final, e compare a eficiência das duas implementações. (dica: use dois parâmetros adicionais, para passar adiante os dois últimos termos da série.)

2.2 : Indução

(+ 8 (sin 5)) (+ 8 -0.958924)

n 0

(fat n) n!

(fat 0) 0!

definição concreta de fat (com n 0)

definição abstrata de fat: (fat (n-1)) (n-1)!

(fat n) n × (n-1)! = n × ((n-1) × ... × 1) = n!

(fat n) n!

n 0

(fat (n-1)) (n-1)!

(fat n) n!

Considere a função abaixo, para calcular xⁿ usando um acumulador e recursão final:

      (define exp
        (lambda (x n a)
          (if (zero? n)
              a
              (exp x (- n 1) (* x a)))))

A terminação de exp é trivialmente garantida, pois a cada chamada decrementamos n, e paramos quando n=0. A pré-condição dessa função é que x e a sejam números reais quaisquer, e n um inteiro maior ou igual a zero. Mas para verificarmos que exp realmente calcula xⁿ, precisamos colocar o papel de a mais claro. Em particular, o que ocorre se chamarmos (exp x n a) com um a qualquer? Não é difícil perceber que a função deveria retornar a × xⁿ; portanto, o que devemos verificar é que

(exp x n a) a × xn

No caso base, com n=0, temos que

(exp x 0 a) a = a × x0

que está correto. No caso geral, com n>0, temos que

(exp x n a) (exp x (n-1) (x × a))

Aqui usamos a hipótese de indução no passo, e um pouco de aritmética na igualdade, para chegarmos em:

(exp x (n-1) (x × a)) (x × a) × xn-1=a × xn

Finalmente, se juntarmos tudo e fixarmos a=1, teremos:

(exp x n 1) 1 × xn = xn

---

---

Exemplo 2.6: Considere a função abaixo (incorreta), para calcular 2ⁿ:

      (define f
        (lambda (n)
           (if (zero? n)
               1
               (/ (f (+ n 1))))))

Para n=0, temos

(f 0) 1=20

como queríamos. Para n>0, temos

(f n) (/ (f (n+1)) 2)

Usando o princípio de indução aqui, conseguiríamos provar trivialmente que

(f n) 2n+1/2 = 2n

Mas não é muito difícil perceber que essa função não funciona, donde há algo errado em nosso raciocínio. Se chamarmos essa função com o argumento 5, por exemplo, teremos o traço abaixo:

(f 5)

(/ (f 6) 2)

(/ (/ (f 7) 2) 2)

(/ (/ (/ (f 8) 2) 2) 2)

...

A função ficará se repetindo infinitamente, em uma situação que chamamos de loop. Como a função não termina, não podemos usar o princípio de indução.

---

2.3 : Terminação

n 0

a b

b a

      (define mdc
        (lambda (a b)
          (cond
            ((zero? a) b)
            ((zero? b) a)
            ((>= a b) (mdc (- a b) b))
            (else (mdc a (- b a))))))

• a=0 --- Nesse caso, (mdc 0 b) b=mdc(0,b).
• b=0 --- Idêntico ao caso anterior.
• a b --- Nesse caso,
  (mdc a b) (mdc (a-b) b)
  Como a b, temos que a-b 0, garantindo a pré-condição na chamada recursiva. Pelo princípio de indução,
  (mdc (a-b) b) mdc(a-b,b)
  Mas sabemos (vide acima) que mdc(a-b,b)=mdc(a,b), logo temos que
  (mdc a b) mdc(a,b)

• a<b --- Idêntico ao caso anterior.

h(a,b)=a+b 0

a b

1. Defina a função mdc em Scheme usando essas igualdades.
2. Mostre que sua função sempre termina quando chamada com argumentos positivos.

      (define collatz
        (lambda (n)
           (cond
             ((= n 1) '())
             ((even? n) (cons n (collatz (quotient n 2))))
             (else (cons n (collatz (+ (* n 3) 1)))))))

      (define mult
        (lambda (a b)
          (cond
            ((zero? b) 0)
            ((even? b) (* 2 (mult a (quotient b 2))))
            (else (+ a (* 2 (mult a (quotient b 2))))))))

Mostre que essa função sempre termina quando chamada com a,b 0, e que

(mult a b) a × b

Exercício 2.13: Escreva uma função que retorne a lista dos fatores primos de um dado número. Por exemplo,

(fatores 84) (2 2 3 7)

Use a expressão (zero? (remainder x y)) para testar se x é divisível por y. Mostre que sua função sempre termina quando chamada com n 0, e que o produto dos elementos da lista retornada é igual a n.

2.4 : Padrões de Recursão

      (define filtra-pares
        (lambda (l)
          (cond
            ((null? l) '())
            ((even? (car l)) (cons (car l) (filtra-pares (cdr l))))
            (else (filtra-pares (cdr l))))))

      (define filtra
        (lambda (f l)   ; f e' o predicado de filtro
          (cond
            ((null? l) '())
            ((f (car l)) (cons (car l) (filtra f (cdr l))))
            (else (filtra f (cdr l))))))

(filtra even? '(1 10 9 45 22 11 0)) (10 22 0)

1. elementos ímpares;
2. elementos maiores que 10; (dica: você não precisa definir um novo predicado. Ao invés disso, você pode usar lambda diretamente na chamada: pense na função (lambda (x) (> x 10)).)
3. elementos no intervalo [5,15].

      (define (ordena l)
        (if (null? l)
            '()
            (append
              (ordena (filtra (lambda (x) (<= x (car l))) (cdr l)))
              (cons (car l)
                (ordena (filtra (lambda (x) (> x (car l))) (cdr l)))))))

(mapeia round '(1.3 5.01 3.32)) (1 5 3)

1. uma função ls que receba uma lista de números e retorne a lista de seus senos.
2. uma função q que receba uma lista de números e retorne a lista de seus quadrados. Por exemplo,
   (q '(3 9 2)) (9 81 4)

1. calcular o maior elemento de uma lista;
2. calcular o menor elemento de uma lista;
3. calcular o comprimento de uma lista;
4. contar quantas vezes um dado número aparece em uma lista;
5. inverter uma lista.

Exercício 2.22: Usando a função acumula, escreva um predicado genérico, que receba um predicado e uma lista, e verifique se todos os elementos da lista satisfazem o predicado dado. Por exemplo,

(acpred even? '(2 3 4 6)) #f

(acpred odd? '(3 19 7 1)) #t

Exercício 2.23: Identifique alguma função recursiva já implementada por você que não possa ser reescrita sem o uso de recursão, usando-se filtra, mapeia, e acumula.

2.5 : Repetições

      (define soma-aux
        (lambda (l s)
          (if (null? l)
              s
              (soma-aux (cdr l) (+ s (car l))))))


      (define soma (lambda (ll) (soma-aux ll 0)))

• Os parâmetros da função original, no exemplo apenas ll, que são passados inalterados para soma-aux.
• Os parâmetros de soma-aux, ou variáveis, l e s.
• Os valores iniciais que damos aos parâmetros de soma-aux, no caso ll e 0.
• As expressões de atualização, que definem os novos valores dos parâmetros a cada nova chamada recursiva. No exemplo acima, essas expressões são (cdr l) (para l) e (+ s (car l)) (para s).
• O teste de terminação, (null? l).
• O valor final da função, que é o valor final de s.

      (define soma
        (lambda (ll)
          (do ([l ll (cdr l)]
               [s 0 (+ s (car l))])
              ((null? l) s))))

      (do ([n1 v1 e1]
            ...
           [nn vn en])
          (teste valor-final))

      (define aux
        (lambda (n1 ... nn)
          (if teste
              valor-final
              (aux e1 ... en))))


      (aux v1 ... vn)   ; <= expressao equivalente ao do

      (define (media l)
        (do ((l1 l (cdr l1))
             (s  0 (+ s (car l1)))
             (n  0 (+ n 1)))
             ((null? l1) (/ s n))))

l1 (cdr l1), s (+ s (car l1)), n (+ n 1)

l1 (cdr l1), s (+ s (car l1)), n (+ n 1)

l1 (cdr l1), s (+ s (car l1)), n (+ n 1)

1. fat(n) = n!
2. exp(x,n) = xⁿ (sendo n um número natural)
3. 
4. f(n) = sin 1 + sin 2 + ^... + sin n
5. uma função comp que retorne o comprimento de uma lista
6. uma função som que retorne o somatório de uma lista de números.
7. uma função inverte que retorne uma dada lista invertida.
8. uma função conta que retorne o número de vezes que um dado símbolo aparece em uma lista;

Capítulo 3 :

Representação de Dados

3.1 : Representando Conjuntos

Uma grande variedade de dados podem ser representados através do conceito matemático de conjuntos. Por exemplo, um programa de controle acadêmico pode utilizar conjuntos para armazenar as disciplinas cursadas por um aluno, os pré-requisitos de uma disciplina, os alunos de cada curso, etc.

Uma maneira bastante direta para se representar conjuntos em Scheme é através de uma lista de seus elementos. Note que um mesmo conjunto pode ser representado por várias listas; por exemplo, o conjunto {a,b} pode ser representado pelas listas (a b), (b a), (a b a), etc. De modo a diminuir um pouco essa multiplicidade, vamos exigir que uma lista representando um conjunto nunca tenha elementos repetidos (esse tipo de restrição sobre possíveis representações de um valor é denominado invariante). Assim, as listas (a b) e (b a) ambas representam o conjunto {a,b}, enquanto (a b a) não é uma representação válida de nenhum conjunto (pois não satisfaz o invariante).

Mais do que armazenar dados, um computador deve ser capaz de manipular esses dados. Assim, mais importante do que definirmos como representar um determinado tipo de dado, é mostrarmos como podemos manipular dados usando essa representação. Vamos então mostrar como as diversas operações básicas de conjuntos podem ser definidas sobre a representação com listas.

A operação mais básica sobre conjuntos é o predicado pertence?, para verificar se um dado elemento pertence a um conjunto. Sua definição não apresenta dificuldades:

      (define pertence?
        (lambda (e c)
          (if (null? c)
              #f
              (or (equal? e (car c))
                  (pertence? e (cdr c))))))

No caso base, com o conjunto vazio, a função resulta em falso (nenhum elemento pode pertencer ao conjunto vazio). Se a lista não é vazia, um elemento na lista ou é igual ao primeiro elemento ou então está no resto da lista.

A união de dois conjuntos já não é tão direta. Podemos pensar em simplesmente concatenar as duas listas, mas se existirem elementos comuns aos dois conjuntos, eles apareceriam repetidos na lista final, desrespeitando nosso invariante. Para evitarmos esse problema, temos que tomar o cuidado de somente inserir um novo elemento no resultado se ele ainda não estiver lá:

      (define uniao
        (lambda (a b)
          (cond
            ((null? a) b)
            ((pertence? (car a) b) (uniao (cdr a) b))
            (else (cons (car a) (uniao (cdr a) b))))))

Exercício 3.1: Faça o traço da chamada (uniao '(a b c) '(b e)).

Exercício 3.2: Escreva uma função que receba dois conjuntos e retorne sua interseção.

Exercício 3.3: Escreva uma função que receba dois conjuntos e retorne sua diferença. (A diferença entre dois conjuntos A e B, A-B, é o conjunto formado pelos elementos de A que não pertencem a B.)

Exercício 3.4: Escreva um predicado que receba dois conjuntos c1 e c2 e verifique se c1 c2.

Exercício 3.5: Escreva um predicado que receba dois conjuntos c1 e c2 e verifique se c1 = c2. Observe que não basta comparar as listas. Por exemplo, os conjuntos representados pelas listas (1 2 3) e (2 3 1) são iguais. (dica: lembre-se que c1 = c2 se e somente se c1 c2 e c2 c1.)

Exercício 3.6: Redefina as funções de união e interseção de conjuntos usando do.

Exercício 3.7: Reescreva as funções de união e interseção de conjuntos utilizando a função acumula, do exercício

3.2 : Representação de Números Naturais

      (define soma
        (lambda (a b)
           (if (zer? b)
               a
               (inc (soma a (dec b))))))

      (define soma
        (lambda (a b)
          (do ((a1 a (inc a1))
               (b1 b (dec b1)))
             ((zer? b1) a1))))

      (define zero 0)
      (define zer? zero?)
      (define inc (lambda (n) (+ n 1)))
      (define dec (lambda (n) (- n 1)))

1. Uma função sub, para subtrair dois números. Por exemplo,
   (sub '(1 1 1 1) '(1 1)) (1 1)
   O que acontece com sua função na chamada abaixo?
   (sub '(1) '(1 1 1))

2. Uma função mult, para multiplicar dois números. Por exemplo,
   (mult '(1 1 1) '(1 1)) (1 1 1 1 1 1)

      (define comp
        (lambda (a b)
           (cond
             ((and (zer? a) (zer? b)) 0)
             ((zer? a) -1)
             ((zer? b)  1)
             (else (comp (dec a) (dec b))))))

1. Uma função div, para dividir dois números, retornando o quociente da divisão. Por exemplo,
   (div '(1 1 1 1 1) '(1 1)) (1 1)
   O que ocorre com sua função se for feita uma divisão por 0?
2. Uma função resto, retornando o resto da divisão de dois números. Por exemplo,
   (resto '(1 1 1 1 1) '(1 1)) (1)

3.3 : Tabelas Associativas

      (
        (Denise  2221111)
        (Paulo   2741555)
        (Jose    2221133)
        (Maria   2129876)
      )

1. Defina uma variável catalogo, com sua lista pessoal de telefones.
2. Defina uma função de consulta que receba um nome e retorne o telefone associado a esse nome em catalogo. Por exemplo,
   (telefone 'Denise) 2221111
   (dica: use recursão final.)

      (define M97-1 '(
        (M-9611110 (INF1001 FIS1034 MAT1090))
        (M-9610222 (FIS1034 FIL1890))
        (M-9520000 ())
        (M-9523456 (INF1001 FIS1034 MAT1090 JUR1110))))

Escreva uma função que receba o código de uma disciplina e uma lista representando um resultado de matrícula, e retorne uma lista dos alunos matriculados nessa disciplina. Por exemplo:

(cursando 'MAT1090 M97-1) (M-9611110 M-9523456)

(dica: use suas funções para manipular conjuntos.)

Exercício 3.12: Escreva uma função que receba os números de matrícula de dois alunos e retorne a lista de disciplinas que ambos fazem juntos. (dica: use suas funções para manipular conjuntos e para manipular tabelas.)

Considere agora mais duas tabelas, uma associando o número de matrícula ao nome do aluno, e outra associando o código de disciplina ao professor. Por exemplo:

      (define NOMES '(
        (M-9611110 "Paulo Moura")
        (M-9610222 "Maria Nunes")
        (M-9520000 "Marcos Cintra")
        (M-9523456 "Marta Silva Teles")))


      (define PROFS '(
        (INF1001 "Joel Santos Borges")
        (FIS1034 "Fabio Tavares")
        (MAT1090 "Leila Pinheiro")
        (JUR1110 "Sonia Maria do Carmo")
        (FIL1890 "Carlos Augusto")))

Exercício 3.13: Defina uma função com a mesma especificação do exercício

(cursando 'MAT1090 M97-1) ("Paulo Moura" "Marta Silva Teles")

3.4 : Árvores Binárias

log₂ 10⁶ 20

1. estime, muito aproximadamente, quantos assinantes estão listados.
2. Procure um nome qualquer no catálogo, e conte quantos outros nomes você tem que ler até achar (ou não) o que você procura.
3. Seria viável achar algum nome no catálogo se este não estivesse organizado em ordem alfabética?

   Figura 3.1: Representação gráfica de uma árvore binária
(incluindo as sub-árvores vazias).

   Figura 3.2: Árvore binária da figura 3.1,
sem mostrar as sub-árvores vazias.

1. (A B C)
2. (5 (1 3 4) 7)
3. (2 (10 () 3) (2 1 9))
4. A
5. (A () (B () (C () (D () E))))

      (define arvore-vazia '())


      (define vazia? null?)

      (define folha?
        (lambda (a)
          (not (list? a))))

      (define cria-arvore
        (lambda (r e d)
          (if (and (vazia? e) (vazia? d))
              r
              (cons r (cons e (cons d '()))))))

      (define raiz
        (lambda (a)
          (if (folha? a)
              a
              (car a))))

      (define num-nos
        (lambda (a)
          (cond
            ((vazia? a) 0)
            ((folha? a) 1)   ; caso opcional
            (else (+ 1 (num-nos (esquerda a)) (num-nos (direita a)))))))

      (define num-nos
        (lambda (a)
          (cond
            ((vazia? a) 0)
            (else (+ 1 (num-nos (esquerda a)) (num-nos (direita a)))))))

      (define soma-arvore
        (lambda (a)
          (if (vazia? a)
              a
              (cria-arvore (+ 1 (raiz a))
                           (soma-arvore (esquerda a))
                           (soma-arvore (direita a))))))

1. uma função que retorne a soma de todos os nós de uma dada árvore de números;
2. uma função que retorne a altura de uma dada árvore; (dica: use a função pré-definida max.)
3. uma função que retorne uma lista com todos os elementos de uma dada árvore; (dica: use a função pré-definida append, ou a função definida no exercício 2.2.h, para juntar as várias partes do resultado.)
4. na função do item anterior, em que ordem os elementos da árvore aparecem na lista? Qual é o primeiro? Qual é o último?
5. uma função que receba n e retorne uma árvore contendo n nós, todos com o valor 1. Procure fazer as duas sub-árvores terem sempre aproximadamente o mesmo número de elementos.
6. uma função que receba n e retorne uma árvore contendo n nós, cada um com um valor diferente de 1 até n. Procure fazer as duas sub-árvores terem sempre aproximadamente o mesmo número de elementos. (dica: defina sua função com dois parâmetros, i e n, para retornar uma árvore numerada de i até n.)

Representação de Expressões Aritméticas

   Figura 3.3: Árvore binária representando a expressão 5 ×  (3 + 1).

1. 3+4
2. 3 × 4 + 5
3. 3 + 4 × 5
4. 3+4+5
5. 3/4 + 5/2
6. 3+2+10+9+2
7. (3+2)+10+(9+2)

(converte '(* (+ 5 4) (- 2 3))) ((5 + 4) * (2 - 3))

Árvores Binárias de Busca

   Figura 3.4: Uma árvore de busca.

3.5 : Notação Posicional e Bases de Numeração

      (define base->num
        (lambda (l)
          (if (null? l)
              0
              (+ (car l) (* base (base->num (cdr l)))))))

      (define num->base
        (lambda (n)
          (if (zero? n)
              '()
              (cons (remainder n base) (num->base (quotient n base))))))

Operações Aritméticas com Notação Posicional

      (define inc
        (lambda (n)
          (cond
            ((null? n) '(1))
            ((= (+ (car n) 1) base) (cons 0 (inc (cdr n)))))))
            (else (cons (+ (car n) 1) (cdr n)))

      (define soma
        (lambda (a b v)     ; v indica "vai um"
          (cond
            ((and (null? a) (null? b)) (if (zero? v) '() '(1)))
            ((null? a) (soma '(0) b v))
            ((null? b) (soma a '(0) v))
            (else (let ((d (+ (car a) (car b) v)))
                    (if (< d base)
                      (cons d (soma (cdr a) (cdr b) 0))
                      (cons (- d base) (soma (cdr a) (cdr b) 1))))))))

   Figura 3.5: Função para somar dois números na base decimal.

1. uma função para subtrair dois números. Siga o mesmo raciocínio que usamos para soma, tentando traduzir para Scheme o algoritmo de subtração que usamos manualmente.
2. Um predicado para testar se um número é menor que outro.

Base Binária

(base->num (num->base n)) n

1. 2, 4, 6, 16, e 33 para a base binária (base 2);
2. 3, 6, e 12 para a base 3;
3. 13, 64, e 60 para a base 16.

1. dup2(x) = 2x
2. div2(x) = x ÷ 2
3. verificar se o número é par.

3.6 : Outros Exercícios

1. Usando esta representação, escreva uma função que receba um polinômio e um valor para x, e retorne o valor do polinômio para o x dado. (dica: use a igualdade
   a_n xⁿ + a_n-1 x^n-1 + ^... + a₁ x + a₀ = a₀ + x(a₁ + x(a₂ + ^... + x (a_n) ^... ))
   para simplificar os cálculos.)
2. Escreva uma função auxiliar que receba n e retorne a lista (1/1! - 1/3! 1/5! - 1/7! ... ) com n elementos.
3. A lista gerada pelo item anterior, com n=4, representa o polinômio Usando a função do primeiro item, calcule o valor desse polinômio para alguns valores de x entre 0 e 1. Compare os valores obtidos com os de sin x. Aumente o número de termos do seu polinômio (aumentando n na função do item anterior), e repita a comparação.
4. Escreva uma função que some dois polinômios. A soma de dois polinômios é um polinômio de grau igual ao maior grau entre os polinômios somados, e onde cada coeficiente é igual a soma dos coeficientes de igual grau nos polinômios somados. (dica: veja exercício 2.5.f.)
5. Escreva uma função que receba um polinômio e retorne sua derivada. Relembrando, a derivada de um polinômio de grau n
   a_n xⁿ + a_n-1 x^n-1 + ^... + a₁ x + a₀
   é o polinômio de grau n-1
   (n × a_n) x^n-1 + ((n-1) × a_n-1) x^n-2 + ^... + 2a₂ x + a₁

      (define calc
         (lambda (exp)
            (cond
               ((number? exp) exp)
               ((equal? (car exp) '+) (+ (calc (cadr exp)) (calc (caddr exp))))
               ((equal? (car exp) '*) (* (calc (cadr exp)) (calc (caddr exp)))))))

   Figura 3.6: Definição inicial da função calc.

Exercício 3.39: Considere a função mostrada na figura

1. faça o traço da chamada (calc '(+ (* 4 5) 2)).

2. Modifique a função calc de forma que ela também interprete subtração e divisão.

3. Modifique sua função para tratar expressões com nomes, como por exemplo (+ x y). Para isso, vamos precisar de um ambiente, que associe cada nome ao seu valor. Esse ambiente pode ser representado como uma lista associativa; por exemplo, o ambiente {x 12, y 23} será representado pela lista ((x 12) (y 23)). O ambiente deve então ser passado como um parâmetro adicional para a função calc, e consultado (use uma função auxiliar consulta) toda vez que a expressão for um nome (use o predicado symbol? para testar se a expressão é um nome). Um exemplo de uso segue abaixo; lembre-se que calc agora recebe dois argumentos, a expressão a ser calculada e o ambiente com o valor das variáveis:
   (calc 'b '((a 1) (b 8))) 8
   (calc '(* (+ y 3) x) '((x 2) (y 5))) 16

4. Usando a função acima, escreva uma função declare que acrescente um par (nome valor) em um dado ambiente, mas onde o valor pode ser dado através de uma expressão. Essa função recebe um par (nome expressão) e um ambiente, e retorna o novo ambiente. Por exemplo:
   (declare '(x 1) '((y 2) (z 5))) ((x 1) (y 2) (z 5))
   (declare '(val (* 2 2)) '((y 2) (z 5))) ((val 4) (y 2) (z 5))
   (declare '(x (+ 4 y)) '((y 2) (z 5))) ((x 6) (y 2) (z 5))

5. Usando a função acima, acrescente na sua função calc uma operação para definir valores (parecida com o let), chamada def. O uso de def é exemplificado abaixo:
   (calc '(def (x 10) (+ x 3)) '()) 13
   (calc '(def (x (+ 2 8)) (* (+ x 3) y)) '((y 5))) 65
   (dica: use calc para calcular o valor da expressão, em um ambiente onde a nova variável foi associada ao valor adequado. Use a função do item anterior para construir esse novo ambiente.)

Capítulo 4 :

Programação Procedural

4.1 : Interação

      (define mostra-seno
        (lambda (x)
          (begin (display "O valor do seno de ")
                 (display x)
                 (display " é ")
                 (display (sin x)))))

(begin (* 10 5) (- 5 4)) 1

      (define mostra-lista
        (lambda (l)
          (if (null? l)
              '()
              (begin
                (display (car l))
                (newline)
                (mostra-lista (cdr l))))))

      (define mostra-lista
        (lambda (l)
          (if (not (null? l))
              (begin
                (display (car l))
                (newline)
                (mostra-lista (cdr l))))))

      (define (mostra-n n t)
        (if (not (zero? n))
           (begin
             (display t)
             (mostra-n (- n 1) t))))

1. Dado um número n, escrever os valores de n²,(n-1)²,...,9,4,1, um por linha.
2. Dado um número n, escrever os valores de 1, 4, 9, ...,(n-1)²,n², um por linha.
3. Escrever os elementos de uma dada lista, um por linha, precedidos pelo seu número de ordem. Por exemplo, uma chamada como
   (mostra-num-linha '(martelo prego alicate))
   deve produzir uma saída como

   1 - martelo
   2 - prego
   3 - alicate
   

4. Escrever os elementos de uma dada lista, dois por linha, separados por um espaço. Por exemplo, uma chamada como
   (mostra-lista '(martelo prego alicate tesoura serrote))
   deve produzir uma saída como

   martelo prego
   alicate tesoura
   serrote
   

   (dica: use o predicado even? para decidir se é hora de mudar de linha.)
5. Generalize a função do exercício anterior para, ao invés de escrever dois elementos por linha, escrever n por linha, onde n é um parâmetro do procedimento.

      (do ([n1 v1 e1]
            ...
           [nn vn en])
          (teste valor-final)
          corpo)

      (define aux
        (lambda (n1 ... nn)
          (if teste
              valor-final
              (begin
                corpo
                (aux e1 ... en)))))


      (aux v1 ... vn)   ; <= expressao equivalente ao do

      (define mostra
        (lambda (l)
          (do ((l1 l (cdr l1)))
              ((null? l1))
              (display (car l1))
              (newline))))

1. Conjuntos representados por listas. Mostre os elementos entre chaves {...}, separados por vírgulas; por exemplo:
   (mostra-conjunto '(3 10 9 5)) {3,10,9,5}

2. Números na representação binária. Mostre os números com os dígitos mais significativos à esquerda, e seguidos por um b. Trate o valor zero de maneira adequada; por exemplo:
   (mostra-binario '(0 0 1 0 1)) 10100b
   (mostra-binario '()) 0b

3. Catálogos representados por listas associativas. Mostre cada par chave valor em uma linha, com um -> entre eles; por exemplo:
   (mostra-catalogo '((Denise 2221111) (Paulo 2741555)))
   

4. Conjuntos representados por árvores de busca. Mostre os elementos entre chaves {...}, separados por vírgulas, em ordem crescente; por exemplo:
   (mostra-conjunto '(5 (3 1 4) (10 () 12))) {1,3,4,5,10,12}
   (dica: use suas funções para manipulação de árvores binárias (vazia?, raiz, etc). Se você percorrer a árvore da maneira adequada, os elementos aparecerão naturalmente em ordem crescente. A maior dificuldade deste exercício é colocar as vírgulas de maneira correta.)

A
    B
        -
        E
            H
    C
        F
        G
            I
            J

      (define f
         (lambda (a b)
           ...))

      (define f
         (lambda (a b)
           (begin (display a) (newline) (display b) (newline)
             ...)))

(begin (display "Entre com dois números")
       (newline)
       (+ (read) (read)))

1. Pedir um número ao usuário, e em seguida mostrar a mensagem "O seno de x é sin x", onde x é o valor fornecido e sin x o seu seno. (dica: use let para guardar o valor lido.)
2. Repetidamente pedir um número ao usuário, até este entrar com o número 0, e retornar a soma dos números lidos.
3. Repetidamente pedir um número ao usuário, até este entrar com o número 0, e retornar uma lista com todos os números lidos, na mesma ordem em que eles foram dados.
4. Pedir um número n ao usuário, em seguida ler mais n números, e retornar uma lista com esses n números.
5. Repetidamente pedir um número ao usuário, até este entrar com o número 0, e mostrar a soma e o produto dos números lidos (não incluir o 0).

4.2 : Vetores

(vector-ref v 0) 3

(vector-ref v 1) 19

(vector-ref v 2) (8 9)

(vector-ref v 3) 4

1. Defina uma variável contendo um vetor com os elementos 1, 2, 4, 5, e 10.
2. Defina uma função que receba um vetor e retorne seu último elemento.
3. Defina uma função que receba um vetor de números e retorne a média aritmética entre o primeiro e o último elementos.
4. Defina uma função que receba um vetor de números e retorne a soma de seus três primeiros elementos.
5. Defina uma função que receba um vetor e um índice i, e retorne a média dos valores nas posições i e i+1.
6. Defina um predicado que receba um vetor e dois índices i e j, e verifique se os valores nas posições i e j do vetor são iguais.

Como a única maneira de se acessar um elemento de um vetor é através de um índice, a recursão sobre vetores é bastante diferente da recursão sobre listas. Ao invés de usarmos car, cdr e null?, devemos usar um índice variando de um em um, passando assim por todos os elementos do vetor. A função vector-length pode ser usada para saber em que índice parar (ou começar) a recursão.

---

Exemplo 4.6: Para somarmos os elementos de um vetor, podemos definir uma função como abaixo, usando recursão final:

      (define soma-aux
        (lambda (v i s)
          (if (= i (vector-length v))
              s
              (soma-aux v (+ i 1) (+ s (vector-ref v i))))))


      (define soma (lambda (v) (soma-aux v 0 0)))

Na função soma-aux, v é o vetor cujos elementos estamos somando, i percorre os índices, e s acumula o resultado. O traço dessa função, quando chamada sobre o vetor #(2 5 3), será:

(soma '#(2 5 3))

(soma-aux '#(2 5 3) 0 0)

(soma-aux '#(2 5 3) 1 2)

(soma-aux '#(2 5 3) 2 7)

(soma-aux '#(2 5 3) 3 10)
fim, pois i = (vector-length v)
10 resultado final

Essa mesma função pode ser escrita, de forma mais compacta, usando-se o do:

      (define soma
        (lambda (v)
          (do ((i 0 (+ i 1))
               (s 0 (+ s (vector-ref v i))))
              ((= i (vector-length v)) s))))

---

---

Exemplo 4.7: Como podemos acessar os elementos do vetor diretamente, isto é, em qualquer ordem, podemos reescrever a função soma somando os elementos do último para o primeiro. Como a terminação é quando i passar de 0, só precisamos chamar vector-length uma única vez, no início da repetição. Nesse caso, a função pode ser escrita como:

      (define soma
        (lambda (v)
            (do ((i (- (vector-length v) 1) (- i 1))
                 (s 0 (+ s (vector-ref v i))))
                ((< i 0) s))))

Note que i começa com o tamanho do vetor menos 1, que é o último índice do vetor.

---

Exercício 4.7: Defina as seguintes funções:

1. Uma função que retorne o produto dos elementos de um vetor.
2. Uma função que retorne uma lista com os elementos de um vetor.¹⁷
3. Uma função busca que verifique se um dado elemento existe em alguma posição do vetor. Caso positivo, a função deve retornar o índice onde esse elemento foi encontrado; caso contrário, retorna (). Por exemplo,
   (busca '#(banana pera uva goiaba) 'uva) 2
   (busca '#(banana pera uva goiaba) 'pitanga) ()

4. Uma função que imprima os elementos de um vetor, um por linha.
5. Uma função maior que retorne o maior elemento em um vetor de números. Por exemplo,
   (maior '#(10 8 5 19 3 -8)) 19

Defina uma função indice-maior que retorne o índice do maior elemento em um vetor de números. Essa função deve receber, além do vetor, um índice indicando até que elemento procurar. Por exemplo,

(indice-maior '#(10 8 5 19 3 -8) 5) 3

pois o maior valor do vetor, 19, está na posição 3; enquanto

(indice-maior '#(10 8 5 19 3 -8) 2) 0

pois o maior elemento até o índice 2 (isto é, entre os 3 primeiros elementos) é 10, na posição 0.

Exercício 4.9: Considere um vetor onde cada elemento é uma lista com um símbolo e um número, como por exemplo:

(define v #((u 1) (r 2) (s 5) (c 0) (c 7) (o -1) (i 4) (c -1)))

O número em cada posição do vetor é usado para indicar uma próxima posição no vetor, formando um encadeamento. Por exemplo, na posição 3 de v temos a lista (c 0), indicando que a próxima posição no encadeamento é a posição 0. Na posição 0 temos (u 1), indicando o 1 como a próxima posição. O valor -1 em uma posição indica o fim de uma cadeia.

Escreva uma função cadeia que, dados um vetor como descrito acima, e uma posição inicial, retorne a lista com os símbolos contidos nas posições encadeadas. Por exemplo, com v declarado como acima, teríamos:

(cadeia v 3) (c u r s o)

(cadeia v 6) (i c c)

O procedimento vector-set! permite alterarmos o valor de qualquer posição de um vetor. Esse procedimento recebe o vetor a ser alterado, o índice, e o novo valor a ser colocado naquele índice. O valor antigo é simplesmente apagado. Por exemplo, se definirmos

(define vet '#(2 90 -9 0.1))

e executarmos

(vector-set! vet 2 13)

após essa operação vet será '#(2 90 13 0.1). Vale a pena frizar que, ao contrário de cons para listas, vector-set! não cria um novo vetor, mas modifica o valor armazenado em uma dada posição de um vetor pré-existente. Também é importante lembrar que vector-set! é um procedimento. O valor retornado por essa função é irrelevante. Usamos vector-set! somente para modificar um valor em uma posição de um dado vetor.

---

Exemplo 4.8:

      (define zera-vetor
        (lambda (v)
          (do ((i 0 (+ i 1)))
              ((= i (vector-length v)))
              (vector-set! v i 0))))

      (define s-aux
        (lambda (v i)
          (if (> i 0)
              (begin
                (troca v i (indice-maior v i))
                (s-aux v (- i 1))))))


      (define s (lambda (v) (s-aux v (- (vector-length v) 1))))

(make-vector 8) #(() () () () () () () ())

      (define cria-zeros
        (lambda (n)
          (let ((v (make-vector n)))
             (begin
               (zera-vetor v)
               v))))

      (define lista->vetor-aux
        (lambda (v i l)
           (if (null? l)
               v
               (begin
                  (vector-set! v i (car l))
                  (lista->vetor-aux v (+ i 1) (cdr l))))))


      (define lista->vetor (lambda (l)
            (lista->vetor-aux (make-vector (length l)) 0 l)))

Escreva uma função soma-vetor, que receba dois vetores de números com o mesmo tamanho, e retorne um novo vetor com a soma dos elementos dos vetores dois a dois. Por exemplo:

(soma-vetor '#(1 3 5) '#(8 7 8)) #(9 10 13)

Exercício 4.16:

Escreva uma função cria-vetor que receba um tamanho n e uma função f, e retorne o vetor composto pelos valores f(0), f(1), ..., f(n-1). Por exemplo,

(cria-vetor 5 (lambda (x) (* x 2))) #(0 2 4 6 8)

(cria-vetor 4 (lambda (x) 1)) #(1 1 1 1)

Exercício 4.17: Refaça o exercício

1. Escreva uma função que receba dois parâmetros m e n e retorne uma matriz de zeros de tamanho m × n. Por exemplo
   (make-matrix 3 2) #(#(0 0) #(0 0) #(0 0))
   (dica: use a função cria-vetor.)

2. Escreva uma função matrix-ref que receba uma matriz a e dois índices i e j, e retorne o valor do elemento a_{i j}.

3. Escreva uma função matrix-set! que receba uma matriz a, dois índices i e j, e um valor v, e modifique o valor da posição a_{i j} para v.

4. Escreva uma função cria-matriz, que receba m, n, e uma função f, e retorne uma nova matriz de tamanho m × n, onde cada elemento a_{i j} tem o valor de f(i,j). Por exemplo,
   (cria-matriz 3 3 +) #(#(0 1 2) #(1 2 3) #(2 3 4))
   (dica: use a função cria-vetor.)

5. Escreva uma função que receba duas matrizes e seus tamanhos, e retorne a matriz com o produto das duas matrizes dadas. Para lembrar, o produto de uma matriz a de tamanho n × m por uma matriz b de m × k, é uma matriz c de tamanho n × k, com seus elementos definidos pela fórmula
   
   (dica: procure escrever uma função para calcular o somatório acima, e use a função cria-matriz para construir o resultado.)

Capítulo 5 :

Solução de Alguns Exercícios Selecionados

Exercício 1.1.k: (+ 1 2 3 4 5 6 7 8 9). Tanto o operador + quanto o operador * podem receber mais de dois argumentos.
Exercício 1.1.q: (+ (sin 4.5) (cos 3.7))
Exercício 1.2.d: 3.1 × (2 + 5.4)
Exercício 1.2.q: sin x + cos x
Exercício 1.2.r: sin (x + cos x)
Exercício 1.3.f: (- (/ 5 2) (quotient 5 2))
Exercício 1.3.g: (+ (* (quotient 1345 17) 17) (remainder 1345 17))
Exercício 1.7.e: O símbolo a será associado ao operador de soma. Após essa definição, você pode escrever (a 4 5) para somar 4 e 5.
Exercício 1.13.a: caar, pois o valor de (caar l) é:
(caar l)
definição de caar
(car (car l))
valor de l
(car (car '((a b c) (e f) g)))

(car '(a b c))

'a

Exercício 1.13.e: cadadr. Fazendo o traço:
(cadadr l)
definição de cadadr
(car (cdr (car (cdr l))))
valor de l
(car (cdr (car (cdr '((a b c) (e f) g)))))

(car (cdr (car '((e f) g))))

(car (cdr '(e f)))

(car '(f))

'f


Exercício 1.14.a: (define dobro (lambda (x) (* x 2))) ou então (define dobro (lambda (x) (+ x x))).
Exercício 1.14.g: (define f (lambda (x y) 10))
Exercício 1.14.k: (define f (lambda (x y z) (- (+ (* 10 x) (* 5 y)) z)))
Exercício 1.14.n: (define segundo (lambda (l) (cadr l))) Ou mais diretamente: (define segundo cadr)
Exercício 1.16.d:
(((lambda (x) (lambda (y) (- x y))) 4) 5)
1^o lambda, com {x 4}
((lambda (y) (- 4 y)) 5)
lambda, com {y 5}
(- 4 5)
aritmética
-1

Exercício 1.18.b: (define maior5 (lambda (x) (> x 5)))
Exercício 1.18.e: Testar se é o mesmo que testar se x² < 2; em Scheme:
(define mr2 (lambda (x) (< (* x x) 2)))
Exercício 1.21.f: Uma lista tem pelo menos dois elementos quando 1) ela não é vazia, e 2) não fica vazia se lhe tirarmos um elemento. Em Scheme:

      (define len2?
        (lambda (l)
          (and (not (null? l))
               (not (null? (cdr l))))))

Usando cond, podemos reescrever len2? como:

      (define len2?
        (lambda (l)
          (cond
            ((null? l) #f)
            ((null? (cdr l)) #f)
            (else #t))))

Exercício 1.23.c: O predicado (and (> x 5) (<= x 10)) é verdadeiro quando x (5,10]. Portanto, o predicado (not (and (> x 5) (<= x 10))) é verdadeiro quando x estiver fora desse intervalo. Uma outra forma de dizer que x está fora de um intervalo é dizer que, ou ele está abaixo do intervalo (x 5), ou que ele está acima (x>10). Em Scheme, (or (<= x 5) (> x 10)).
Exercício 2.2.d: Ao contrário de várias outras funções, não faz muito sentido definirmos a função máximo para uma lista vazia (mais formalmente, podemos dizer que a operação max não tem elemento neutro). Assim, nosso caso base será a lista com um único elemento, onde o maior elemento da lista é esse único valor. Para o caso recursivo, supomos que temos o resultado da chamada recursiva, (maximo (cdr l)). Tendo esse valor, qual o valor máximo da lista l? Ou é esse valor, ou é (car l), dependendo qual deles é maior. Mas para comparar apenas dois número já temos uma função pronta, chamada max. Juntando tudo, teremos:

      (define maximo
        (lambda (l)
          (if (null? (cdr l))  ; ultimo/unico elemento?
              (car l)
              (max (car l) (maximo (cdr l))))))

Note que a função não está definida para a lista vazia.
Exercício 2.2.e:

      (define pares?
        (lambda (l)
          (if (null? l)
              #t
              (and (even? (car l))
                   (pares? (cdr l))))))

Exercício 2.5.a:

      (define n-esimo
        (lambda (n l)
          (if (= n 1)   ; primeiro elemento?
              (car l)
              (n-esimo (- n 1) (cdr l)))))

Note que, se n for maior que o comprimento da lista, a lista irá terminar antes de n chegar a 1, e teremos um erro ao aplicar cdr sobre a lista vazia.
Exercício 2.6.i:

      (define pos-aux
        (lambda (e l n)
          (cond
            ((null? l) '())
            ((equal? e (car l)) n)
            (else (pos-aux e (cdr l) (+ n 1))))))


      (define pos (lambda (e l) (pos-aux e l 1)))

Exercício 2.21.c:

      (define comp (lambda (l) (acumula 0 (lambda (a e) (+ a 1)) l)))

Observação: dependendo da maneira como você implementou a função acumula, podem ser necessárias pequenas modificações na solução acima, como por exemplo trocar a ordem dos parâmetros a (acumulador) e e (elemento), ou mesmo a ordem dos argumentos na chamada de acumula.
Exercício 2.25: Fazendo uma tradução mecânica, teríamos:

      (define media-aux
        (lambda (l l1 s n)
          (if (null? l1)
              (/ s n)
              (media-aux l (cdr l1) (+ s (car l1)) (+ n 1)))))

      (define media (lambda (l) (media-aux l l 0 0)))

Em uma implementação normal, não precisaríamos do parâmetro l na função media-aux, pois ele não é utilizado.
Exercício 2.27.h: Uma implementação normal para essa função, usando-se recursão final, é mostrada abaixo:

      (define conta-aux
        (lambda (l1 e n)
          (if (null? l1)
              n
              (if (equal? e (car l1))
                  (conta-aux (cdr l1) e (+ n 1))
                  (conta-aux (cdr l1) e n)))))

      (define conta (lambda (l e) (conta-aux l e 0)))

Mas não sabemos como passar dessa forma para o do, pois temos duas ocorrências da chamada recursiva. Entretanto, a função conta-aux pode ser reescrita como abaixo, onde usamos o if diretamente no cálculo do novo valor de n:

  (define conta-aux
    (lambda (l1 e n)
      (if (null? l1)
          n
          (conta-aux (cdr l1) e (if (equal? e (car l1)) (+ n 1) n)))))

Agora, podemos transformar a recursão final para do diretamente:

      (define conta
        (lambda (l e)
          (do ((l1 l (cdr l1))
               (n 0 (if (equal? e (car l1)) (+ n 1) n)))
              ((null? l1) n))))

Exercício 3.16.b:

Exercício 3.17: Lembrando que as sub-árvores de uma folha são árvores vazias, temos:

      (define esquerda
        (lambda (a)
          (if (folha? a)
              arvore-vazia
              (cadr a))))

A função direita é definida analogamente. Assim como raiz, essas funções não estão definidas sobre a árvore vazia.
Exercício 3.20.d: Considerando que 3+4+5 é na realidade (3+4)+5, teremos a árvore:

Na representação pré-fixada, essa árvore resulta na lista (+ (+ 3 4) 5); na representação in-fixada, temos ((3 + 4) + 5); e na pós-fixada, ((3 4 +) 5 +).
Exercício 3.25: Se a árvore tem uma sub-árvore esquerda não vazia, seu menor elemento está nessa sub-árvore. Caso contrário, seu menor elemento é a própria raiz:

      (define menor
        (lambda (a)
          (if (vazia? (esquerda a))
              (raiz a)
              (menor (esquerda a)))))

Note que essa função não funcionará corretamente se chamada com a árvore vazia; isso apenas reflete o fato de que o valor do menor elemento de uma árvore vazia não é bem definido.
Exercício 3.27:

      (define insere
        (lambda (e a)
          (cond
          ((vazia? a) (cria-arvore e arvore-vazia arvore-vazia))
          ((= e (raiz a)) a)
          ((< e (raiz a)) (cria-arvore (raiz a)
                                       (insere e (esquerda a))
                                       (direita a)))
          (else (cria-arvore (raiz a)
                             (esquerda a)
                             (insere e (direita a)))))))

Exercício 4.1.d: A dificuldade neste exercício é saber quando mudar de linha. Uma solução convencional para esse problema é usarmos um contador, que nos diz quantos elementos já foram impressos. Sempre que esse contador for par, é hora de mudar de linha; caso contrário, apenas damos um espaço:

      (define (mostra-lista-aux l i)
        (if (not (null? l))
          (begin
            (display (car l))
            (if (even? i) (newline) (display " "))
            (mostra-lista-aux (cdr l) (+ i 1)))))


      (define (mostra-lista l) (mostra-lista-aux l 1))

O procedimento acima pode ser diretamente traduzido para usar um do:

      (define (mostra-lista l)
        (do ((l l (cdr l))
             (i 1 (+ i 1)))
            ((null? l))
            (display (car l))
            (if (even? i) (newline) (display " "))))

Exercício 4.3.a: Existem dois detalhes nesse procedimento. Primeiro, como o par de chaves deve ser mostrado uma única vez, em torno de uma repetição de elementos, sua exibição deve ser feita fora da repetição. Segundo, como as vírgulas aparecem entre os elementos, para n elementos temos apenas n-1 vírgulas. Uma solução para isso é só mostrarmos a vírgula após um elemento se ele não for o último.

      (define mostra-elementos
        (lambda (l)
          (do ((l l (cdr l)))
              ((null? l))
              (display (car l))
              (if (not (null? (cdr l))) (display ",")))))

      (define mostra-conjunto
        (lambda (c)
          (begin
            (display "{")
            (mostra-elementos c)
            (display "}")
            (newline))))

Exercício 4.5.c:

      (define le-lista
        (lambda ()
          (let ((v (read)))
            (if (zero? v)
                '(0)
                (cons v (le-lista))))))

Exercício 4.6.c:

      (define f
        (lambda (v)
          (/ (+ (vector-ref v 0)
                (vector-ref v (- (vector-length v) 1)))
             2)))

Exercício 4.7.b:

      (define vetor-lista-aux
        (lambda (v i)
          (if (= i (vector-length v))
              '()
              (cons (vector-ref v i) (vetor-lista-aux v (+ i 1))))))


      (define vetor-lista (lambda (v) (vetor-lista-aux v 0)))

Exercício 4.8:

      (define indice-maior
        (lambda (v i)
          (if (= i 0)
              0
              (let ((m (indice-maior v (- i 1))))
                (if (>= (vector-ref v i) (vector-ref v m))
                    i
                    m)))))

Exercício 4.11:

      (define troca
        (lambda (v i j)
           (let ((vi (vector-ref v i))
                 (vj (vector-ref v j)))
                (vector-set! v i vj)
                (vector-set! v j vi))))

Exercício 4.16: Para essa função, precisamos primeiro criar um vetor, depois preenchê-lo com os valores f(0), f(1), ..., f(n-1), e finalmente retornar o próprio vetor.

      (define cria-vetor
        (lambda (n f)
          (do ((v (make-vector n) v)
               (i 0 (+ i 1)))
              ((= i n) v)
              (vector-set! v i (f i)))))

Observe o v como valor final do do, que por sua vez é o valor final da função.
Exercício 4.18.a: A função (lambda (i) (cria-vetor n (lambda (j) 0))) é uma função que, quando chamada com qualquer argumento, cria um vetor com n zeros. Portanto, colocando essa função como argumento de outro cria-vetor, temos uma expressão que cria um vetor onde cada elemento é um vetor com n zeros, ou seja, uma matriz de zeros:

      (define cria-matriz-zeros
        (lambda (n m)
          (cria-vetor n (lambda (i)
                          (cria-vetor m (lambda (j) 0))))))

Notas de Pé de Pagina

f = x ^. 2x