Aula 7

Implemente uma funçao que retorna T se seu argumento é uma arvore AVL. (Nota parcial se a funçao so verifica se a arvore á de busca binaria

;;; 1a versao abb
(defun abb? (a)
  (if (null a) T
      (let* ((esq (second a))
             (dir (third a))
             (no (first a))
             (abbesq (abb? esq))
             (abbdir (abb? dir))
             )
          (if (and abbesq abbdir 
                   (or (null esq)
                       (< (maior esq) no))
                   (or (null dir)
                       (< no (menor dir)))
                   )
                   T nil)
        )))

(defun maior (a)
   (if (null (third a)) (first a) 
       (maior (third a))
))

(defun menor (a)
   (if (null (second a)) (first a) 
       (menor (second a))
))

O código acima levemente deselegante pois passeia pelas sub arvores 2 vezes, uma para verificar se elas sao abb e a segunda para extrair o menor ou maior delas. Uma versao mais elegante verifica se as arvores sao abb e ao mesmo tempo obtem o maior e o menor de cada arvore

;;; 2a versao abb
(defun abb? (a)
  (if (null a) T 
      (if (abbaux a) T nil)
      ))

(defun abbaux (a)
;; retorna (menor maior) se sim ou nil se nao
  (if (null a) '(0 0)
      (let* ((esq (second a))
             (dir (third a))
             (no (first a))
             (abbesq (abbaux esq))
             (abbdir (abbaux dir))
             (menordir (first abbdir))
             (maioresq (second abbesq))
             )
          (if (and abbesq abbdir 
                   (or (null esq)
                       (< maioresq no))
                   (or (null dir)
                       (< no menordir))
                   )
                   (list (first esq) (second dir))
                   nil
        ))))

A 1a versao para o AVL, baseado na primeira versao do ABB

(defun avl? (a)
  (if (null a) T
      (let* ((esq (second a))
             (dir (third a))
             (no (first a))
             (avlesq (avl? esq))
             (avldir (abb? dir))
             (profdir (if (null dir) -20 (prof dir)))
             (profesq (if (null esq) -10 (prof esq)))
             )
          (if (and avlesq avldir 
                   (or (null esq)
                       (< (maior esq) no))
                   (or (null dir)
                       (< no (menor dir)))
                   (< (abs (- profesq profdir)) 2)
                   )
                   T nil)
        )))

(defun prof (a)
    (if (null a) 0
        (+ 1 (max (prof (second a)) (prof (third a))))
        ))

A 2a versao mais elegante

;;; 2a versao abb
(defun avl? (a)
  (if (null a) T 
      (if (avlaux a) T nil)
      ))

(defun avlaux (a)
;; retorna (menor maior profundidade) se sim ou nil se nao
  (if (null a) '(0 0 -1)
      (let* ((esq (second a))
             (dir (third a))
             (no (first a))
             (avlesq (avlaux esq))
             (avldir (avlaux dir))
             (menordir (first abbdir))
             (maioresq (second abbesq))
             (pesq (third avlesq))
             (pdir (third avldir))
             )
          (if (and avlesq avldir 
                   (or (null esq)
                       (< maioresq no))
                   (or (null dir)
                       (< no menordir))
                   (< (abs (- pesq pdir)) 2))
                   (list (first esq) (second dir) (+ 1 (max pesq pdir)))
                   nil
        ))))

• (mapcar fn lista) -> aplica a funçao fn em todos argumentos da lista

(defun soma1 (x) (+ 1 x))

(mapcar #'soma1 '(9 8 10 30)) -> (10 8 11 31)

• (mapcar fn lista1 lista2) aplica a função fn nos elementos correspondentes das listas

(mapcar #'- '(9 8 10 30) '(2 5 10 50)) -> (7 3 0 -20)

• funçoes anonimas

(mapcar #'(lambda (x) (+ 1 x)) '(9 8 10 30))

• (apply fn lista) chama a funçao fn com os elementos de lista como argumentos

(apply #'+ '(9 8 10 30)) -> 57

• (funcall fn arg1 arg2 .. argn) chama a funçao com argumentos arg1, arg2 ..argn)

(funcall #'+ 9 8 10 30) -> 57

• ache o menor de uma lista dada a funçao menor que é T se o primeiro argumento é menor que o segundo

(defun minz (l menor)
   (minzaux l menor (first l)))

(defun minzaux (l menor acc)
  (if (null l) acc
      (if (funcall menor (first l) acc) 
          (minzaux (rest l) menor (first l))
          (minzaux (rest l) menor acc)
          )))

(minz '(2 4 5 7 9 13) #'(lambda (a b)
                          (if (or (and (oddp a) (oddp b)) (and (evenp a) (evenp b))) (< a b)
                            (if (oddp a) T nil))))
                   

(defun ordenado? (l menor)
  (if (or (null l) (null (rest l))) T
      (let ((a (first l)) 
            (b (first (rest l))))
        (if (funcall menor a b) (ordenado? (rest l) menor)
            nil))))

(ordenado? '(5 11 4 8 10) #'(lambda (a b)
                               (if (or (and (oddp a) (oddp b)) (and (evenp a) (evenp b))) (< a b)
                                   (if (oddp a) T nil))))

• refaça os exercicios de matrizes usando o o mapcar, (mutiplicacao de 2 vetores é uma combinaçao de mapcar com apply!!)
• existe uma solucao para a transposta usando mapcar e apply que é espantosa.