Costos.tex

\nonstopmode

\documentclass[a4paper,10pt]{article}
%\usepackage{fullpage}
\usepackage{listings}
\lstset{language=Haskell}
\usepackage[utf8]{inputenc}
\usepackage[english]{babel}
\usepackage{amsmath}
\usepackage[margin=1in]{geometry}
\usepackage{indentfirst}


\author{
    Marzorati Denise \\
    \texttt{marzorati.denise@gmail.com}
    \and Soncini Nicolás \\
    \texttt{soncininicolas@gmail.com}
}

\date{
    8 de Junio de 2016
}

\title{
    \Huge \textsc{Especificación de costos} \\
    \large \textsc{Estructuras de Datos y Algoritmos II} \\
    \textsc{Trabajo Práctico 2}
}

\begin{document}

\bigskip
\bigskip
\bigskip

\maketitle

\thispagestyle{empty}

\begin{center}
\large \bf Docentes de la materia
\end{center}

\begin{center}
Mauro Jaskelioff

Cecila Manzino

Juan M. Rabasedas

Martin Ceresa
\end{center}

\newpage{}


\part*{Implementación con Listas}


%FILTERS
\section*{\texttt{filterS}}

    La implementación de $filterS$ con listas hace uso del paralelismo para
reducir su profundidad lo más posible en base a las aplicaciones de la función 
que se le pasa.
\lstinputlisting[firstline=88, lastline=88]{SeqList.hs}
\lstinputlisting[firstline=20, lastline=23]{SeqList.hs}

    El \texttt{trabajo} de la función se puede tomar de la siguiente forma:

\begin{equation*}
    W \left(filterS\; f \;xs\right) \in
    O \left( \sum_{i=0}^{\vert xs \vert -1} W \left( f\; xs_i \right) \right)
\end{equation*}

De esta forma, se calcula la aplicación de la función argumento en cada
llamada recursiva de $filterS$ hasta que la lista termine vacía.
En el mejor de los casos, si $W \left( f\; xs_i \right) \in O \left( 1 \right)$,
su sumatoria queda como $\vert xs \vert$, por lo tanto se puede omitir sumar este valor
en la cota superior del trabajo.

\bigskip

La \texttt{profundidad} de la función se puede reducir gracias a la aplicación
en paralelo de la función argumento, por lo tanto se puede deducir que:

\begin{equation*}
    S \left(filterS\; f \; xs \right) \in
    O \left( \vert xs \vert + \max_{i=0}^{\vert xs \vert -1} S \left( f\; xs_i \right) \right)
\end{equation*}

En este caso, como el máximo de todos los trabajos puede quedar constante, debemos
sumar el trabajo de obtener cada elemento, lo cual suma $\vert xs \vert$.


\bigskip

 
%SHOWT
\section*{\texttt{showtS}}


    La implementación de $showtS$ con listas divide la lista en dos mitades
y con las funciones $takeS$ y $dropS$.
\lstinputlisting[firstline=90, lastline=90]{SeqList.hs}
\lstinputlisting[firstline=91, lastline=91]{SeqList.hs}
\lstinputlisting[firstline=92, lastline=92]{SeqList.hs}
\lstinputlisting[firstline=27, lastline=33]{SeqList.hs}
    Sabemos que las funciones utilizadas son lineales:

\begin{equation*}
    W/S \left( takeS\; xs\; n \right) \in 
    O \left( \vert xs \vert \right)
\end{equation*}
\begin{equation*}
    W/S \left( dropS\; xs\; n \right) \in 
    O \left( \vert xs \vert \right)
\end{equation*}
tanto en su trabajo como en su profundidad. 

\smallskip
   
    Luego, podemos concluir fácilmente que valen los siguientes costos ya
que se aplica una vez cada función sobre la mitad de la lista.

\begin{equation*}
    W \left( showtS\; xs \right) \in O \left( \vert xs \vert \right)
\end{equation*}

\begin{equation*}
    S \left( showtS\; xs \right) \in O \left( \vert xs \vert \right)
\end{equation*}


\bigskip
    

%REDUCES
\section*{\texttt{reduceS}}

    La implementación de $reduceS$ toma una función de costo desconocido,
un elemento y una lista del mismo tipo y aplica el algoritmo de reduce
de forma que opera con la función dada $\oplus$ los elementos de la lista
de a pares sobre el resultado de cada llamada recursiva. Este orden de 
reducción (u operación) es el dado por el TAD.

