Abstração de Dados

Lucas Vieira

Sistema para Números Racionais

Número racional

Racional é todo número que pode ser escrito na forma \(\frac{a}{b}\), onde \(a\) e \(b\) são números inteiros, com \(b\) diferente de \(0\):

\begin{equation*} \mathbb{Q} = \{\, x\, |\, \forall a \in \mathbb{Z};\, \forall b \in \mathbb{Z^{*}}: x = \frac{a}{b} \} \end{equation*}

Um número racional tem, então, dois componentes principais: numerador e denominador.

Podemos representar álgebras específicas para estes números, baseando-se nesta ideia.

Implementando operações com racionais

Suponha que tenhamos algum tipo de "nuvem", capaz de carregar as informações para uma fração (fraction). Suponha também que temos a seguinte função, em Lisp, que cria uma destas "nuvens".

(define (make-frac numer denom) ...)

Além de criar estas "nuvens", precisamos de formas para recuperar os dados que estas nuvens contém. Suponhamos, então, que podemos recuperar estas informações com estes procedimentos:

(define (frac-numer frac) ...)

(define (frac-denom frac) ...)

A implementação da forma com estas "nuvens" carregam a informação ficou a cargo do seu amigo, o Jorge. Sendo assim, estas implementações são irrelevantes para você, que só tem acesso à documentação, dizendo que elas foram implementadas.

Seu diretor pediu para que você ficasse responsável por implementar as seguintes operações:

  • +frac, que soma duas frações;
  • -frac, que subtrai duas frações;
  • *frac, que multiplica duas frações;
  • /frac, que divide duas frações;
  • frac-print, que imprime uma fração na tela, na forma a/b.

Sabendo apenas dos utilitários já implementados, costrua estas funções; não é necessário simplificar a fração.

Implementação de +frac

Nesta implementação, simplesmente construímos uma nova fração, e informamos qual será seu numerador e seu denominador.

  • O denominador é a multiplicação dos denominadores de a e b.
  • O numerador é a soma das multiplicações cruzadas entre o numerador de uma fração e o denominador da outra.
(define (+frac a b)
  (make-frac (+ (* (frac-numer a)
                   (frac-denom b))
                (* (frac-numer b)
                   (frac-denom a)))
             (* (frac-denom a)
                (frac-denom b))))

Implementação de frac-print

Podemos usar a função display, de Scheme, para resolver este problema.

(define (display-frac frac)
  (display (frac-numer frac))
  (display "/")
  (display (frac-denom frac))
  (display "\n"))

Células Cons

Cons cells são pares ordenados. Cada um dos elementos do par pode conter um tipo primitivo, ou outra cons cell.

(cons 1 2) ;; => (1 . 2)

Sintaxe

(cons <primeiro-elemento> <segundo-elemento>)

Recuperando dados de uma célula cons

(car (cons 1 2)) ;; -> 1
(cdr (cons 1 2)) ;; -> 2

Cons cells com outras cons cells no cdr

(cons 1 (cons 2 '() ))

ATENÇÃO: '() é um símbolo especial.

Listas

Listas são formadas por encadeamento de cons cells sucessivos, em seus respectivos cdr's.

(cons 1 (cons 2 (cons 3 (cons 4 '() ))))

(list 1 2 3 4) ; forma usando a função list
'(1 2 3 4)     ; forma de lista quotada

cons-cells.png

Cons'ar um valor ao início de uma lista cria uma nova lista, onde o valor cons'ado aparece no início.

(define *minha-lista* '(1 2 3 4))

(cons 5 *minha-lista*) ; => (5 1 2 3 4)

ATENÇÃO: Esta operação não altera a lista original!

Sintaxe

(list <e1> <e2> <e3> ... <en>)
'(<e1> <e2> <e3> ... <en>)

'() denota uma lista vazia, sendo o cdr da última cons cell de uma lista.

Quotar uma lista envolve transmitir o que está no interior dela como dados, na íntegra.

Se a criação da sua lista envolve alguma computação, é melhor utilizar list.

(list 1 2 (+ 3 4)) ;; => (1 2 7)
'(1 2 (+ 3 4))     ;; => (1 2 (+ 3 4))

Recuperando dados de uma lista

(car (list 1 2 3)) ;; -> 1
(cdr (list 1 2 3)) ;; -> (2 3)

;; Combinações de elementos pré-estabelecidas.
;; Evite, em prol de legibilidade
(cadr  (list 1 2 3)) ;; -> 2
(cddr  (list 1 2 3)) ;; -> (3)
(caddr (list 1 2 3)) ;; -> 3
;; etc...

Tipos diferentes de listas

A sintaxe de Lisp é completamente composta de listas. Se ignorarmos os casos especiais (special forms como if e cond), toda lista é uma aplicação de um procedimento (car) sobre os operandos (cdr).

(+ 1 2 3 4)

Em contrapartida, uma lista quotada ou gerada usando list está no "modo dados". Não existe aplicação inerente, apenas dados que podem ser percorridos e manipulados.

'(1 2 3 4 5)

Implementando números racionais

Como um número racional é um aglomerado de dois valores, podemos utilizar uma cons cell para representá-lo.

(define (make-frac numer denom)
  (cons numer denom))

Os componentes da fração podem ser recuperados usando as funções que recuperam informações de uma cons cell.

(define (frac-numer frac)
  (car frac))

(define (frac-denom frac)
  (cdr frac))

Note que cada uma das definições acaba por ter meramente o efeito de uma outra função que já existe em Scheme. Podemos cortar caminho definindo cada função diretamente como outra:

(define make-frac cons)
(define frac-numer car)
(define frac-denom cdr)

Isto diz respeito ao fato de funções serem também valores, uma característica que será abordada na próxima aula.

Exercícios

Exercício 1

Construa as funções -frac, *frac e /frac do exemplo com números racionais.

Exercício 2

Construa uma abstração para um ponto em um espaço bidimensional. Você deverá ter procedimentos para:

  • Criar um ponto;
  • Recuperar cada coordenada de um ponto qualquer.

Exercício 3

Construa uma abstração para um retângulo em um espaço bidimensional. Um retângulo possui uma localização no espaço e duas dimensões (largura e altura). Você deverá ter procedimentos para:

  • Criar um retângulo;
  • Recuperar o ponto no espaço em que está;
  • Recuperar sua largura;
  • Recuperar sua altura.

Exercício 4

Crie um predicado square? que informa se um retângulo é um quadrado. Utilize a abstração para retângulos implementada no Exercício 3.

Exercício-desafio

Crie uma função distance que informa a distância entre dois pontos. Utilize a abstração para pontos implementada no Exercício 2.

Dica: a função sqrt calcula a raiz quadrada de um número.