\documentclass[a4paper,12pt,twoside]{book}

% Longitud del ancho del texto, para que no se desperdicie tanto
% espacio en los márgenes.
\setlength{\textwidth}{15.5cm}

\usepackage[spanish]{babel} % Etiquetas y silabeado en español
\usepackage{times}  % Usar Font Times Roman
\usepackage{t1enc}
\usepackage[T1]{fontenc}
\usepackage{verbatim}
\title{Biblioteca de funciones para \\
	Paradigmas de Programación}
\author{Lucas Di Pentima {\tt <lucas@lunix.com.ar>} }

\begin{document}

\setcounter{page}{1}
\pagenumbering{roman}

\maketitle
\clearpage
\tableofcontents
\clearpage

% Volvemos a la numeración normal antes de empezar con los contenidos
\pagenumbering{arabic}

%%%%%%%%%%%%%%%%%%%%
% Capítulo: SCHEME %
%%%%%%%%%%%%%%%%%%%%
\chapter{Programación Funcional: Scheme}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Sección: Procesamiento de grafos %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Grafos}

\subsection{es-conexo?/1}
Retorna \textbf{True} si el grafo es conexo

\begin{verbatim}
; Representación del grafo: Lista de listas (pares) 
; de vértices conectados
; Ejemplo: (es-conexo? '((a b) (a d) (b d) (b c) (d g) (e f)))

; Retorna el 1er vértice del par
(define vertice1
  (lambda (par)
    (car par)))

; Retorna el 2do vértice del par
(define vertice2
  (lambda (par)
    (cadr par)))

; Construye un par con los vértices dados
(define conspar
  (lambda (v1 v2)
    (list v1 v2)))

; Da vuelta el par dado
(define davuelta
  (lambda (par)
    (conspar (vertice2 par)
             (vertice1 par))))

; Retorna true si el par existe en el grafo dado
(define existe-par?
  (lambda (par grafo)
    (if (miembro par grafo)
        #t
        (if (miembro (davuelta par) grafo)
            #t
            #f))))

; Retorna true si el vértice existe en el par dado
(define en-par?
  (lambda (v par)
    (if (or (equal? (vertice1 par) v)
            (equal? (vertice2 par) v))
        #t
        #f)))

; Retorna el otro vértice del par dado que no sea v
(define el-otro
  (lambda (v par)
    (if (equal? v (vertice1 par))
        (vertice2 par)
        (vertice1 par))))

; Retorna el grafo sin el par dado
(define saca-par
  (lambda (par grafo)
    (if (null? grafo) 
        '()
        (if (or (equal? par (car grafo))
                (equal? (davuelta par) (car grafo)))
            (cdr grafo)
            (cons (car grafo) (saca-par par (cdr grafo)))))))

; Retorna el primer par donde haya el vértice dado en el grafo
(define buscar-par
  (lambda (x grafo)
    (cond
     ((null? grafo) '())
     ((en-par? x (car grafo)) (car grafo))
     (else (buscar-par x (cdr grafo))))))

; Retorna true si existe un camino entre los vértices 
; dados en el grafo
(define hay-camino?
  (lambda (x y grafo)
    (int grafo grafo x y)))

; Función interna de <<hay-camino?>>
(define int
  (lambda (grafo-orig grafo-mod x y)
    (cond
     ((existe-par? (conspar x y) grafo-orig) #t)
     ((null? grafo-mod) #f)
     ((null? (buscar-par x grafo-mod)) #f)
     (else
      (if (int grafo-orig (saca-par (buscar-par x grafo-mod) 
                                    grafo-mod)
               (el-otro x (buscar-par x grafo-mod)) y)
          #t
          (int grafo-orig (saca-par (buscar-par x grafo-mod) 
                                    grafo-mod)
               x y))))))

; Retorna true si el grafo dado es conexo
(define es-conexo?
  (lambda (grafo)
    (cond
     ((null? grafo) #t)
     ((null? (cdr grafo)) #t)
     (else
      (es-conexo-int (car (saca-dupes (flatten grafo))) 
                     (cdr (saca-dupes (flatten grafo)))
                     grafo)))))

; Función interna de <<es-conexo?>>
(define es-conexo-int
  (lambda (v listav grafo)
    (cond
     ((null? listav) #t)
     ((hay-camino? v (car listav) grafo) 
      (es-conexo-int v (cdr listav) grafo))
     (else #f))))
\end{verbatim}

%%%%%%%%%%%%%%%%%%%%%%%%
% Sección: Misceláneos %
%%%%%%%%%%%%%%%%%%%%%%%%
\section{Misceláneos}

\subsection{display-tower-of-hanoi/1}
Soluciona la Torre de Hanoi

\begin{verbatim}
(define display-tower-of-hanoi
  (let ((show-move (lambda (s d) 
                     (display s)
                     (display " -> ")
                     (display d))))
    (lambda (n)
      (letrec 
        ((move 
           (lambda (n source destination helper)
             (if (= n 1) 
                 (begin
                   (show-move source destination) 
                   (newline))
                 (begin
                   (move (- n 1) source helper destination)
                   (show-move source destination)
                   (display ", ")
                   (move (- n 1) helper destination source))))))
        (move n 'L 'R 'C)))))
\end{verbatim}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Sección: Procesamiento de Números %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Procesamiento de Números}

\subsection{divides-by/2}
Retorna \textbf{True} si el primer argumento es divisible por el
segundo

\begin{verbatim}
(define divides-by
  (lambda (n)
    (lambda (k)
      (zero? (remainder k n)))))
\end{verbatim}

\subsection{fact/1}
Calcula el factorial del número pasado por parámetro

\begin{verbatim}
(define fact
  (lambda (int)
    (if (zero? int)
        1
        (* int (fact (- int 1))))))
\end{verbatim}

\subsection{fib/1 y fib2/1}
Dos versiones de una función que calcula números de la serie de
Fibonacci, la primer función lo hace mediante un proceso iterativo y
la segunda mediante un proceso recursivo.

\begin{verbatim}
; Fibonacci iterativo
(define fib
  (lambda (n)
    (fib-iter 1 0 n)))

(define fib-iter
  (lambda (a b count)
    (if (= count 0)
        b
        (fib-iter (+ a b) a (- count 1)))))

; Fibonacci recursivo
(define fib2
  (lambda (n)
    (cond ((= n 0) 0)
          ((= n 1) 1)
          (else (+ (fib2 (- n 1))
                   (fib2 (- n 2)))))))
\end{verbatim}

\subsection{fib/1}
Calcula el número de Fibonacci del número pasado por parámetro

\begin{verbatim}
(define fib
  (lambda (int)
    (if (< int 2) 
        int
        (+ (fib (- int 1)) (fib (- int 2))))))
\end{verbatim}

\subsection{fact-it/2}
Calcula el factorial del número pasado por parámetro, iterativamente

\begin{verbatim}
(define fact-it
  (lambda (int acc)
    (if (zero? int)
        acc
        (fact-it (- int 1) (* acc int)))))
\end{verbatim}

\subsection{fib-it/2}
Calcula el número de Fibonacci del número pasado por parámetro,
iterativamente

\begin{verbatim}
(define fib-it
  (lambda (int acc1 acc2)
    (if (= int 1)
        acc2
        (fib-it (- int 1) acc2 (+ acc1 acc2)))))
\end{verbatim}

\subsection{even?/1}
Devuelve \textbf{True} si el número argumento es par.

\begin{verbatim}
(define even? 
  (lambda (int)
    (if (zero? int)
        #t
        (odd? (- int 1)))))
\end{verbatim}

\subsection{odd?/1}
Devuelve \textbf{True} si el número argumento es impar.

\begin{verbatim}
(define odd?
  (lambda (int)
    (if (zero? int)
        #f
        (even? (- int 1)))))
\end{verbatim}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Sección: Procesamiento de Listas %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Procesamiento de Listas}

\subsection{saca-dupes/1}
Toma como argumento una lista y devuelve otra lista con los elementos
duplicados eliminados

\begin{verbatim}
(define saca-dupes
  (lambda (lista)
    (saca-dupes-int lista '())))

(define saca-dupes-int
  (lambda (lista1 lista2)
    (cond
     ((null? lista1) lista2)
     ((not (miembro (car lista1) lista2)) 
      (saca-dupes-int (cdr lista1) (cons (car lista1) lista2)))
     (else
      (saca-dupes-int (cdr lista1) lista2)))))
\end{verbatim}

\subsection{remove/2}
Elimina todas las ocurrencias del item pasado como primer argumento en
la lista del segundo argumento.

\begin{verbatim}
(define remove
  (lambda (item ls)
    (cond
      ((null? ls) '())
      ((equal? (car ls) item) (remove item (cdr ls)))
      (else (cons (car ls) (remove item (cdr ls)))))))
\end{verbatim}

\subsection{count-all/1}
Cuenta todos los items en la lista pasada como argumento. Si la lista
es una lista de listas, contará también todos los ítems de las listas
internas.

\begin{verbatim}
(define count-all
  (lambda (ls)
    (cond
      ((null? ls) 0)
      ((not (pair? (car ls))) (+ 1 (count-all (cdr ls))))
      (else (+ (count-all (car ls)) (count-all (cdr ls)))))))
\end{verbatim}

\subsection{remove-all/2}
Elimina todas las ocurrencias del item pasado como primer argumento en
la lista pasada como segundo argumento. Si la lista es una lista de
listas, se eliminarán las ocurrencias del item en las listas
interiores también.

\begin{verbatim}
(define remove-all
  (lambda (item ls)
    (cond
      ((null? ls) '())
      ((equal? (car ls) item) (remove-all item (cdr ls)))
      ((pair? (car ls)) 
       (cons (remove-all item (car ls)) 
             (remove-all item (cdr ls))))
      (else (cons (car ls) (remove-all item (cdr ls)))))))
\end{verbatim}



\subsection{last-item/1}
Da como resultado el último ítem de una lista

\begin{verbatim}
(define last-item
  (lambda (ls)
    (cond
      ((null? (cdr ls)) (car ls))
      (else (last-item (cdr ls))))))
\end{verbatim}

\subsection{remove-1st/2}
Elimina la primer ocurrencia del item en la lista

\begin{verbatim}
(define remove-1st
  (lambda (item ls)
    (cond
      ((null? ls) '())
      ((equal? (car ls) item) (cdr ls))
      (else (cons (car ls) (remove-1st item (cdr ls)))))))
\end{verbatim}

\subsection{swapper/3}
Reemplaza todas las ocurrencias del primer argumento, por el segundo
argumento en la lista del tercer argumento

\begin{verbatim}
(define swapper 
  (lambda (x y ls) 
    (cond
      ((null? ls) '())
      ((equal? (car ls) x) 
       (cons y (swapper x y (cdr ls))))
      ((equal? (car ls) y) 
       (cons x (swapper x y (cdr ls))))
      (else 
       (cons (car ls) (swapper x y (cdr ls)))))))
\end{verbatim}

\subsection{atom?/1}
Retorna \textbf{True} si el parámetro es un átomo

\begin{verbatim}
(define atom?
  (lambda (obj)
    (not(list? obj))))
\end{verbatim}

\subsection{concatenar/2}
Concatena ambas listas pasadas como parámetros y devuelve el resultado

\begin{verbatim}
(define concatenar
  (lambda (lista1 lista2)
    (if (or
         (atom? lista1)
         (atom? lista2))
        '()
        (concatenar-iter lista1 lista2 '()))))

(define concatenar-iter
  (lambda (lista1 lista2 listares)
    (if (not (null? lista1))
        (concatenar-iter (cdr lista1) lista2 
                         (cons (car lista1) listares))
        (if (not (null? lista2))
            (concatenar-iter lista1 (cdr lista2) 
                             (cons (car lista2) listares))
            (reverse listares)))))
\end{verbatim}

\subsection{flatten/1}
Toma como parámetro una lista (que puede tener listas adentro) y
retorna una lista con los átomos de esa lista de listas

\begin{verbatim}
(define flatten
  (lambda (lista)
    (if (null? lista)
        '()
        (if (atom? (car lista))
            (cons (car lista) (flatten (cdr lista)))
            (concatenar (flatten (car lista)) 
                        (flatten (cdr lista)))))))
\end{verbatim}

\subsection{cuadLista/1}
Dada una lista obtener una lista con los cuadrados de cada elemento de
la lista.

\begin{verbatim}
(define (cuad n)
    (* n n))

(define (cuadLista l)
    (if (null? l) l
        (cons (cuad (car l))
            (cuadLista (cdr l)))))
\end{verbatim}

\subsection{incLista/1}
Dada una lista obtener una lista con los elementos incrementados en uno.

\begin{verbatim}
(define (inc n)
    (+ 1 n))

(define (incLista l)
    (if (null? l) l 
        (cons (inc (car l))
            (incLista (cdr l)))))
\end{verbatim}

\subsection{parLista/1}
Dada una lista obtener una lista donde cada elemento x de la lista
original se reemplaza por el par (x x).

\begin{verbatim}
(define (par n)
    (cons n n))

(define (parLista l)
    (if (null? l) l
        (cons (par (car l))
            (parLista (cdr l)))))
\end{verbatim}

\subsection{negLista/1}
Dada una lista obtener el resultado de evaluar si el elemento es
negativo o no.

\begin{verbatim}
(define (neg n)
    (< n 0))

(define (negLista l)
    (if (null? l) l 
         (cons (neg (car l))
             (negLista (cdr l)))))
\end{verbatim}

\subsection{map}
Genere la función \emph{map} que aplica el primer argumento al segundo
y reescriba las funciones anteriores \emph{cuadLista},
\emph{incLista}, \emph{parLista} y \emph{negLista} utilizando map.

\begin{verbatim}
(define map
    (lambda (f)
        (lambda (l)
            (if (null? l) l
                (cons (f (car l)) ((map f) (cdr l)))))))

(define cuadLista2
    (map cuad))

(define incLista2
    (map inc))

(define parLista2
    (map par))

(define negLista2
    (map neg))
\end{verbatim}

\subsection{long/1}
Longitud de una lista

\begin{verbatim}
(define (long l)
    (if (null? l) 0 (+ 1 (long (cdr l)))))
\end{verbatim}

\subsection{concat/2}
Concatena dos listas

\begin{verbatim}
(define concat
    (lambda (x y)
        (if (null? x)
            y
            (cons (car x) (concat (cdr x) y)))))
\end{verbatim}

\subsection{reverse/1}
Invierte una lista

\begin{verbatim}
(define reverse
    (lambda (l)
        (if (null? l) 
            '()
            (concat (reverse (cdr l)) (cons (car l) '())))))
\end{verbatim}

\subsection{member?/2}
Determina si un elemento es miembro de una lista

\begin{verbatim}
(define member?
  (lambda (item ls)
    (cond
      ((null? ls) #f)
      (else (or (equal? (car ls) item) 
                (member? item (cdr ls)))))))
\end{verbatim}

\subsection{derivaPol/1}
Deriva un Polinomio

\begin{verbatim}
(define consTno
    (lambda (coef exp) (cons coef exp)))

(define coef
    (lambda (t) (car t)))

(define exp
    (lambda (t) (cdr t)))

(define derivaTno
    (lambda (t)
        (if (eqv? (exp t) 0)
            (consTno 0 0)
            (constno
                (* (coef t) (exp t))
                (- (exp t) 1)))))

(define derivaPol
    (lambda (p)
        ((map derivaTno) p)))
\end{verbatim}

\subsection{minimo/1}
Halla el mínimo de una lista

\begin{verbatim}
(define (minimo l)
    (if (null? l) l
        (if (null? (cdr l)) (car l)
            (if (< (car l) (minimo (cdr l)))
                (car l)
                (minimo (cdr l))))))
\end{verbatim}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Sección: Árboles Binarios %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Árboles Binarios}
Representación de árboles binarios como listas
\begin{verbatim}
arbol := nil | (cont arbol arbol)
\end{verbatim}

\subsection{vacio?/1}
Devolver TRUE si el árbol es vacío.

\begin{verbatim}
(define (vacio? arb)
        (if (eq? arb 'nil) #t
            #f))
\end{verbatim}

\subsection{der/1}
Retorna la rama derecha de un árbol.

\begin{verbatim}
(define (der arb)
        (caddr (arb)))
\end{verbatim}

\subsection{izq/1}
Retorna la rama izquierda de un árbol.

\begin{verbatim}
(define (izq arb)
        (cadr arb))
\end{verbatim}

\subsection{contar/1}
Contar la cantidad de elementos de un árbol

\begin{verbatim}
(define (contar arb)
    (if (vacio? arb) 0
        (+ (contar (izq arb))
            (contar (der arb))
            1)))
\end{verbatim}

\subsection{raiz/1}
Devuelve la raiz del árbol.

\begin{verbatim}
(define (raiz arb)
    (car arb))
\end{verbatim}

\subsection{pertenece/2}
Determina si un elemento pertenece a un árbol o no.

\begin{verbatim}
(define (pertenece elem arb)
    (if (vacio? arb) #f
        (or (eqv? elem (raiz arb))
            (pertenece elem (izq arb))
            (pertenece elem (der arb)))))
\end{verbatim}

\subsection{inorden/1}
Obtiene la lista de recorrer en inorden un árbol binario

\begin{verbatim}
(define (inorden arb)
    (if (vacio? arb) #f
        (append (inorden (izq arb))
                (list (raiz arb))
                (inorden (der arb)))))
\end{verbatim}

\subsection{preorden/1}
Obtiene la lista de recorrer en preorden un árbol binario

\begin{verbatim}
(define (preorden arb)
    (if (vacio? arb) #f
        (append (list (raiz arb))
                (preorden (izq arb))
                (preorden (der arb)))))
\end{verbatim}

\subsection{posorden/1}
Obtiene la lista de recorrer en posorden un árbol binario

\begin{verbatim}
(define (posorden arb)
    (if (vacio? arb) #f
        (append (posorden (izq arb))
                (posorden (der arb))
                (list (raiz arb)))))         
\end{verbatim}

%%%%%%%%%%%%%
% SMALLTALK %
%%%%%%%%%%%%%
% \chapter{Programacion Orientada a Objetos: SmallTalk}

%%%%%%%%%%
% PROLOG %
%%%%%%%%%%
\chapter{Programación en Lógica: Prolog}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Sección: Combinatoria de Listas %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Combinatoria de Listas}

\subsection{perm/2}
Permutation of the list L is a list containing all elements of list L
in some order. Guess which permutation is generated first usign
following procedure. And what about second?

\begin{verbatim}
perm(List,[H|Perm]) :- delete(H,List,Rest),
        perm(Rest,Perm).
perm([],[]).
       
delete(X,[X|T],T).
delete(X,[H|T],[H|NT]) :- delete(X,T,NT).
\end{verbatim}

\subsection{comb/3}
Combination is an arbitrary subset of the set containing given number
of elements. The order of elements is irrelevant.
\begin{verbatim}
comb(0,_,[]).
comb(N,[X|T],[X|Comb]) :- N > 0,
        N1 is N-1,
        comb(N1,T,Comb).
comb(N,[_|T],Comb) :- N > 0,
        comb(N,T,Comb).
\end{verbatim}

\subsection{varia/3}
Variation is a subset with given number of elements. The order of
elements in variation is significant.
\begin{verbatim}
varia(0, _, []).
varia(N, L, [H|Varia]) :- N > 0,
        N1 is N - 1,
        delete(H, L, Rest),
        varia(N1, Rest, Varia).
\end{verbatim}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Sección: Ordenamiento de Listas %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Ordenamiento de Listas}

\subsection{lstOrdMayor/1}
Determina si la lista está ordenada de mayor a menor

\begin{verbatim}
lstOrdMayor([]).
lstOrdMayor([X]).
lstOrdMayor([X,Y|Xs]) :- X >= Y,
        lstOrdMayor([Y|Xs]).
\end{verbatim}

\subsection{lstOrdMenor/1}
Determina si la lista está ordenada de menor a mayor

\begin{verbatim}
lstOrdMenor([]).
lstOrdMenor([X]).
lstOrdMenor([X,Y|Xs]) :- X =< Y,
        lstOrdMenor([Y|Xs]).
\end{verbatim}

\subsection{ordLstMenor/2}
Ordena una lista de menor a mayor

\begin{verbatim}
ordLstMenor([],[]).
ordLstMenor([L|LS],[Menor|LS2]) :- sacarMenor([L|LS],L1,Menor),
        ordLstMenor(L1,LS2).
\end{verbatim}

\subsection{ordLstMayor/2}
Ordena una lista de mayor a menor

\begin{verbatim}
ordLstMayor([],[]).
ordLstMayor([L|LS],[Mayor|LS2]) :- sacarMayor([L|LS],L1,Mayor),
        ordLstMayor(L1,LS2).
\end{verbatim}

\subsection{naive\_sort/2}
Naive sort is not very efficient algorithm. It generates all
permutations and then it tests if the permutation is a sorted list.
\begin{verbatim}
naive_sort(List,Sorted):-perm(List,Sorted),is_sorted(Sorted).
       
is_sorted([]).
is_sorted([_]).
is_sorted([X,Y|T]) :- X <= Y,
        is_sorted([Y|T]).
\end{verbatim}

\subsection{insert\_sort/2}
Insert sort is a traditional sort algorithm. Prolog implementation of
insert sort is based on idea of accumulator.

\begin{verbatim}
insert_sort(List, Sorted) :- i_sort(List, [], Sorted).
i_sort([], Acc, Acc).
i_sort([H|T], Acc, Sorted) :- insert(H,Acc,NAcc),
        i_sort(T,NAcc,Sorted).
       
insert(X, [Y|T], [Y|NT]) :- X > Y,
        insert(X,T,NT).
insert(X, [Y|T], [X,Y|T]) :- X <= Y.
insert(X, [], [X]).
\end{verbatim}

\subsection{quick\_sort/2}
Quick sort is one of the fastest sort algorithms. However, its power
is often overvalued. The efficiency of quick sort is sensitive to
choice of pivot which is used to distribute list into two "halfs".
\begin{verbatim}
quick_sort([], []).
quick_sort([H|T], Sorted) :- pivoting(H, T, L1, L2),
        quick_sort(L1, Sorted1),
        quick_sort(L1, Sorted2),
        append(Sorted1,[H|Sorted2]).
       
pivoting(H, [], [], []).
pivoting(H, [X|T], [X|L], G) :- X <= H,
        pivoting(H, T, L, G).
pivoting(H, [X|T], L, [X|G]) :- X > H,
        pivoting(H, T, L, G).
\end{verbatim}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Sección: Misceláneos de Listas %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Misceláneos de Listas}

\subsection{flatten/2}
Retorna una lista con los átomos de la lista pasada por argumento

\begin{verbatim}
flatten([],[]).
flatten([X|Y],[X|R]) :- atomic(X),
        flatten(Y,R).
flatten([X|Y],R) :- not(atomic(X)),
        flatten(X,L),
        flatten(Y,Q),
        concatenar(L,Q,R).
\end{verbatim}

\subsection{longitud/2}
Devuelve la longitud de una lista

\begin{verbatim}
longitud([],0).
longitud([X|Y],Z) :- longitud(Y,F),
        Z is F + 1.
\end{verbatim}

\subsection{sacarUno/3}
Saca la primer ocurrencia del primer parámetro dentro de la lista, y
además devuelve la lista sin ese elemento

\begin{verbatim}
sacarUno(X,[X|Xs],Xs).
sacarUno(X,[Y],[Y]) :- X \== Y,!.
sacarUno(X,[Y|Ys],[Y|L2]) :- X \== Y,
        sacarUno(X,Ys,L2).
\end{verbatim}

\subsection{sacarMayor/3}
Devuelve el mayor de la lista y la lista sin el mayor

\begin{verbatim}
sacarMayor(L,L2,M) :- max(L,M),
        sacarUno(M,L,L2),!.
sacarMayor([X],[],X).
\end{verbatim}

\subsection{sacarMenor/3}
Devuelve el menor de la lista y la lista sin el menor

\begin{verbatim}
sacarMenor(L,L2,M) :- min(L,M),
        sacarUno(M,L,L2),!.
sacarMenor([X],[],X).
\end{verbatim}

\subsection{reverse/2}
Da vuelta una lista
\begin{verbatim}
reverse(L1, L2) :- reserse(L1, [], L2).

reverse([], SoFar, SoFar).
reverse([H|T], SoFar, Final) :- 
        reverse(T, [H|SoFar], Final).
\end{verbatim}

\subsection{last/2}
Devuelve el último elemento de la lista que se pasa como segundo argumento
\begin{verbatim}
last(X, [X]).
last(X, [_|Y]) :- last(X,Y).
\end{verbatim}

\subsection{nextto/3}
Devuelve \textbf{Yes} si el primer y segundo argumento se encuentran
consecutivos en la lista que se pasa como tercer argumento.
\begin{verbatim}
nextto(X,Y,[X,Y|_]).
nextto(X,Y,[_|Z]) :- nextto(X, Y, Z).
\end{verbatim}

\subsection{remdup/2}
Dada una lista, elimina los elementos duplicados de dicha lista.
\begin{verbatim}
remdup(L,M) :- dupacc(L,[],M).

dupacc([],A,A).
dupacc([H|T],A,L) :- member(H,A), !, dupacc(T,A,L).
dupacc([H|T],A,L) :- dupacc(T,[H|A],L).
\end{verbatim}

\subsection{concatenar/3}
Concatena la primer lista con la segunda que se le pasa como
parámetro, asignando el resultado al tercer parámetro.
\begin{verbatim}
concatenar([],L,L).
concatenar([Head|Tail], L, [Head | X]) :-
        concatenar(Tail, L, X). 
\end{verbatim}

\subsection{esLista/1}
Devuelve \textbf{Yes} si el parámetro que se le pasa es un átomo
(recordar que los números no se consideran átomos).
\begin{verbatim}
esLista(L) :- not(atom(L)), not(number(L)).
\end{verbatim}

\subsection{listaAtomos/2}
Toma como primer parámetro una lista (que puede ser una lista de
listas) y asigna al segundo parámetro una lista con todos los átomos
constituyentes de la primer lista.
\begin{verbatim}
listaAtomos([], []).
listaAtomos([H|T], [H|L]) :- atom(H),
        listaAtomos(T, L).
listaAtomos([H|T], L) :- esLista(H),
        listaAtomos(H,L1),
        listaAtomos(T,L2),
        concatenar(L1, L2, L).
\end{verbatim}

\subsection{pertenece/2}
Toma dos argumentos, el primero es un elemento y el segundo es una
lista simple de elementos. Devuelve \textbf{Yes} si el elemento
pertenece a esa lista simple.
\begin{verbatim}
pertenece(X, [X|_]).
pertenece(X, [Y|L]) :- not(X = Y),
        pertenece(X, L).
\end{verbatim}

\subsection{max/2}
Retorna el mayor elemento de una lista

\begin{verbatim}
max([X],X) :- !.
max([X|Xs],X) :- max(Xs,Y), 
        X > Y,!.
max([X|Xs],Y) :- max(Xs,Y), 
        X =< Y.
\end{verbatim}

\subsection{min/2}
Retorna el menor elemento de una lista

\begin{verbatim}
min([X],X) :- !.
min([X|Xs],X) :- min(Xs,Y),
        X < Y,!.
min([X|Xs],Y) :- min(Xs,Y),
        X >= Y.
\end{verbatim}

\subsection{sacaElem/3}
Toma como primer argumento una lista, como segundo argumento el
elemento a quitar de la lista y como tercer argumento la lista
obtenida.
\begin{verbatim}
sacaElem([], _, []).
sacaElem([H|T], H, T) :- !.
sacaElem([H|T], E, [H|L]) :- sacaElem(T, E, L).
\end{verbatim}

\subsection{nMayores/3}
Toma como primer argumento una lista de números enteros positivos,
como segundo elemento un número que se refiere a la cantidad de
números mayores a extraer de la lista anterior, y como tercer elemento
la lista con los N elementos mayores de la primer lista.
\begin{verbatim}
nMayores([], _, []).
nMayores(_, 0, []).
nMayores(L, N, [H|T]) :- N > 0,
        mayor(L,H),
        sacaElem(L, H, L2),
        M is N - 1,
        nMayores(L2, M, T).
\end{verbatim}

\subsection{esSublista/2}
Toma como primer argumento una lista y como segundo argumento otra
lista. Devuelve \textbf{Yes} si la primer lista es sublista de la
segunda.
\begin{verbatim}
esSublista([], _).
esSublista([H|T], [H|L]) :- esSublista(T, L).
esSublista(L, [_|T]) :- esSublista(L, T).
\end{verbatim}

\subsection{sustElem/4}
Toma como primer argumento una lista, como segundo argumento, el
elemento a buscar, como tercer argumento, el elemento a usar como
reemplazo del anterior, y como cuarto argumento, la lista resultante.
Ejemplo:
\begin{verbatim}
           sust([a,b,c,d,[l,a],b,c,[l,a]],[l,a],[c],T)
           T=[a,b,c,d,[c],b,c,[c]]
\end{verbatim}
\begin{verbatim}
sustElem([], _, _, []).
sustElem(L, L, L2, L2).
sustElem([H1|T1], H1, P2, [P2|T2]) :- 
        sustElem(T1, H1, P2, T2), !.
sustElem([H1|T1], P1, P2, [H1|L]) :- 
        sustElem(T1, P1, P2, L).
\end{verbatim}

\subsection{ocurre/2}
Toma como primer argumento un elemento y como segundo argumento una
lista (puede ser una lista de listas). Devuelve \textbf{Yes} si el
primer elemento ocurre en la lista.
\begin{verbatim}
ocurre(Elemento, [Elemento]).
ocurre(Elemento, [Elemento|_]).
ocurre(Elemento, [H|_]) :- esLista(H),
        ocurre(Elemento, H).
ocurre(Elemento, [_|T]) :- ocurre(Elemento, T).
\end{verbatim}

\subsection{maplist/3}
maplist(Pred, OldList, NewList)

Devuelve \textbf{Yes} si Pred(Old,New) tiene éxito por cada elemento
en OldList y por cada elemento en NewList. Es el equivalente de la
función <<mapcar>> en Lisp.
\begin{verbatim}
maplist(Pred, [], []) :- !.
maplist(Pred, [Old|Olds], [New|News]) :- !,
        apply(Pred, Old, New),
        %  put a cut here if multiple solutions are not wanted
        maplist(Pred, Olds, News).
\end{verbatim} 

% Página nueva...
\clearpage

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Sección: Trabajo con conjuntos %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Trabajo con conjuntos}

\subsection{union/3}
union/3 realiza la unión de los conjuntos representados por las dos
primeras listas y lo retorna en el tercer argumento.

\begin{verbatim}
union([X|Y],Z,W) :- member(X,Z),
                    union(Y,Z,W).
union([X|Y],Z,[X|W]) :- not(member(X,Z)),
                        union(Y,Z,W).
union([],Z,Z).
\end{verbatim}

\subsection{interseccion/3}
Realiza la intersección de los conjuntos representados por las dos
primeras listas y lo retorna en el tercer argumento.

\begin{verbatim}
interseccion([X|Y],M,[X|Z]) :- member(X,M),
                               interseccion(Y,M,Z).
interseccion([X|Y],M,Z) :- not(member(X,M)),
                           interseccion(Y,M,Z).
interseccion([],M,[]).
\end{verbatim}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Sección: Evaluación de expresiones %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Evaluación de Expresiones}
Este conjunto de predicados permite al usuario evaluar y simplificar
expresiones booleanas.

\begin{verbatim}
pred([X|R]) :- not(atomo(X)).

atomo(X) :- atom(X), integer(X).

:- op(720,fy,no).
:- op(730,yfx,and).
:- op(740,yfx,or).

const_logica(true).
const_logica(false).

and_eval(true,true,true).
and_eval(true,false,false).
and_eval(false,true,false).
and_eval(false,false,false).

or_eval(true,true,true).
or_eval(true,false,true).
or_eval(false,true,true).
or_eval(false,false,false).

no_eval(true,false).
no_eval(false,true).

eval_exp(X,X) :- const_logica(X).
eval_exp(X and Y,Resp) :- eval_exp(X,RX),
        eval_exp(Y,RY),
        and_eval(RX,RY,Resp).
eval_exp(X or Y,Resp) :- eval_exp(X,RX),
        eval_exp(Y,RY),
        or_eval(RX,RY,Resp).
eval_exp(no X, Resp) :- eval_exp(X,RX),
        no_eval(RX,Resp).

simplificar(no(X or Y),NoX and NoY) :-
        simplificar(X,NoX),
        simplificar(Y,NoY).
simplificar(no(X and Y),NoX or NoY) :-
        simplificar(X,NoX),
        simplificar(Y,NoY).
simplificar(no(no(X)),NoNoX) :-
        simplificar(X,NoNoX).
simplificar(no(X),no(X)) :- atom(X).
simplificar(X and Y,RX and RY) :-
        simplificar(X,RX),
        simplificar(Y,RY).
simplificar(X or Y,RX or RY) :-
        simplificar(X,RX),
        simplificar(Y,RY).
simplificar(X,X) :- atom(X).

eval(X,Y) :- simplificar(X,Z),
        eval_exp(Z,Y).
\end{verbatim}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Sección: Procesamiento de árboles %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Procesamiento de árboles}

\subsection{sumahoja/2}
sumahoja/2 toma dos parámetros, el primero es un árbol de estructura:

arbol(Raiz, AI, AD)

Este predicado suma los valores de las hojas del árbol y las devuelve
como el segundo parámetro. (un nodo hoja es aquel que tiene AD y AI
como nil).
\begin{verbatim}
raiz(arbol(R, _, _), R).
ai(arbol(_, AI, _), AI).
ad(arbol(_, _, AD), AD).

sumahoja(Arbol, N) :- raiz(Arbol, N),
        ai(Arbol, nil),
        ad(Arbol, nil).
sumahoja(Arbol, N) :- ai(Arbol,nil),
        ad(Arbol, AD),
        sumahoja(AD, N).
sumahoja(Arbol, N) :- ad(Arbol,nil),
        ai(Arbol, AI),
        sumahoja(AI, N).
sumahoja(Arbol, N) :- ai(Arbol, AI),
        ad(Arbol, AD),
        sumahoja(AI, N1),
        sumahoja(AD, N2),
        N is N1 + N2.
\end{verbatim}

\subsection{prof/2}
Cuenta la profundidad de un árbol.

\begin{verbatim}
prof(nil,-1).
prof([R,I,D],N) :- prof(I,N1),
        prof(D,N2),
        N1 >= N2,
        N is N1 + 1.
prof([R,I,D],N) :- prof(I,N1),
        prof(D,N2),
        N1 < N2,
        N is N2 + 1.
\end{verbatim}

\subsection{preorden/2}
Preorden recorre primero raíz, luego izquierda y por último derecha.

\begin{verbatim}
preorden(nil,[]).
preorden([R,I,D],Z) :- preorden(I,L),
        preorden(D,W),
        concatenar([R|L],W,Z).
\end{verbatim}

\subsection{inorden/2}
Inorden recorre primero izquierda, luego raíz y por último derecha.

\begin{verbatim}
inorden(nil,[]).
inorden([R,I,D],Z) :- inorden(I,L),
        inorden(D,K),
        concatenar(L,[R|K],Z).
\end{verbatim}

\subsection{posorden/2}
Posorden recorre primero izquierda, luego derecha y por último raíz.

\begin{verbatim}
posorden(nil,[]).
posorden([R,I,D],Z) :- posorden(I,L),
        posorden(D,K),
        concatenar(L,K,P),
        concatenar(P,[R],Z).
\end{verbatim}

\subsection{esCompleto/1}
Retorna \textbf{Yes} si el árbol es completo

\begin{verbatim}
esCompleto([]).
esCompleto([R,I,D]) :- posorden(I,K),
        posorden(D,M),
        longitud(K,KL),
        longitud(M,ML),
        KL = ML.
\end{verbatim}

\subsection{pertenece/2}
Retorna \textbf{Yes} si el elemento pasado en segundo parámetro
pertenece al árbol del primer parámetro.

\begin{verbatim}
pertenece([R,I,D],R) :- !.
pertenece([R,I,D],Z) :- I \== nil,
        pertenece(I,Z).
pertenece([R,I,D],Z) :- D \== nil,
        pertenece(D,Z).
\end{verbatim}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Sección: Trabajo con grafos %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Trabajo con grafos}

\subsection{esConexo/1}
Verifica que un grafo no dirigido sea conexo.

\begin{verbatim}
% Ejemplo:
% esConexo([arco(a,b),arco(a,d),arco(b,d),arco(e,f)]).

% Elimina todas las aserciones sobre arcos
sacarCaminos :- retract(arco(_, _)),
        sacarCaminos.
sacarCaminos.

% Arma las aserciones sobre los arcos del grafo
% pasado como parámetro
ponerCaminos([]).
ponerCaminos([H|T]) :- asserta(H),
        ponerCaminos(T).

% Chequea la conexión entre dos nodos
hayCamino(X, Y) :- arco(X, Y).
hayCamino(X, Y) :- arco(Y, X).
hayCamino(X, Y) :- arco(X, Z),
        hayCamino(Z, Y).

% Transforma el grafo en una lista de nodos
% (duplicados, no importa)
enlistar([], []).
enlistar([arco(X,Y)|T], [X|[Y|P]]) :- enlistar(T, P).

% Chequea que el primer nodo de la lista pasada como
% parámetro tenga conección con los nodos del resto
% de la lista
chequearCaminos([]).
chequearCaminos([_|[]]).
chequearCaminos([H|[T|P]]) :- hayCamino(H, T),
        chequearCaminos([H|P]).

% Predicado principal, elimina las aserciones de arcos, agrega
% las del grafo pasado como parámetro y confirma la conexión
% de todos los nodos.
esConexo([]) :- !.
esConexo([_|[]]) :- !.
esConexo(G) :- sacarCaminos,
        ponerCaminos(G),
        enlistar(G, L), !,
        chequearCaminos(L).
\end{verbatim}

\end{document}