\lstinputlisting[firstline=95, lastline=95]{SeqList.hs}
\lstinputlisting[firstline=45, lastline=47]{SeqList.hs}
\lstinputlisting[firstline=55, lastline=58]{SeqList.hs}

    Ahora, a la hora de calcularlos para $reduceS$, nosotros debemos forzar
el orden de reducción, ya que la implementación de $contraer$ utiliza un orden
que no cumple la especificación necesaria, pero es fácil identificar el rol que
cumple al ser bien integrado a $reduceS$.

    Como primera función auxiliar se encuentra $contraer$, que dada una función y
una lista, opera de a pares sus elementos, tomando las llamadas recursivas y las 
aplicaciones de la función en forma paralela. 

\lstinputlisting[firstline=49, lastline=52]{SeqList.hs}

    Debemos entonces calcular los costos de $contraer$ para poder calcular los de la 
función pedida, ésta queda como el costo de recorrer toda la lista sumado a los costos 
de las operaciones dos a dos. Pero ésta ultima, en el caso que todas las operaciones 
sean constantes, ya queda acotada por la longitud de la lista, luego podemos obviar 
éste parametro al calcular su trabajo:

\begin{equation*}
    W \left( contraer \;\oplus \;xs \right) \in
    O \left( \sum_{i=0}^{(\vert xs / 2 \vert) - 1} W \left( xs_{2i} \oplus xs_{2i+1} \right) \right)
\end{equation*}

    Lo mismo no sucede en su profundidad, ya que se suma el máximo de las profundidades
de las operaciones, con lo cual éstas pueden quedar constantes, pero el trabajo está 
acotado por el trabajo de recorrer la lista (que es lineal sobre su longitud):

\begin{equation*}
    S \left( contraer \;\oplus \;xs \right) \in
    O \left( \vert xs \vert + \max_{i=0}^{(\vert xs / 2 \vert) - 1} S \left( xs_{2i} \oplus xs_{2i+1} \right) \right)
\end{equation*}

\smallskip

    Es claro entonces el costo que aporta adecuar esta función para que trabaje sobre
cada resultado de un llamado recursivo de si mismo, cumpliendo así el orden de
reducción pedido por el TAD de Secuencias para $reduceS$.

    Ahora sí podemos calcular el trabajo de $reduceS$, el cual queda de la siguiente
manera: 

\begin{equation*}
    W \left( reduceS \oplus \; b \; xs \right) \in
    O \left( \vert xs \vert + \sum_{(xs_i \oplus xs_j) \in \mathcal{O}_r(\oplus,b,xs)} W \left( xs_i \oplus xs_j \right) \right)
\end{equation*}

\bigskip

    Tanto su \texttt{trabajo} como su \texttt{profundidad} se ven afectadas por
el reordenamiento de reducción sobre el resultado de $contraer$, con lo cual la paralelización
de ésta no puede ser aprovechada, y obtenemos:

\begin{equation*}
    S \left( reduceS \oplus \; b \; xs \right) \in
    O \left( \vert xs \vert + lg \;\vert xs \vert \max_{(xs_i \oplus xs_j) \in \mathcal{O}_r(\oplus,b,xs)} S \left( xs_i \oplus xs_j \right) \right)
\end{equation*}


\bigskip


%SCANS
\section*{\texttt{scanS}}

    La implementación de \texttt{scanS} hace uso de varias funciones auxiliares
para su correcto funcionamiento y su fácil comprensión.
\lstinputlisting[firstline=96, lastline=96]{SeqList.hs}
\lstinputlisting[firstline=68, lastline=73]{SeqList.hs}

    Para obtener el costo del mismo debemos primero describir y especificar los 
costos de las funciones que lo auxilian.

    Como primera función auxiliar se encuentra $contraer$, que dada una función y
una lista, opera de a pares sus elementos, tomando las llamadas recursivas y las 
aplicaciones de la función en forma paralela. (Se detallan los costos en la
especificación de costos de reduceS).

\smallskip

    Luego hacemos uso de la función $expandir$, que dada una función y dos listas
(la primera siendo la lista argumento de $scanS$, y la segunda el resultado de aplicarle
a la primera la función $contraer$) retorna una única lista que combina ambas:
\lstinputlisting[firstline=62, lastline=65]{SeqList.hs}

\begin{equation*}
    W \left( expandir \;\oplus \;xs \;zs \right) \in
    O \left( \sum_{i=0}^{(\vert xs \vert)/2 - 1} W \left( xs_{\lfloor (2i+1)/2 \rfloor} \oplus zs_{2i} \right) \right)
\end{equation*}

