CLASS #2 - LISP
__________________

-> Listas: 

Em LISP, as listas constituem as estruturas de dados mais importantes na linguagem. 

Em LISP, as listas são contruídas usando uma cadeia de estrutras ligadas entre si designadas CONS 

-> CONS é constituído por dois componentes: o CAR (primeiro elemento) e o CDR (resto da lista).

-> A função CONS toma dois argumentos e retorna um par contendo esses dois elementos.

Ex:
> (cons 1 2) 						; (1 . 2)
> (cons 'a 'b)						; (A . B)
> (cons 1 nil)						; (1)
> (cons 1 (cons 2 nil))				; (1 2)
> (cons 1 (cons 2 (cons 3 nil)))	; (1 2 3)
> (cons 'a (cons 'b (cons 'c nil)))	; (A B C)

-> Outra maneira de criar listas é utilizando a função LIST:

> (list 1 2) 						; (1 2)
> (list 'a 'b)						; (A B)
> (list 1 nil)						; (1 NIL)
> (list 1 2 3)						; (1 2 3)
> (list 1 (list 2 nil))				; (1 (2 NIL))
> (list 1 (list 2 (list 3 5)))		; (1 (2 (3 5)))

-> O LISP fornece diversos operadores de manipulação de listas:

- CAR: selecciona o primeiro elemento da lista
> (car '(1 2 3))	; 1

- CDR: selecciona o resto da lista (devolve todos os elementos exepto o primeiro)
> (cdr '(1 2 3))	; (2 3)

-> Podemos combinar os operadores CAR e CDR de forma a seleccionar certos elementos da lista

- CADR = (CAR (CDR list)), ou seja, selecciona o segundo elemento da lista
> (cadr '(1 2 3))	; 2

- CAAR = (CAR (CAR list)), selecciona o primeiro elemento de um conjunto de listas
> (caar '( (1 2 3) (4 5))) 		; 1

- CADAR = (CAR (CDR (CAR list)))
> (CADAR '( (1 2 3) (4 5))) 	; 2

- CDAR	= (CDR (CAR list))
> (CDAR '( (1 2 3) (4 5)))		; (2 3)

-> Outra forma de seleccionar elementos de uma lista é usando os operadores FIRST, SECOND, etc

> (first '(1 2 3))	; 1
> (second '(1 2 3))	; 2
> (third '(1 2 3))	; 3 ...

-> Ou então, podemos usar a função NTH

> (nth 0 '(1 2 3))	; 1
> (nth 1 '(1 2 3))	; 2
> (nth 2 '(1 2 3))	; 3  ...

-> Operações sob listas:

- LENGTH: retorna o tamanho da lista
> (length '(1 2 3))		; 3

- APPEND: junta N listas de uma forma não destrutiva
> (setf l1 '(1 2 3))
> (setf l2 '(4 5 6))
> (setf l3 (append l1 l2))	; (1 2 3 4 5 6)
> l1						; (1 2 3)
> l2						; (4 5 6)

- NCONC: junta N listas de uma forma destrutiva (o primeiro argumento é destruido)
> (seft l3 (NCONC l1 l2))	; (1 2 3 4 5 6)
> l1						; (1 2 3 4 5 6)
> l2						; (4 5 6)

- SORT: ordena os elementos de uma lista de acordo com uma função.
> (sort '(4 1 2 5 3) #'< )		; (1 2 3 4 5)
> (sort '(4 1 2 5 3) #'> )		; (5 4 3 2 1)
> (sort '(4 1 2 5 3) #'= )		; (4 1 2 5 3)

; EXERCISE 1.7. ==========================================================================

[EX 1.7.1] (cons 2 ()) = (2)
[EX 1.7.2] (cons nil nil) = (NIL)
[EX 1.7.3] (cons '(1 2 3) '(a b c)) = ((1 2 3) A B C)
[EX 1.7.4] (cons 1 '(1 2 3)) = (1 1 2 3)
[EX 1.7.5] (first '(1 2 3)) = 1
[EX 1.7.6] (rest '(1 2 3)) = (2 3)
[EX 1.7.7] '(+ 1 2 3) = (+ 1 2 3)
[EX 1.7.8] (list 1 2 3) = (1 2 3)
[EX 1.7.9] (list 'a 'b 'c) = (A B C)
[EX 1.7.10] (list 1 (+ 1 2 3) 3) = (1 6 3)
[EX 1.7.11] (list 1 '(+ 1 2 3) 3) = (1 (+ 1 2 3) 3)
[EX 1.7.12] (append '(1 2 3) ’(a b c)) = (1 2 3 A B C)

; EXERCISE 1.11. ==========================================================================

(cons 												; builds ( (1 2 3) (3 5) (8)) 
	(cons 											; builds ( (1 2 3) (3 5) ) 
		(cons 1 (cons 2 (cons 3 nil))) 						; builds ( (1 2 3) )
		(cons (cons 3 (cons 5 nil)) nil)) 					; builds ( (3 5) )
	  (cons (cons 8 nil) nil))								; builds ( (8) ) 

; EXERCISE 1.14. ==========================================================================

(defun inverte_rec ( my_list )
"função inverte que recebe uma lista de elementos e retorna uma lista com os elementos
da lista argumento pela ordem inversa."
	(inverte_rec_aux my_list nil))

(defun inverte_rec_aux ( my_list param )
"função inverte que recebe uma lista de elementos e retorna uma lista com os elementos
da lista argumento pela ordem inversa."
	(if (null my_list)
		 param
		(inverte_rec_aux (rest my_list) (cons (first my_list) param )))) 	
			
(defun inverte_iter ( my_list )
"função inverte que recebe uma lista de elementos e retorna uma lista com os elementos
da lista argumento pela ordem inversa."
	(let ((res nil))
		(dotimes (i (length my_list)) 
			(setf res (cons (nth i my_list) res)))
		res))

; EXERCISE 1.15. ==========================================================================

(defun membro ( val my_list )
"função membro que recebe um elemento e uma lista de elementos e retorna verdade se o
elemento pertence à lista e falso em caso contrário"
	(loop for i in my_list do
		(when (eq val i)
			(return-from membro t ))) 
	nil)
		
; EXERCISE 1.16. ==========================================================================

(defun retira ( val my_list )
"função retira que recebe um elemento e uma lista de elementos e retorna uma lista que
corresponde à lista argumento à qual foram retiradas todas as ocorrências do elemento."
	(let ((res nil))
		(loop for i in my_list do
			(when (not (eq val i))  
				(setf res (append res (list i)))))
	res))
		
; EXERCISE 1.20. ==========================================================================
	
;; EXAMPLE USING LOW LEVEL FUNCTION
"função substitui que recebe dois elementos e uma lista de elementos e devolve a lista
com todas as ocorrências do primeiro elemento substituídas pelo segundo."
(defun substitui ( elem1 elem2 my_list )
  (cond ((atom my_list) my_list)
        ((equal elem1 (car my_list)) (substitui elem1 elem2 (append (list elem2) (cdr my_list))))
        ('otherwise
         (cons (substitui elem1 elem2 (car my_list))
               (substitui elem1 elem2 (cdr my_list))))))	
					
; EXERCISE 1.21. ==========================================================================

(defun interseccao ( list1 list2)
"função interseccao que recebe duas listas sem elementos repetidos e devolve uma lista
que contém todos os elementos em comum nas duas listas. Sugestão: Utilize a função member do
Common Lisp."
	(let ((res nil))
		(loop for i in list1 do
			(when (member i list2)	; found an intersection
				(setf res (append res (list i)))))
		res))
		
###########################################################################################

VECTORES:

- O LISP permite a definição de arrays com uma ou várias dimensões através da função MAKE-ARRAY.
- Um array pode guardar qualquer objecto.
- A indexação de um  aaray começa em 0.

-> Para criar um array, podemos usar a função MAKE-ARRAY
> (setf my-array (make-array '(10)))	; #(NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL)

-> Para aceder ao Nésimo elemento do array, usamos a função AREF
> (setf (aref my-array 3) -1)			; #(NIL NIL NIL -1 NIL NIL NIL NIL NIL NIL)
> (aref my-array 3)						; -1

-> Podemos criar uma matrix 2x2, fazendo
> (setf matrix (make-array '( 2 2 )))	; #2A((NIL NIL) (NIL NIL))

> (setf (aref matrix 0 0) 1)
> (setf (aref matrix 1 1) 1)
> (setf (aref matrix 0 1) 0)
> (setf (aref matrix 1 0) 0)

> matrix								; #2A((1 0) (0 1))

-> Podemos obter as dimensions de uma matriz usando:

> (array-dimensions matrix )			; (2 2)
> (array-dimensions my-array)			; (10)

> (array-dimension matrix 0)			; 2
> (array-dimension matrix 1)			; 2

; EXERCISE 1.29. ==========================================================================
(defvar *matrix1*  (make-array '(3 3) 
						:initial-contents'( (1 2 3) 
											(4 5 6)
											(7 8 9))))

(defvar *matrix2*  (make-array '(3 3) 
						:initial-contents'( (10 11 12) 
											(13 14 15)
											(16 17 18))))
(defvar *matrix3*  (make-array '(3 3) 
						:initial-contents'( (1 0 0) 
											(0 1 0)
											(0 0 1))))										
(defun soma-matrizes (matrix1 matrix2)
"função soma-matrizes que recebe duas tabela de 2 dimensões (x, y) de igual tamanho
arbitrário e retorna outra tabela que corresponde à soma das duas tabelas."
	(let ((size_x (array-dimension matrix1 0))
		   (size_y (array-dimension matrix1 1))
	       (matrix_sum (make-array (array-dimensions matrix1))))
	
		  (dotimes (i size_x)
		  	(dotimes (j size_y)
				(setf (aref matrix_sum i j) (+ (aref matrix1 i j) (aref matrix2 i j )))))
		matrix_sum))

; EXERCISE 1.30. ==========================================================================

(defun transpoe (matrix) 
"função transpoe que recebe uma tabela de 2 dimensões (x, y) de tamanho arbitrário e
retorna outra tabela que corresponde à transposição da tabela recebida em argumento."
	(let* ((size_x (array-dimension matrix 0))
		  (size_y (array-dimension matrix 1))
		  (transpose_matrix (make-array (list size_y size_x))))
		  
		  (dotimes (i size_x)
		  	(dotimes (j size_y)
				(setf (aref transpose_matrix j i) (aref matrix i j)) ))
		
		transpose_matrix))

; EXERCISE 1.31. ==========================================================================

(defun diagonal (matrix) 
"função diagonal que recebe uma tabela de 2 dimensões (x, y) de tamanho arbitrário e
retorna verdade se esta é uma tabela diagonal e falso em caso contrário"
	(let ((size_x (array-dimension matrix 0))
		  (size_y (array-dimension matrix 1)))
		  
		  (dotimes (i size_x)
		  	(dotimes (j size_y)
				(if (= i j)									; when a diagonal is found
					;; check if the elems are non-zero
					(when (eq (aref matrix i j) 0) 
						(return-from diagonal nil))	
					;; else, check if non-diagonal elems are zero	
					(when (not (eq (aref matrix i j) 0)) 
						(return-from diagonal nil))))) 
		t))
		
; EXERCISE 1.32. ==========================================================================

(defun copy-array-2-dim (matrix) 
"função copy-array-2-dim que recebe uma tabela bidimensional de tamanho arbitrário e retorna uma 
cópia dessa tabela"
	(let ((size_x (array-dimension matrix 0))
		  (size_y (array-dimension matrix 1))
		  (copy_matrix (make-array (array-dimensions matrix))))
		  
		  (dotimes (i size_x)
		  	(dotimes (j size_y)
				(setf (aref copy_matrix i j) (aref matrix i j)  )))
		copy_matrix))
		
#######################################################################################

ESTRUTURAS

-> As estruturas são um tipo de dados definido pelo programador, onde podemos combinar dados de diferentes tipos.
As estruturas servem para guardar certo tipo de informações.

-> Podemos definir uma estrutura usando a função DEFSTRUCT. 
-> Imaginemos que queremos criar um record de um livro:

> (defstruct book 
   	title 
   	author 
   	subject 
   	book-id 
)					; BOOK

-> A declaração acima cria uma estrutura do tipo BOOK. Cada vez que criarmos um objecto deste tipo, ele terá sempre
estas componentes.

-> Quando definimos uma estrutura, automaticamente são criadas as funções: 

* book-title
* book-author
* book-subject
* book-book-id

-> Estas funções servem para aceder aos campos da estrutura book.

Outra função que é automaticamente criada é:

* make-book: contrutor que cria uma estrutura do tipo book
* book-p:	testa se a estrura é do tipo book

(setf livro1 (make-book 
				:title "Retrato de Dorian Gray"
   			 	:author "Oscar Wilde" 
   			 	:subject "Literatura Clássica"
   			 	:book-id "478")
)

(setf livro2 (make-book 
				:title "O Alquimista"
   			 	:author "Paulo Coelho" 
   			 	:subject "Esoterismo"
   			 	:book-id "500")
)

> (book-author livro1) 		; "Oscar Wilde"
> (book-title livro1)		; "Retrato de Dorian Gray"
> (book-subject livro1)		; "Literatura Clássica"
> (book-book-id livro1)		; "478"

; EXERCISE 1.33. ==========================================================================

; Defina uma estrutura que representa informação sobre um modelo de carro. Considere que
; um modelo é caracterizado por uma marca, designação, potência, cilindrada e extras.
(defstruct modelo_carro
	marca
	designacao
	potencia
	cilindrada
	extras)

; Defina uma estrutura veículo que representa informação sobre um veículo. Considere que
; este é caracterizado por uma matrícula, ano de registo e um modelo de carro
(defstruct veiculo
	matricula
	ano_registo
	modelo_carro)

; Crie um veículo de matrícula 12-34-AB, ano de registo 1900, marca Rolls-Royce, designação
; Silver-Ghost, 300 Cv de potência, 20000cm3 de cilindrada e sem extras.

(defvar modeloA)
(setf modeloA (make-modelo_carro
				:marca "Rolls-Roice"
				:designacao "Silver-Ghost"
				:potencia 300
				:cilindrada 20000
				:extras nil))
				
(format t "[EX 1.33.2] modelo_carro: ~a~%~%" modeloA )
	
(defvar veiculo1)
(setf veiculo1 (make-veiculo 
		 			:matricula "12-34-AB"
					:ano_registo 1900
					:modelo_carro modeloA))
					
(format t "[EX 1.33.2] veiculo: ~a~%~%" veiculo1 )

(defun veiculo-cilindrada (veiculo)
"função veiculo-cilindrada que recebe um veículo e retorna a cilindrada desse veículo."
	(modelo_carro-cilindrada (veiculo-modelo_carro veiculo)))

(veiculo-cilindrada veiculo1)
(format t "[EX 1.33.4] (veiculo-cilindrada veiculo1) = ~a~%~%" (veiculo-cilindrada veiculo1) )

; EXERCISE 1.34. ==========================================================================

#|
  Defina uma estrutura estado que contenha a seguinte informação:
  Um campo tabuleiro: array de 3x3 que representa o tabuleiro do jogo. Cada posição
  conterá o símbolo X, O ou NIL, consoante tenha uma peça do jogador respectivo ou nenhuma peça
  Um campo proximo: irá conter o símbolo X ou O consoante o próximo jogador a jogar.
|#

(defstruct estado
	tabuleiro
	proximo
)

(defun cria-estado ()
"função cria-estado que devolve uma instância da estrutura do tipo estado,
devidamente inicializada, em que o primeiro jogador é o X."
	(let ((estado nil))
		(setf estado (make-estado
						:tabuleiro (make-array '(3 3))
						:proximo 'X))
	estado))

(defvar *estado1* (cria-estado))	
(format t "[EX 1.34.2] (cria-estado) = ~a~%~%" *estado1* )

(defun joga (est x y)
	(cond ((or (< x 0) (< y 0) (> x 2) (> y 2) ) nil)
		(T (setf (aref (estado-tabuleiro est) x y)
			(estado-proximo est)
			(estado-proximo est)
			(if (eql (estado-proximo est) 'X)
				'O
				'X))
		est)))

(format t "[EX 1.34.2] (joga *estado1* 1 3) = ~a~%" (joga *estado1* 1 2) )
(format t "[EX 1.34.2] After calling function Joga: *estado1*= ~a~%~%" *estado1* )

(format t "[EX 1.34.2] (let ((est (cria-estado))) (let ((est2 (joga est 1 1))) est2)) = ~a~%~%" (let ((est (cria-estado))) (let ((est2 (joga est 1 1))) est2)) )

(format t "[EX 1.34.2] (let ((est (cria-estado)) (est2 (joga est 1 1))) est2) = ERRO! Nao se pode atribuir a variavel est dentro do mesmo let~%~%")

(defvar *estado2* (cria-estado))	
(format t "[EX 1.34.2] (cria-estado) = ~a~%~%" *estado2* )

(defun joga2 (est x y)
	(cond ((or (< x 0) (< y 0) (> x 2) (> y 2)) nil)
		(T (let ((novo-est (copy-estado est)))
					(setf (aref (estado-tabuleiro novo-est) x y) 
					 		(estado-proximo novo-est) (estado-proximo novo-est)
					  (if (eql (estado-proximo novo-est) 'X)
					  		'O
							'X))
				novo-est))))

(format t "[EX 1.34.2] (joga2 estado 1 3) = ~a~%~%" (joga2 *estado1* 1 2) )
(format t "[EX 1.34.2] A funcao copy-estado cria uma instancia da estrutura estado. Quando fazemos uma altercao, essa alteracao e' feita internamente na estrutura principal~%~%")

;; you have to copy the hard way...
(defvar *estado3* (cria-estado))	
(format t "[EX 1.34.2] (cria-estado) = ~a~%~%" *estado3* )

(defun joga3 (estado x y)
	(let ((novo-estado (cria-estado))
		  (size (array-dimension (estado-tabuleiro estado) 0)))
		
	(dotimes (i size)
		(dotimes (j size)
			(setf (aref (estado-tabuleiro novo-estado) i j)
				  (aref (estado-tabuleiro estado) i j))))
	
	(setf (aref (estado-tabuleiro novo-estado) x y) (estado-proximo estado))
	
	;;check who will be the next player
	(if (eql (estado-proximo estado) 'X)
		(setf (estado-proximo novo-estado) 'O)
		(setf (estado-proximo novo-estado) 'X))
	
	novo-estado))

(format t "[EX 1.34.2] (joga3 *estado3* 1 2) = ~a~%~%" (joga3 *estado3* 1 2) )
(format t "[EX 1.34.2] After calling function Joga3: *estado3*= ~a~%~%" *estado3* )