162 lines
9.5 KiB
TeX
Executable File
162 lines
9.5 KiB
TeX
Executable File
\documentclass[10pt,a4paper]{article}
|
|
\usepackage[utf8]{inputenc}
|
|
\usepackage[spanish]{babel}
|
|
\usepackage{amsmath}
|
|
\usepackage{amsfonts}
|
|
\usepackage{amssymb}
|
|
\usepackage{hyperref}
|
|
\usepackage{graphicx}
|
|
\usepackage{listings}
|
|
\usepackage{xcolor}
|
|
\usepackage{caption}
|
|
\usepackage{multicol}
|
|
\usepackage{pgf}
|
|
\usepackage{tikz}
|
|
\usetikzlibrary{automata,positioning,arrows}
|
|
|
|
\definecolor{codegreen}{rgb}{0,0.6,0}
|
|
\definecolor{codegray}{rgb}{0.5,0.5,0.5}
|
|
\definecolor{codepurple}{rgb}{0.58,0,0.82}
|
|
\definecolor{backcolour}{rgb}{0.95,0.95,0.92}
|
|
\definecolor{darkblue}{rgb}{0,0,.75}
|
|
|
|
\lstdefinestyle{mystyle}{
|
|
backgroundcolor=\color{backcolour},
|
|
commentstyle=\color{codegreen},
|
|
keywordstyle=\color{magenta},
|
|
numberstyle=\tiny\color{codegray},
|
|
stringstyle=\color{codepurple},
|
|
basicstyle=\ttfamily\footnotesize,
|
|
breakatwhitespace=false,
|
|
breaklines=true,
|
|
captionpos=b,
|
|
keepspaces=true,
|
|
numbers=left,
|
|
numbersep=5pt,
|
|
showspaces=false,
|
|
showstringspaces=false,
|
|
showtabs=false,
|
|
tabsize=2
|
|
}
|
|
|
|
\lstset{style=mystyle}
|
|
|
|
\lstloadlanguages{Matlab} %use listings with Matlab for Pseudocode
|
|
\lstnewenvironment{PseudoCode}[1][]
|
|
{\lstset{language=Matlab,basicstyle=\scriptsize, keywordstyle=\color{darkblue},numbers=left,xleftmargin=.04\textwidth,#1}}
|
|
{}
|
|
|
|
\renewcommand{\rmdefault}{ptm}
|
|
%\usepackage[all,cmtip]{xy}
|
|
%\usepackage{graphicx}
|
|
\author{Programación funcional para la física computacional}
|
|
\title{Recursión}
|
|
\begin{document}
|
|
\maketitle
|
|
\section*{Funciones bien definidas}
|
|
|
|
Una de las ventajas de la programación funcional es que, al basarse en funciones, se alienta a que la usuaria defina nuevas a conveniencia. Pero estas funciones deben estar bien definidas para evitar problemas al ejecutarse. Para nadie es raro el clásico problema de la división de dos números enteros que regresa una resultado en principio mal pues regresa un número natural a menos que se le indique por algún comando especial.
|
|
|
|
Para evitar tener que manejar distintos comandos extras, en \emph{haskell} podemos decir que tipo de datos acepta y cuales regresa desde la misma definición de la función.
|
|
|
|
Ejemplos de como se pudedn definir nuevas funciones a partir de viejas funciones (ya en la librería de \emph{haskell})
|
|
|
|
\begin{itemize}
|
|
\item Una función que indica si el número dado es par, es decir, toma como valor un entero de precisión variable (Integral) y regresa un \emph{booleano}.
|
|
\lstinputlisting[basicstyle=\ttfamily\scriptsize,firstline=1,lastline=2,language=haskell]{fun.hs}
|
|
\item La función que divide una lista en sus primeros $n$ elementos y los restantes, recibe una lista y regresa una lista de listas
|
|
\lstinputlisting[basicstyle=\ttfamily\scriptsize,firstline=4,lastline=6,language=haskell]{fun.hs}
|
|
\item La función que resta los elementos correspondientes de cada lista
|
|
\lstinputlisting[basicstyle=\ttfamily\scriptsize,firstline=7,lastline=9,language=haskell]{fun.hs}
|
|
\end{itemize}
|
|
|
|
Pero podemos usar algunas cosas dentro del lenguaje para definir funciones más allá, por ejemplo, usando expresiones condicionales (cosa común en la definición de funciones en \emph{python} y que también está en \emph{haskell})
|
|
|
|
\begin{itemize}
|
|
\item Expresiones condicionales para definir la función que regresa el valor absoluto de un entero
|
|
\lstinputlisting[basicstyle=\ttfamily\scriptsize,firstline=10,lastline=12,language=haskell]{fun.hs}
|
|
\item Expresiones condicionales anidadas para que regrese el signo del número dado (como cadena)
|
|
\lstinputlisting[basicstyle=\ttfamily\scriptsize,firstline=13,lastline=16,language=haskell]{fun.hs}
|
|
\end{itemize}
|
|
|
|
Ya hemos trabajado un poco con comprensión de listas, aunque no hemos visto mucho detalle. Lo que sabemos es que podemos usar \emph{guardas} tal como se usan para definir conjuntos en matemáticas. Facilitan y reducen el tamaño de las definiciones, volvemos a definir la función de líneas arriba pero ahora de manera más sencilla:
|
|
|
|
\lstinputlisting[basicstyle=\ttfamily\scriptsize,firstline=17,lastline=21,language=haskell]{fun.hs}
|
|
|
|
La sección pasada vimos reconocimiento de patrones, no era tan sencillo para \emph{haskell}, pero realmente esta la funcionalidad incluida en algunas de sus operaciones. Por ejemplo en las operaciones \emph{booleanas} del tipo \emph{True \&\& False} lo que hace el lenguaje es reconocer los patrones y asociarlos a las operaciones lógicas. Pero hay otros casos de reconocimiento de patrones
|
|
|
|
\begin{itemize}
|
|
\item Patrones en eneadas
|
|
\lstinputlisting[basicstyle=\ttfamily\scriptsize,firstline=22,lastline=24,language=haskell]{fun.hs}
|
|
\item Lista de patrones
|
|
\lstinputlisting[basicstyle=\ttfamily\scriptsize,firstline=25,lastline=28,language=haskell]{fun.hs}
|
|
\item Lista de patrones con el constructor
|
|
\lstinputlisting[basicstyle=\ttfamily\scriptsize,firstline=29,lastline=31,language=haskell]{fun.hs}
|
|
\end{itemize}
|
|
|
|
Como ya saben también podemos hacer uso de las definiciones con cálculo $\lambda$. El clásico ejemplo de definir la suma:
|
|
\lstinputlisting[basicstyle=\ttfamily\scriptsize,firstline=32,lastline=34,language=haskell]{fun.hs}
|
|
Definir funciones sólo por su estructura, sin tener que hacer alguna operación algebraica, en este caso sólo por el orden en que se dan los valores de entrada
|
|
\lstinputlisting[basicstyle=\ttfamily\scriptsize,firstline=35,lastline=37,language=haskell]{fun.hs}
|
|
Incluso se pueden llamar a otras funciones dentro de la definición de la función, como en el siguiente caso:
|
|
\lstinputlisting[basicstyle=\ttfamily\scriptsize,firstline=38,lastline=41,language=haskell]{fun.hs}
|
|
O haciendo el mismo caso desde un nivel aún más básico
|
|
\lstinputlisting[basicstyle=\ttfamily\scriptsize,firstline=42,lastline=44,language=haskell]{fun.hs}
|
|
|
|
Pero además este tipo de definiciones de funciones facilita definir operadores nuevos, por lo regular llamados \emph{secciones}. La estructura en que se definen, de distintas formas, se muestra a continuación:
|
|
|
|
\begin{align*}
|
|
(\#)\ =& \ \setminus x\ ->\ (\setminus y\ ->\ x\ \# y) \\
|
|
(x\ \#)\ =& \setminus y\ ->\ x\ \# y \\
|
|
(\#\ y)\ =& \setminus x\ ->\ x\ \# y
|
|
\end{align*}
|
|
|
|
El primer caso espera dos entradas para operar con el nuevo operador, las dos últimas espera sólo una entrada para operar por la derecha o izquierda, respectivamente (podría ser un operador no conmutativo, así que el orden importa).
|
|
|
|
En ocasiones es complicado definir un nuevo operador, muchos de los símbolos ya están tomados por el sistema. Algunas de las funciones compactas propias de \emph{haskell} definidas a partir de \emph{secciones}:
|
|
|
|
\begin{itemize}
|
|
\item $(+)$ la suma que ya usamos
|
|
\item $(1+)$ la función sucesor (la que suma $1$ al único número dado)
|
|
\item $(1/)$ el inverso de un número
|
|
\item $(*2)$ el doble de un número
|
|
\item $(/2)$ la mitad de un número
|
|
\end{itemize}
|
|
|
|
\section*{Comprensión de listas}
|
|
|
|
Otro tema que ya hemos pasado de rápido es la comprensión de listas, veamos más a detalle. La idea más directa es que estaos definiendo conjuntos de una manera que se asemeja mucho a la notación matemática. Las \emph{guardas}, que se escriben ``$\mid$'' funcionan como un \emph{tal que} al leer la descripción.
|
|
|
|
\begin{itemize}
|
|
\item Podemos tener el caso donde hacemos una lista de parejas, nos da todas las posibles combinaciones de parejas: $[(x,y) \mid x<- [1,2,3],\ y <- [4,5]]$
|
|
\item Si cambiamos el ordenamiento en la definición, obtendremos las mismas parejas, pero con distinto orden: $[(x,y) \mid y <- [4,5],\ x<- [1,2,3]]$
|
|
\end{itemize}
|
|
|
|
Podemos definir una función (que realmente ya existe en \emph{haskell}) para conocer la longitud de una lista, pero a partir de comprensión de listas:
|
|
\lstinputlisting[basicstyle=\ttfamily\scriptsize,firstline=45,lastline=47,language=haskell]{fun.hs}
|
|
|
|
Un ejemplo que ya se saben obtener los números primos entre $1$ y $n$, pero no de forma perezosa. Lo primero es identificar los factores de cada número entre $1$ y $n$
|
|
\lstinputlisting[basicstyle=\ttfamily\scriptsize,firstline=48,lastline=50,language=haskell]{fun.hs}
|
|
|
|
Agregamos para obtener los números primos a partir de la función ya definida para obtener los factores, todo hecho a partir de comprensión de listas. Lo que hace la función \emph{primo} es llamar a la anterior función \emph{factores} que da como resultado una lista y comparar si esa lista tiene como únicos factores al $1$ y al mismo número, respondiendo un \emph{verdadero} o \emph{falso}.
|
|
|
|
Posteriormente la función \emph{primo} es llamada dentro de la comprensión de listas de la función \emph{primos} que nos regresará la lista de números entre $2$ y $n$ siempre y cuando el número cumpla con la condición de la función \emph{primo}.
|
|
|
|
\lstinputlisting[basicstyle=\ttfamily\scriptsize,firstline=51,lastline=56,language=haskell]{fun.hs}
|
|
|
|
Para buscar valores dentro de listas de parejas, podemos definir una función, algo parecida a lo que se hizo para la función \emph{primo}, comparamos las entradas de la lista, si la primera entrada de la pareja es igual al valor dado entonces nos regresa el o los valores con los que forma pareja.
|
|
|
|
\lstinputlisting[basicstyle=\ttfamily\scriptsize,firstline=57,lastline=59,language=haskell]{fun.hs}
|
|
|
|
Una función que hemos utilizado y no nos hemos detenido mucho en ver a detalle es \emph{zip}. Esta función espera recibir dos listas y forma una lista de parejas, asociando los miembros correspondientes de cada lista
|
|
|
|
\begin{equation*}
|
|
zip\ ['a','b','c']\ [1,2,3,4] \rightarrow [('a',1),('b',2),('c',3)]
|
|
\end{equation*}
|
|
|
|
\subsection*{Cifrado del César}
|
|
|
|
|
|
|
|
\end{document}
|