\begin{equation*}
    S \left( expandir \;\oplus \;xs \;zs \right) \in
    O \left( \vert xs \vert + \max_{i=0}^{(\vert xs \vert)/2 - 1} S \left( xs_{\lfloor (2i+1)/2 \rfloor} \oplus zs_{2i} \right) \right)
\end{equation*}

\bigskip

    Podemos concluir de esta forma, dado que la función $scanS$ para listas llama a 
expandir sobre una recursión de aplicar contraer a la lista dada, que su \texttt{trabajo} 
es por lo menos lineal, que se calcula como:

\begin{equation*}
    W \left( scanS \oplus \; b \; xs \right) \in
    O \left( \vert xs \vert + \sum_{(xs_i \oplus xs_j) \in \mathcal{O}_s(\oplus,b,xs)} W \left( xs_i \oplus xs_j \right) \right)
\end{equation*}

    Y dado que las profundidades de $expandir$ y $contraer$ son como mínimo lineales,
la \texttt{profundidad} de $scanS$ queda como la suma del tamaño de la lista y el
máximo de las profundidades de la aplicación de la función sobre las sub-aplicaciones
en el orden de reducción dado. Con lo cual tenemos:

\begin{equation*}
    S \left( scanS \oplus \; b \; xs \right) \in
    O \left( \vert xs \vert +  lg \;\vert xs \vert \max_{(xs_i \oplus xs_j) \in \mathcal{O}_s(\oplus,b,xs)} S \left( xs_i \oplus xs_j \right) \right)
\end{equation*}





\bigskip
\newpage{}





\part*{Implementación con Arreglos Persistentes}

%FILTERS
\section*{\texttt{filterS}}

    La función $filterS$ toma una lista y una función sobre elementos de la misma
y hace uso de $tabulateS$ para aplicar la función sobre cada elemento y $joinS$ para
unir los resultados sueltos de la aplicación anterior.\\
\lstinputlisting[firstline=66, lastline=66]{SeqArray.hs}
\lstinputlisting[firstline=24, lastline=24]{SeqArray.hs}
\begin{scriptsize}\lstinputlisting[firstline=25, lastline=26]{SeqArray.hs}\end{scriptsize}

    Sabemos que los costos de $tabulateS$ y $joinS$ para arreglos persistentes son:

\begin{equation*}
    W \left(tabulateS \;f \;n \right) \in
    O \left( \sum_{i=0}^{n-1} W \left( f\; i \right) \right)
\end{equation*}

\bigskip

\begin{equation*}
    S \left( tabulateS \;f \;n \right) \in
    O \left( \max_{i=0}^{n-1} S \left( f\; i \right) \right)
\end{equation*}

\smallskip
\begin{center}
y
\end{center}

\begin{equation*}
    W \left(joinS \;as\right) \in
    O \left( \vert as \vert + \sum_{i=0}^{\vert as \vert -1} \left( \vert as_i \vert \right) \right)
\end{equation*}

\begin{equation*}
    S \left(joinS\; \; as \right) \in
    O \left( \;lg \; \vert as \vert \; \right)
\end{equation*}


\bigskip
\bigskip

    De ambas se puede calcular que el \texttt{trabajo} de $filterS$ queda la
suma de la longitud del arreglo y la sumatoria del costo de trabajo de las
aplicaciones de la función a cada elemento. En el mejor de los casos, la función
utilizada es de costo constante, con lo cual ya tendríamos el costo lineal sobre
la longitud del arreglo en ese caso. De esto se puede omitir el tamaño del arreglo,
con lo que nos quedaría:
 
\begin{equation*}
    W \left(filterS \;f \;as \right) \in
    O \left( \sum_{i=0}^{\vert as \vert -1} W \left( f\; as_i \right) \right)
\end{equation*}

\bigskip

    Ahora, al momento de calcular su \texttt{profundidad} es una simple suma
de las profundidades de $joinS$ y $tabulateS$, y no puede omitirse ninguna ya
que cualquiera de ellas puede tomar un valor mayor a la otra, dependiendo del
costo de las funciones que utiliza tabulate. Luego podemos observar que:

\begin{equation*}
    S \left( filterS \;f \;as \right) \in
    O \left( \;lg \; \vert as \vert + \max_{i=0}^{\vert as \vert -1} S \left( f\; as_i \right) \right)
\end{equation*}


\bigskip


%SHOWT
\section*{\texttt{showtS}}

%"PARA ESTE FORMATO"?!?!?! HABIENDO TANTAS PALABRAS NO SE ME OCURRE NADA MEJOR?!?!?!?
    Para la implementación de $showtS$ para este formato debemos partir al arreglo
