Skip to content

Latest commit

 

History

History
70 lines (56 loc) · 2.18 KB

aula-17.org

File metadata and controls

70 lines (56 loc) · 2.18 KB

Aula 17

Discutimos sobre o exercício que pergunta a diferença das funções tree->list-1 e tree->list-2 abaixo. Uma tem custo linear e outra logarítmo.

(define (entry tree)
  (car tree))

(define (left-branch tree)
  (cadr tree))

(define (right-branch tree)
  (caddr tree))

(define (make-tree entry left right)
  (list entry left right))

(define (adjoin-set x set)
  (cond ((null? set) (make-tree x '() '()))
        ((= x (entry set)) set)
        ((< x (entry set))
         (make-tree (entry set) 
                    (adjoin-set x (left-branch set))
                    (right-branch set)))
        ((> x (entry set))
         (make-tree (entry set)
                    (left-branch set)
                    (adjoin-set x (right-branch set))))))

(define (tree->list-1 tree)
  (if (null? tree)
      '()
      (append (tree->list-1 (left-branch tree))
              (cons (entry tree)
                    (tree->list-1 (right-branch tree))))))

(define (tree->list-2 tree)
  (define (copy-to-list tree result-list)
    (if (null? tree)
        result-list
        (copy-to-list (left-branch tree)
                      (cons (entry tree)
                            (copy-to-list (right-branch tree)
                                          result-list)))))
  (copy-to-list tree '()))

No final da aula falamos sobre bibliotecas para gráficos e sobre as idéias de projeto.

Livros que comentei em sala:

Estes livros tem uma estrutura similar, onde cada capítulo apresenta um possível projeto bem definido. Podem servir de inspiração e/ou mesmo algum grupo pode se interessar por implementar o capítulo reproduzindo e melhorando alguma coisa.

Outro livro interessante, é o Programming Collective Intelligence (PCI). Uma idéia seria fazer o que este blog abaixo começou mas acho que não terminou, reimplementar os códigos em Lisp (Racket ou Common Lisp).