Lista 1 LISP (turma A)

Definições:

Vamos definir profundidade de um atomo em uma lista como sendo:

e assim por diante.

Ex: a profundidade de a na lista ((a) b c) é 2 pois a e' um elemento de um elemento da lista.

Da mesma forma podemos definir a profundidade de uma sublista em um lista. Assim a sublista (b c) tem profundidade 2 na lista (a ((b c) d) e)

Outra forma de pensar nisso é ver a lista (de listas) como sendo uma arvore.

A lista (a ((b c) d) e) pode ser vista como uma arvore

+ / | \ a + e / \ + d / \ b c Assim a profundidade de d na arvore é 2, e da lista (b c) tambem é 2.

Vamos definir a profundidade de uma lista como sendo a profundidade de seu atomo mais profundo.

Questão 1

Escreva a função super-sublista que dado duas listas verifica se a segunda é alguma sublista da primeira (em alguma profundidade)

Ex: (super-sublista '((a b) (c) (c (e f))) '(e f)) -> T

(super-sublista '((a b) (c) (c (e f))) '(c (e f))) -> T

(super-sublista '((a b) (c) (c (e f))) '(c e f)) -> NIL

Questão 2

Escreva a função poda que dado uma lista e um numero (a profundidade maxima), retorna a primeira lista com as sublistas com profundidade maior ou igual a profundidade maxima removidas.

Ex: (poda '((a b) (c) (c (e f) g )) 2) -> ((a b) (c) (c g))

(poda '(a b c) 2) -> (a b c)

(poda '(x (a b) (c) (c (e f) g )) 1) -> (x)

x não é sublista, portanto não foi removido

Questão 3

Vamos assumir que uma árvore de busca binaria (que armazena pares chave/valor) é representada em Lisp da seguinte forma:

( chave valor subarvore-a-esquerda subarvore-a-direita)

assim (4 a (2 b (1 h nil nil) (3 c nil nil)) (7 a nil (9 g nil nil))) representa a arvore:

4,a / \ 2,b 7,a / \ \ 1,h 3,c 9,g

Chaves são sempre interos, e os valores são quaisquer.

Escreva a função insere que dado um arvore binaria, uma chave e um valor qualquer retorna a arvore binaria com um novo no que armazena o par chave/valor se a chave não estiver na arvore original, ou apenas troca o valor armazenado sem o nó que contem tal chave.

Ex: se a arvore acima é o valor do simbolo xx então: (insere xx 2 'f) retorna
(4 a (2 f (1 h nil nil) (3 c nil nil)) (7 a nil (9 g nil nil))) pois 2 já esta armazenado na arvore.

(insere xx 8 'f) retorna
www(4 a (2 f (1 h nil nil) (3 c nil nil)) (7 a nil (9 g (8 f nil nil) nil)))