en dos partes de forma que nos de una rapida idea de la forma en árbol del mismo.
Para llevar a cabo esto hacemos uso de las funciones ya definidas para arreglos 
persistentes $takeS$ y $dropS$, que devuelven un arreglo con los primeros o últimos
elementos del arreglo según una cantidad arbitraria respectivamente.
\lstinputlisting[firstline=68, lastline=68]{SeqArray.hs}
\lstinputlisting[firstline=69, lastline=69]{SeqArray.hs}
\lstinputlisting[firstline=8, lastline=13]{SeqArray.hs}

    Para considerar los costos de $showtS$ sabemos como primera instancia que los
costos de las funciones auxiliares son constantes:

\begin{equation*}
    W/S \left( takeS\; as\; n \right) \in 
    O \left( 1 \right)
\end{equation*}

\begin{equation*}
    W/S \left( dropS\; as\; n \right) \in 
    O \left( 1 \right)
\end{equation*}

\bigskip
   
    Y como tomar su longitud también lo es (útil para el cálculo de 
$2^{ilog(\vert as \vert -1)}$), tenemos entonces que los costos para la función
$showtS$ también quedan constantes:

\begin{equation*}
    W \left( showtS\; as \right) \in O \left( 1 \right)
\end{equation*}

\begin{equation*}
    S \left( showtS\; as \right) \in O \left( 1 \right)
\end{equation*}


\bigskip
    

%REDUCES
\section*{\texttt{reduceS}}

    Para calcular los costos de la función $reduceS$ tenemos que hacerlo en función
a los costos que posee $contraer$, ya que es la única función auxiliar que llama en
su recursión y la única operación (de costo significante) que realiza.
\lstinputlisting[firstline=73, lastline=73]{SeqArray.hs}
\lstinputlisting[firstline=31, lastline=39]{SeqArray.hs}
\begin{scriptsize}\lstinputlisting[firstline=42, lastline=47]{SeqArray.hs}\end{scriptsize}

    El costo de la función $contraer$ se calcula, para su \texttt{trabajo} como
la suma de las aplicaciones de la función binaria, ya que viene dada por un $tabulateS$
cuyo costo es éste mismo, y por la misma razon la \texttt{profundidad} es su
máximo:

\begin{equation*}
    W \left( contraer \;\oplus \;as \right) \in
    O \left( \sum_{i=0}^{(\vert as / 2 \vert) - 1} W \left( as_{2i} \oplus as_{2i+1} \right) \right)
\end{equation*}

\begin{equation*}
    S \left( contraer \;\oplus \;as \right) \in
    O \left( \max_{i=0}^{(\vert as / 2 \vert) - 1} S \left( as_{2i} \oplus as_{2i+1} \right) \right)
\end{equation*}

\bigskip

    Como la función $reduceS$ se llama recursivamente sobre el resultado de $contraer$,
la cual devuelve un arreglo con la mitad de elementos, podemos ver que ésta debe
entonces recorrer el arreglo en cada paso recursivo, dejándo asi un costo lineal sobre
la longitud del mismo en su costo de \texttt{trabajo}, sumado obviamente a los costos
de trabajo de cada aplicación de la función binaria:

\begin{equation*}
    W \left( reduceS \oplus \; b \; as \right) \in
    O \left( \vert as \vert + \sum_{(as_i \oplus as_j) \in \mathcal{O}_r(\oplus,b,as)} W \left( as_i \oplus as_j \right) \right)
\end{equation*}

\bigskip
    A la hora de calcular su \texttt{profundidad}, sabemos que llama a la función
contraer $lg \;\vert as \vert$ veces, a esto sumamos la máxima profundidad de las 
aplicaciones del argumento primero sobre el orden de reducción dado por sus 
llamadas recursivas. Con lo cual nos queda:

\begin{equation*}
    S \left( reduceS \oplus \; b \; as \right) \in
    O \left( lg \; \vert as \vert * \max_{(as_i \oplus as_j) \in \mathcal{O}_r(\oplus,b,xs)} S \left( as_i \oplus as_j \right) \right)
\end{equation*}


\bigskip


%SCANS
\section*{\texttt{scanS}}

    Por último debemos calcular las cotas superiores de $scanS$, para
esto tenemos que entender el procedimiento que realiza. La función $scanS$ en
cada paso recursivo hace una expansión de llamarse a ella misma 
sobre el resultado de realizar una contracción (esto nos asegura que se 
realizarán igual cantidad de expansiones y contracciones).
\lstinputlisting[firstline=74, lastline=74]{SeqArray.hs}
\lstinputlisting[firstline=52, lastline=56]{SeqArray.hs}
\bigskip

    Durante la contracción se toma al arreglo de valores y se lo opera
dos a dos, dejando así un arreglo de la mitad de la longitud. El costo
de esta función se expresa en un punto anterior.

\bigskip

    En la expansión se toma un arreglo y una tupla (que las llamadas recursivas 
dentro de $scanS$ dejan llena con un arreglo en la primera posición y la 
operación de todos los elementos en la segunda) y los opera y reordena según un
algoritmo ya visto.  De esta forma deja un resultado intermedio útil para otra
llamada de expandir, o el resultado final de $scanS$ en la última llamada. 
\begin{scriptsize}\lstinputlisting[firstline=48, lastline=50]{SeqArray.hs}\end{scriptsize}

Como $expandir$ utiliza un tabulate con funciones constantes en su argumento, podemos
deifnir sus costos como:

\begin{equation*}
    W \left( expandir \;\oplus \;as \;bs \right) \in
    O \left( \sum_{i=0}^{(\vert as \vert)/2 - 1} W \left( as_{\lfloor (2i+1)/2 \rfloor} \oplus bs_{2i} \right) \right)
\end{equation*}

\begin{equation*}
    S \left( expandir \;\oplus \;as \;bs \right) \in
    O \left( \max_{i=0}^{(\vert bs \vert)/2 - 1} S \left( as_{\lfloor (2i+1)/2 \rfloor} \oplus bs_{2i} \right) \right)
\end{equation*}

\bigskip

    Tenemos entonces, dado que cada llamada de $scanS$ sobre un arreglo de una
longitud dada realiza dos llamadas de funciones (una de $contraer$ y otra de
$expandir$) con costos idénticos, y una llamada recursiva sobre un arreglo de
la mitad de la longitud, que su costo de \texttt{trabajo} es:

\begin{equation*}
    W \left( scanS \oplus \; b \; as \right) \in
    O \left( \vert as \vert + \sum_{(as_i \oplus as_j) \in \mathcal{O}_r(\oplus,b,as)} W \left( as_i \oplus as_j \right) \right)
\end{equation*}

    Con el mismo criterio, se llama a ambas funciones en forma del árbol de reduccion,
con lo cual obtenemos una profundidad del máximo de todas las aplicaciones de éste árbol 
(que realizan en conjunto $contraer$ y $expandir$) multiplicado por la profundidad del
mismo (logarítmica): 

\begin{equation*}
    S \left( scanS \oplus \; b \; as \right) \in
    O \left( lg \;\vert as \vert\; \max_{(as_i \oplus as_j) \in \mathcal{O}_r(\oplus,b,as)} S \left( as_i \oplus as_j \right) \right)
\end{equation*}




% \; is a thick space
% \vert is |
% \left( is big left parenthesis
% \right) is big right parenthesis
% \sum is summatory.
% \max is max (math mode)
% \mathbf is bold formatting

%\begin{equation*}
%    W \left( filterS\; f \; s \right) \in
%    O \left( \sum_{i=0}^{\vert s \vert -1} W \left( f \; s_i \right) \right)
%\end{equation*}
%
%\begin{equation*}
%    S \left( filterS\; f \; s \right) \in
%    O \left( \vert s \vert + \max_{i=0}^{\vert s \vert -1} S \left( f \; s_i \right) \right)
%\end{equation*}
%
%
%\section*{\texttt{showtS}}
%
%\texttt{showtS} precisa partir la secuencia dada en dos mitades, de modo que
%utiliza las funciones \texttt{takeS} y \texttt{dropS} (que en el caso de la
%implementación con listas son las mismas funciones que hay en \texttt{Prelude})
%que tienen orden lineal. Esto resulta en costo lineal para trabajo y profundidad:
%
%\begin{equation*}
%    W \left( showtS \; s \right) \in
%    O \left( \vert s \vert \right)
%\end{equation*}
%
%\begin{equation*}
%    S \left( showtS \; s \right) \in
%    O \left( \vert s \vert \right)
%\end{equation*}
%
%
%\section*{\texttt{reduceS}}
%
%Para la implementación de \texttt{reduceS} con listas se usa la función \texttt{contract}
%que toma una operación binaria $\oplus$ y una secuencia $s$ y la contrae aplicando
%la operación binaria a cada par de elementos contiguos. Para esto se calcula la
%operación entre dichos elementos en paralelo al cálculo del paso recursivo de
%\texttt{contract}, resultando en la suma de los trabajos de $\oplus$ aplicado a
%cada par de elementos contiguos de la secuencia para el trabajo y la longitud de
%la secuencia más la máxima de las profundidades de $\oplus$ aplicado a cada par de
%elementos contiguos de la secuencia para la profundidad:
%
%\begin{equation*}
%    W \left( contract \oplus s \right) \in
%    O \left( \vert s \vert + \sum_{i=0}^{\frac{\vert s \vert}{2} + 1} W \left( s_{2i} \oplus s_{2i+1} \right) \right)
%\end{equation*}
%
%\begin{equation*}
%    S \left( contract \oplus s \right) \in
%    O \left( \vert s \vert + \max_{i=0}^{\frac{\vert s \vert}{2} + 1} S \left( s_{2i} \oplus s_{2i+1} \right) \right)
%\end{equation*}
%
%Luego, \texttt{reduceS} aplicado a una operación binaria $\oplus$, un elemento $b$,
%y una secuencia $s$, se calcula aplicando recursivamente \texttt{reduceS} a la
%misma operación $\oplus$, el mismo elemento $b$ y la secuencia obtenida de aplicar
%\texttt{contract} a $s$, generando el orden de reducción buscado. Esto es lo mismo
%para el trabajo y la profundidad, de modo que el costo de recorrer todo el árbol
%de reducción es proporcional al tamaño de la secuencia (lineal) pues estamos
%trabajando con listas. Luego, para el trabajo queda la suma de los trabajos de
%cada aplicación de $\oplus$ en el árbol de reducción más el tamaño de la secuencia y
%para la profundidad resulta la suma de las profundidades de cada aplicación de
%$\oplus$ en el árbol de reducción más el tamaño de la secuencia, ya que por cómo hay
%que forzar el orden de reducción no se puede aprovechar la profundidad de \texttt{contract}.
%
%\newpage
%
%\begin{equation*}
%    W \left( reduceS \oplus \; b \; s \right) \in
%    O \left( \vert s \vert + \sum_{(x \oplus y) \in \mathcal{O}_r(\oplus,b,s)} W \left( x \oplus y \right) \right)
%\end{equation*}
%
%\begin{equation*}
%    S \left( reduceS \oplus \; b \; s \right) \in
%    O \left( \vert s \vert + \sum_{(x \oplus y) \in \mathcal{O}_r(\oplus,b,s)} S \left( x \oplus y \right) \right)
%\end{equation*}
%
%\section*{\texttt{scanS}}
%
%\texttt{scanS}, además de utilizar \texttt{contract}, emplea la función \texttt{combine},
%que toma una operación binaria $\oplus$, 2 secuencias, $s$ y $s'$, y una bandera
%que indica si el índice actual de la secuencia resultante es par (para construir
%el orden de reducción buscado). Cuando el índice es par (bandera en $True$),
%devuelve $s'_{\frac{i}{2}}$, mientras que cuando el índice es impar devuelve
%$s'_{\lfloor \frac{i}{2} \rfloor} \oplus s_{i-1}$ y en este caso ésta operación
%se efectúa en paralelo al paso recursivo, de modo que se mejora un poco la
%profundidad, quedando:
%
%\begin{equation*}
%    W \left( combine \oplus s \; s' \right) \in
%    O \left( \vert s \vert + \sum_{i=1}^{\frac{\vert s \vert}{2}} W \left( s'_{i} \oplus s_{2i - 1} \right) \right)
%\end{equation*}
%
%\begin{equation*}
%    S \left( combine \oplus s \; s' \right) \in
%    O \left( \vert s \vert + \max_{i=1}^{\frac{\vert s \vert}{2}} S \left( s'_{i} \oplus s_{2i - 1} \right) \right)
%\end{equation*}
%
%Luego, \texttt{scanS} simplemente aplica \texttt{combine} con la operación binaria
%$\oplus$, la secuencia original, y la secuencia obtenida de aplicar \texttt{scanS}
%a la contracción de la secuencia original con la operación anterior. Dado que
%\texttt{contract} tiene trabajo por lo menos lineal y \texttt{combine} también,
%el trabajo de scan resulta lineal en la longitud de la secuencia más el trabajo
%de todas las aplicaciones de la operación binaria en el árbol de reducción. En
%cuanto a la profundidad, \texttt{contract} y \texttt{combine} también se comportan
%linealmente por lo menos, de modo que no se puede aprovechar lo poco que se ganó
%en profundidad, así que resulta la longitud de la secuencia más la suma de todas
%las profundidades de las aplicaciones de la operación binaria en el árbol de
%reducción de \texttt{scanS}:
%
%\begin{equation*}
%    W \left( scanS \oplus b \; s \right) \in
%    O \left( \vert s \vert + \sum_{(x \oplus y) \in \mathcal{O}_s(\oplus,b,s)} W \left( x \oplus y \right) \right)
%\end{equation*}
%
%\begin{equation*}
%    S \left( scanS \oplus b \; s \right) \in
%    O \left( \vert s \vert + \sum_{(x \oplus y) \in \mathcal{O}_s(\oplus,b,s)} S \left( x \oplus y \right) \right)
%\end{equation*}
%
%\newpage{}
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%\part*{Implementación con arreglos persistentes}
%
%\section*{\texttt{filterS}}
%
%Para la implementación con arreglos persistentes de \texttt{filterS} primero se
%transforma la secuencia dada en una secuencia donde cada elemento es un singleton
%cuando el elemento cumple con el predicado, o una secuencia vacía cuando no cumple
%con el predicado. Esto se logra usando \texttt{tabulate} con una función que tiene
%costo igual al del predicado, para luego aplicar flatten a la lista resultante,
%de tamaño $\vert s \vert$, donde cada elemento es una secuencia de longitud 1 o 0.
%Luego, \texttt{filterS} resulta con trabajo igual a la suma de los trabajos de
%cada aplicación del predicado a los elementos de la secuencia, y profundidad igual
%al logaritmo de la longitud de la secuencia más el máximo costo de las profundidades
%de todas las aplicaciones del predicado a los elementos de la secuencia:
%
%\begin{equation*}
%    W \left( filterS \; f \; s \right) \in
%    O \left( \sum_{i=0}^{\vert s \vert -1} W(f \; s_i) \right)
%\end{equation*}
%
%\begin{equation*}
%    S \left( filterS \; f \; s \right) \in
%    O \left( \text{lg} \; \vert s \vert + \max_{i=0}^{\vert s \vert -1} S(f \; s_i) \right)
%\end{equation*}
%
%
%\section*{\texttt{showtS}}
%
%La implementación de \texttt{showtS} con arreglos persistentes usa las funciones
%\texttt{takeS} y \texttt{dropS} (ambas con trabajo y profundidad $O \left( 1 \right)$,
%ya que usan \texttt{subArray}), de modo que el trabajo y la profundidad resulta
%constante:
%
%\begin{equation*}
%    W \left( showtS \; s \right) \in
%    O \left( 1 \right)
%\end{equation*}
%
%\begin{equation*}
%    S \left( showtS \; s \right) \in
%    O \left( 1 \right)
%\end{equation*}
%
%
%\section*{\texttt{reduceS}}
%
%Para la implementación de \texttt{reduceS} con arreglos persistentes definimos
%una función \texttt{contract} que contrae la secuencia dada con una operación
%binaria utilizando la función \texttt{tabulate} provista, que a su vez utiliza
%una función con el mismo costo que la operación binaria. En el caso del trabajo,
%\texttt{contract} tiene costo igual a la suma de los trabajos de las aplicaciones
%de la operación binaria a cada par de elementos consecutivos. Por otro lado,
%la profundidad simplemente tiene costo igual a la máxima profundidad de las
%aplicaciones de la operación binaria a cada par de elementos consecutivos:
%
%\begin{equation*}
%    W \left( contract \oplus s \right) \in
%    O \left( \sum_{i=0}^{\frac{\vert s \vert}{2} + 1} W \left( s_{2i} \oplus s_{2i+1} \right) \right)
%\end{equation*}
%
%\begin{equation*}
%    S \left( contract \oplus s \right) \in
%    O \left( \max_{i=0}^{\frac{\vert s \vert}{2} + 1} S \left( s_{2i} \oplus s_{2i+1} \right) \right)
%\end{equation*}
%
%Luego, \texttt{reduceS} utiliza \texttt{contract} en cada llamado recursivo,
%transformando la secuencia dada en otra con la mitad de longitud original, hasta
%llegar a un singleton. En el caso del trabajo, esto resulta en recorrer la secuencia
%en cada paso recursivo (que esto resulta lineal, basta ver que es una recurrencia
%dada por $T \left( n \right) = T \left( \frac{n}{2} \right) + n$ donde $n$ es el
%tamaño de la secuencia) más la suma de todos los trabajos de la aplicación de la
%operación binaria en el árbol de reducción. Por otro lado, la profundidad resulta
%en lg $\vert s \vert$ (debido a que cada aplicación de \texttt{contract} resulta
%en una secuencia con tamaño igual a la mitad de la original) multiplicado por la
%máxima profundidad de todas las aplicaciones de la operación binaria en el árbol
%de reducción (que esto basta para especificar una cota superior, si quisiéramos
%acotarlo más obtendríamos la suma de las profundidades de todas las aplicaciones
%de la operación binaria en cada nivel del árbol de reducción, lo que resulta
%bastante engorroso de escribir, por eso se elije la profundidad dada que aún así
%es buena cota).
%
%\begin{equation*}
%    W \left( reduceS \oplus b \; s \right) \in
%    O \left( \vert s \vert + \sum_{(x \oplus y) \in \mathcal{O}_r(\oplus,b,s)} W \left( x \oplus y \right) \right)
%\end{equation*}
%
%\begin{equation*}
%    S \left( reduceS \oplus b \; s \right) \in
%    O \left( \text{lg} \; \vert s \vert \; \max_{(x \oplus y) \in \mathcal{O}_r(\oplus,b,s)} S \left( x \oplus y \right) \right)
%\end{equation*}
%
%\section*{\texttt{scanS}}
%
%La implementación con arreglos persistentes de \texttt{scanS}, además de utilizar
%\texttt{reduceS}, emplea la función \texttt{combine} que es la que se encarga de
%construír el orden de reducción buscado.
%\texttt{combine} toma una operación binaria, $\oplus$ y 2 secuencias, $s$ y $s'$,
%donde $s'$ se espera que sea el resultado de aplicar \texttt{scanS} con $\oplus$,
%un elemento, y la contracción de $s$ con la operación binaria anterior. Ésta función
%utiliza \texttt{tabulate} con la operación $\oplus$ y una función auxiliar que
%para los índices pares devuelve $s'_{\frac{i}{2}}$ y para los índices impares
%devuelve $s'_{\lfloor \frac{i}{2} \rfloor} \oplus s_{i-1}$, que claramente
%aporta al trabajo y a la profundidad sólo en éste último caso, de modo la especificación
%de costo para \texttt{combine} queda así: 
%
%%La implementación con arreglos persistentes de \texttt{scanS} también utiliza
%%la función \texttt{contract} definida por nosotros (cuyo costo está especificado
%%en el análisis de \texttt{reduceS}) y una nueva función \texttt{combine} que lo
%%que hace es fusionar una secuencia $s$ y otra secuencia $s'$ mediante la operación
%%binaria provista, sabiendo que $s'$ es el resultado de \texttt{scanS} aplicado a
%%$contract s$
%%\texttt{combine} utiliza \texttt{tabulate} con una función que tiene costo $O \left( 1 \right)$
%%cuando el índice es par y $O \left( s'_{i} \oplus s_{2i-1} \right)$ cuando el índice 
%%es impar, de manera que el trabajo y profundidad dependen de éste último caso,
%%quedando:
%
%\begin{equation*}
%    W \left( combine \oplus s \; s' \right) \in
%    O \left( \vert s \vert + \sum_{i=1}^{\frac{\vert s \vert}{2}} W \left( s'_{i} \oplus s_{2i-1} \right) \right)
%\end{equation*}
%
%\begin{equation*}
%    S \left( combine \oplus s \; s' \right) \in
%    O \left( \max_{i=1}^{\frac{\vert s \vert}{2}} S \left( s'_{i} \oplus s_{2i-1} \right) \right)
%\end{equation*}
%
%Por último, \texttt{scanS} simplemente aplica \texttt{combine} a la secuencia original
%y a la obtenida al aplicar \texttt{scanS} con la misma operación, el mismo elemento,
%y la secuencia original contraída. De esta forma, en el caso del trabajo tiene
%que recorrer toda la secuencia para poder calcular la contracción, además de la
%suma de todos los trabajos aportados por las aplicaciones de la operación binaria
%en la reducción de \texttt{scanS}. Por otro lado, en el caso de la profundidad
%sucede algo similar a lo que pasó con \texttt{reduceS} (ver apartado anterior) de
%modo que resulta lg $\vert s \vert$ multiplicado por la máxima profundidad de
%todas las aplicaciones de la operación binaria en la reducción de \texttt{scanS},
%quedando:
%
%\begin{equation*}
%    W \left( scanS \oplus b \; s \right) \in
%    O \left( \vert s \vert + \sum_{(x \oplus y) \in \mathcal{O}_s(\oplus,b,s)} W \left( x \oplus y \right) \right)
%\end{equation*}
%
%\begin{equation*}
%    S \left( scanS \oplus b \; s \right) \in
%    O \left( \text{lg} \; \vert s \vert \; \max_{(x \oplus y) \in \mathcal{O}_s(\oplus,b,s)} S \left( x \oplus y \right) \right)
%\end{equation*}
%
\end{document}