Programación Funcional Avanzada - LDC

Programación Funcional Avanzada
Mejoramiento de desempeño
Ernesto Hernández-Novich
<[email protected]>
Universidad “Simón Bolívar”
Copyright ©2010-2015
Hernández-Novich (USB)
Programación Funcional Avanzada
2015
1 / 43
Mejora del desempeño
Técnica funcional
Mejoramiento del Desempeño
Quiero que mi programa corra más rápido. . .
• Dejar que GHC lo optimize – funciona para la “mente funcional”.
• Aprovechar librerías del sistema – optimizadas para su comfort.
• Si no es suficiente, aplicar las técnicas de profiling para determinar
cuál es la causa del problema.
• Mejoras dramáticas vienen de cambios dramáticos –
usualmente de algoritmos y en los lugares adecuados.
• Lugares que no puedes identificar si no haces profiling.
La optimización prematura es la raíz de todos los males
– Donald Knuth
Hernández-Novich (USB)
Programación Funcional Avanzada
2015
2 / 43
Mejora del desempeño
Buena flojera
La flojera es tu amiga
Procrastinando para ser productivo y eficiente
• Haskell es un lenguaje perezoso – evaluación normal.
• Nada se evalúa a menos que sea absolutamente necesario.
• Aplica a funciones.
• Aplica a constructores de datos – que son funciones.
• Aplica a definiciones locales.
• Evaluación perezosa favorece la programación modular.
• Memorización implícita – espacio en lugar de cómputo.
• Permite separar productores de consumidores.
• Permite especificar productores sobre un conjunto infinito.
Hernández-Novich (USB)
Programación Funcional Avanzada
2015
3 / 43
Mejora del desempeño
Buena flojera
Mergesort
Mejor manera de ordenar en un lenguaje funcional
msort [] = []
msort [ x ] = [ x ]
msort xs = merge ( msort miti ) ( msort mita )
where
( miti , mita ) = halve xs
merge xs [] = xs
merge [] ys = ys
merge xs@ ( x : t ) ys@ ( y : u )
| x <= y
= x : merge t ys
| otherwise = y : merge xs u
• merge – combina dos listas ordenadas, preservando el orden.
• halve – divide la lista en dos mitades.
¿Cómo escribirmos halve?
Hernández-Novich (USB)
Programación Funcional Avanzada
2015
4 / 43
Mejora del desempeño
Buena flojera
Dividir una lista en dos
Primera versión – recursión de cola
halve = go ([] ,[])
where
go ( eac , oac ) []
= ( eac , oac )
go ( eac , oac ) [ x ]
= ( x : eac , oac )
go ( eac , oac ) ( x : y : xs ) = go ( x : eac , y : oac ) xs
• ¿Cómo que usar length, dividir entre dos. . . ? – facepalm!
• Es recursiva de cola – eso “tiene que ser bueno”.
• Puede escribirse como un foldl’ ligeramente truculento –
queda como ejercicio para el lector.
¿Será realmente la mejor solución?
Hernández-Novich (USB)
Programación Funcional Avanzada
2015
5 / 43
Mejora del desempeño
Buena flojera
Dividir una lista en dos
Una función modular quiere ser reutilizada
halve = go ([] ,[])
where
go ( eac , oac ) []
= ( eac , oac )
go ( eac , oac ) [ x ]
= ( x : eac , oac )
go ( eac , oac ) ( x : y : xs ) = go ( x : eac , y : oac ) xs
Consideren las siguientes expresiones
head . fst . halve [ 1. . 1 00 0 0 00 0 0 0 00 0 0 ]
head . snd . halve [ 1. . 1 00 0 0 00 0 0 0 00 0 0 ]
Hernández-Novich (USB)
Programación Funcional Avanzada
2015
6 / 43
Mejora del desempeño
Buena flojera
Dividir una lista en dos
Una función modular quiere ser reutilizada
halve = go ([] ,[])
where
go ( eac , oac ) []
= ( eac , oac )
go ( eac , oac ) [ x ]
= ( x : eac , oac )
go ( eac , oac ) ( x : y : xs ) = go ( x : eac , y : oac ) xs
Consideren las siguientes expresiones
head . fst . halve [ 1. . 1 00 0 0 00 0 0 0 00 0 0 ]
head . snd . halve [ 1. . 1 00 0 0 00 0 0 0 00 0 0 ]
Ambas requieren procesar toda la lista
antes de producir el resultado.
Hernández-Novich (USB)
Programación Funcional Avanzada
2015
6 / 43
Mejora del desempeño
Buena flojera
Dividir una lista en dos
Agregar flojera paga dividendos
halve xs = ( ping xs , pong xs )
ping []
= []
ping [ x ]
= [x]
ping ( x : _ : xs ) = x : ping xs
pong []
= []
pong [ x ]
= []
pong ( _ : x : xs ) = x : pong xs
• Ambas construyen la lista un thunk a la vez.
• Y ahora
head . fst . halve [ 1. . 1 00 0 0 0 00 0 0 00 0 0 ]
head . snd . halve [ 1. . 1 00 0 0 0 00 0 0 00 0 0 ]
pueden responder en tiempo constante
Hernández-Novich (USB)
Programación Funcional Avanzada
2015
7 / 43
Mejora del desempeño
Buena flojera
Mergesort
¿Cómo afecta a mergesort?
• Cuando msort se use para ordenar una lista completa, ambas
implantaciones de halve producirán el mismo resultado.
• La primera halve recorrerá la lista completa para dividirla en dos –
tiene que llegar hasta el final de la recursión de cola.
• La segunda halve también, pero puede ir entregando elementos a
merge a medida que se los va solicitando.
Hernández-Novich (USB)
Programación Funcional Avanzada
2015
8 / 43
Mejora del desempeño
Buena flojera
Mergesort
¿Cómo afecta a mergesort?
• Cuando msort se use para ordenar una lista completa, ambas
implantaciones de halve producirán el mismo resultado.
• La primera halve recorrerá la lista completa para dividirla en dos –
tiene que llegar hasta el final de la recursión de cola.
• La segunda halve también, pero puede ir entregando elementos a
merge a medida que se los va solicitando.
• La segunda versión es mejor – requiere menos memoria intermedia.
Hernández-Novich (USB)
Programación Funcional Avanzada
2015
8 / 43
Mejora del desempeño
Buena flojera
Mergesort
¿Cómo afecta a mergesort?
• Cuando msort se use para ordenar una lista completa, ambas
implantaciones de halve producirán el mismo resultado.
• La primera halve recorrerá la lista completa para dividirla en dos –
tiene que llegar hasta el final de la recursión de cola.
• La segunda halve también, pero puede ir entregando elementos a
merge a medida que se los va solicitando.
• La segunda versión es mejor – requiere menos memoria intermedia.
• ¿Cuán modular es msort?
min = head . msort
• La primera halve hace que min sea O(n · log n).
• La segunda halve hace que min sea O(n).
Hernández-Novich (USB)
Programación Funcional Avanzada
2015
8 / 43
Mejora del desempeño
Buena flojera
Mergesort
¿Cómo afecta a mergesort?
• Cuando msort se use para ordenar una lista completa, ambas
implantaciones de halve producirán el mismo resultado.
• La primera halve recorrerá la lista completa para dividirla en dos –
tiene que llegar hasta el final de la recursión de cola.
• La segunda halve también, pero puede ir entregando elementos a
merge a medida que se los va solicitando.
• La segunda versión es mejor – requiere menos memoria intermedia.
• ¿Cuán modular es msort?
min = head . msort
• La primera halve hace que min sea O(n · log n).
• La segunda halve hace que min sea O(n).
Compruébenlo usando profiling
Hernández-Novich (USB)
Programación Funcional Avanzada
2015
8 / 43
Mejora del desempeño
La flojera contraataca
La flojera contraataca
• Demasiada flojera puede impactar negativamente el desempeño
• Los thunks requieren memoria en el heap.
• Se mantienen allí “hasta que hacen falta”.
• Si hacen falta inmediatamente, ¿para qué esperar?
• Ya conocen la historia de foldl y foldl’ –
no armar una cascada de sumas sino sumar de una vez.
Hernández-Novich (USB)
Programación Funcional Avanzada
2015
9 / 43
Mejora del desempeño
La flojera contraataca
La flojera contraataca
• Demasiada flojera puede impactar negativamente el desempeño
• Los thunks requieren memoria en el heap.
• Se mantienen allí “hasta que hacen falta”.
• Si hacen falta inmediatamente, ¿para qué esperar?
• Ya conocen la historia de foldl y foldl’ –
no armar una cascada de sumas sino sumar de una vez.
• GHC es capaz de optimizar con Strictness Analysis
• Compilar con la opción -O.
• Detecta funciones estrictas o parcialmente estrictas.
• Genera código que omite los thunks para esos casos.
Hernández-Novich (USB)
Programación Funcional Avanzada
2015
9 / 43
Mejora del desempeño
La flojera contraataca
La flojera contraataca
• Demasiada flojera puede impactar negativamente el desempeño
• Los thunks requieren memoria en el heap.
• Se mantienen allí “hasta que hacen falta”.
• Si hacen falta inmediatamente, ¿para qué esperar?
• Ya conocen la historia de foldl y foldl’ –
no armar una cascada de sumas sino sumar de una vez.
• GHC es capaz de optimizar con Strictness Analysis
• Compilar con la opción -O.
• Detecta funciones estrictas o parcialmente estrictas.
• Genera código que omite los thunks para esos casos.
Si el lenguaje es perezoso,
¿como puede tener funciones estrictas?
Hernández-Novich (USB)
Programación Funcional Avanzada
2015
9 / 43
Mejora del desempeño
La flojera contraataca
Funciones estrictas o semi-estrictas
Los argumentos cuentan la historia
Una función es estricta en un argumento si para evaluar la función
siempre es necesario evaluar el argumento.
null :: [ a ] -> Bool
null [] = True
null _ = False
cond :: Bool -> a -> a -> a
cond True t e = t
cond False t e = e
• null es estricta en su único argumento – es una función estricta.
• cond es estricta en el primer argumento, el resto es perezoso –
es una función semi-estricta.
Hernández-Novich (USB)
Programación Funcional Avanzada
2015
10 / 43
Mejora del desempeño
La flojera contraataca
Strictness analysis tiene sus límites
Sólo detecta cosas obvias decidibles.
suminit :: [ Int ] -> Int -> Int -> ( Int ,[ Int ])
suminit xs n acc =
case n == 0 of
True -> ( acc , xs )
False -> case xs of
[]
-> ( acc ,[])
( x : xs ) -> suminit xs (n -1) ( acc + x )
Hernández-Novich (USB)
Programación Funcional Avanzada
2015
11 / 43
Mejora del desempeño
La flojera contraataca
Strictness analysis tiene sus límites
Sólo detecta cosas obvias decidibles.
suminit :: [ Int ] -> Int -> Int -> ( Int ,[ Int ])
suminit xs n acc =
case n == 0 of
True -> ( acc , xs )
False -> case xs of
[]
-> ( acc ,[])
( x : xs ) -> suminit xs (n -1) ( acc + x )
• GHC puede garantizar que es estricta en el segundo argumento (n) –
genera código para evaluar el (n-1) de forma estricta.
Hernández-Novich (USB)
Programación Funcional Avanzada
2015
11 / 43
Mejora del desempeño
La flojera contraataca
Strictness analysis tiene sus límites
Sólo detecta cosas obvias decidibles.
suminit :: [ Int ] -> Int -> Int -> ( Int ,[ Int ])
suminit xs n acc =
case n == 0 of
True -> ( acc , xs )
False -> case xs of
[]
-> ( acc ,[])
( x : xs ) -> suminit xs (n -1) ( acc + x )
• GHC puede garantizar que es estricta en el segundo argumento (n) –
genera código para evaluar el (n-1) de forma estricta.
• No puede concluir nada definitivo acerca de los usos de acc –
genera código estándar con thunks para las sumas.
Hernández-Novich (USB)
Programación Funcional Avanzada
2015
11 / 43
Mejora del desempeño
La flojera contraataca
Strictness analysis tiene sus límites
Sólo detecta cosas obvias decidibles.
suminit :: [ Int ] -> Int -> Int -> ( Int ,[ Int ])
suminit xs n acc =
case n == 0 of
True -> ( acc , xs )
False -> case xs of
[]
-> ( acc ,[])
( x : xs ) -> suminit xs (n -1) ( acc + x )
• GHC puede garantizar que es estricta en el segundo argumento (n) –
genera código para evaluar el (n-1) de forma estricta.
• No puede concluir nada definitivo acerca de los usos de acc –
genera código estándar con thunks para las sumas.
Nosotros si podemos concluir cosas,
así que nos ponemos estrictos manualmente.
Hernández-Novich (USB)
Programación Funcional Avanzada
2015
11 / 43
Mejora del desempeño
Argumentos Estrictos
Forzar evaluación estricta cuando conviene
Chitty-chitty, bang-bang!
{ - # LANGUAGE BangPatterns # -}
suminit :: [ Int ] -> Int -> Int -> ( Int ,[ Int ])
suminit xs ! n ! acc =
case n == 0 of
True -> ( acc , xs )
False -> case xs of
[]
-> ( acc ,[])
( x : xs ) -> suminit xs (n -1) ( acc + x )
• GHC reescribe los bang patterns como aplicaciones de seq.
• No nos interesa xs estricto – ¡para poder operar sobre listas infinitas!
Hernández-Novich (USB)
Programación Funcional Avanzada
2015
12 / 43
Mejora del desempeño
Constructores Estrictos
¿Y los constructores de datos?
Eran funciones, ¿no?
• Los constructores de datos son funciones y perezosas.
data Pair a b = MakePair a b Int
ghci > : type MakePair
a -> b -> Int -> Pair a b
• No evalúan sus argumentos a menos que sea necesario.
• Thunks inside!
• Contenidos escalares estrictos siempre son una buena idea
data Pair a b = MakePair a b ! Int
Hernández-Novich (USB)
Programación Funcional Avanzada
2015
13 / 43
Mejora del desempeño
Constructores Estrictos
¿Y los constructores de datos?
Eran funciones, ¿no?
• Los constructores de datos son funciones y perezosas.
data Pair a b = MakePair a b Int
ghci > : type MakePair
a -> b -> Int -> Pair a b
• No evalúan sus argumentos a menos que sea necesario.
• Thunks inside!
• Contenidos escalares estrictos siempre son una buena idea
data Pair a b = MakePair a b ! Int
Para todo lo demás, usar Mucho Cuidado™.
Hernández-Novich (USB)
Programación Funcional Avanzada
2015
13 / 43
Mejora del desempeño
Constructores Estrictos
A ver. . .
What would Buddah do?
data Tree = Leaf | Node Int Tree Tree
insert :: Int -> Tree -> Tree
insert x Leaf
= Leaf
insert x ( Node y l r )
| x < y
= Node y ( insert x l ) r
| x > y
= Node y l ( insert x r )
| otherwise = Node x l r
• Es estricta en
Hernández-Novich (USB)
Programación Funcional Avanzada
2015
14 / 43
Mejora del desempeño
Constructores Estrictos
A ver. . .
What would Buddah do?
data Tree = Leaf | Node Int Tree Tree
insert :: Int -> Tree -> Tree
insert x Leaf
= Leaf
insert x ( Node y l r )
| x < y
= Node y ( insert x l ) r
| x > y
= Node y l ( insert x r )
| otherwise = Node x l r
• Es estricta en el segundo argumento.
Hernández-Novich (USB)
Programación Funcional Avanzada
2015
14 / 43
Mejora del desempeño
Constructores Estrictos
A ver. . .
What would Buddah do?
data Tree = Leaf | Node Int Tree Tree
insert :: Int -> Tree -> Tree
insert x Leaf
= Leaf
insert x ( Node y l r )
| x < y
= Node y ( insert x l ) r
| x > y
= Node y l ( insert x r )
| otherwise = Node x l r
• Es estricta en el segundo argumento.
• El segundo argumento podría ser un thunk inmenso. . .
• . . . que siempre es necesario evaluar – es un árbol de búsqueda.
Hernández-Novich (USB)
Programación Funcional Avanzada
2015
14 / 43
Mejora del desempeño
Constructores Estrictos
A ver. . .
What would Buddah do?
data Tree = Leaf | Node Int Tree Tree
insert :: Int -> Tree -> Tree
insert x Leaf
= Leaf
insert x ( Node y l r )
| x < y
= Node y ( insert x l ) r
| x > y
= Node y l ( insert x r )
| otherwise = Node x l r
• Es estricta en el segundo argumento.
• El segundo argumento podría ser un thunk inmenso. . .
• . . . que siempre es necesario evaluar – es un árbol de búsqueda.
• Vale la pena que el tipo de datos sea completamente estricto.
Hernández-Novich (USB)
Programación Funcional Avanzada
2015
14 / 43
Mejora del desempeño
Constructores Estrictos
¿En qué quedamos?
Procrastination pro-tips
• Estructuras arbóreas finitas suelen usar sub-estructuras estrictas
data Set a = Tip | Bin ! Int a !( Set a ) !( Set a )
• Conviene tener el tamaño precalculado – por eso el Int
• Conviene tener la estructura de subárboles precalculada.
• Los contenidos se mantienen perezosos.
Hernández-Novich (USB)
Programación Funcional Avanzada
2015
15 / 43
Mejora del desempeño
Constructores Estrictos
¿En qué quedamos?
Procrastination pro-tips
• Estructuras arbóreas finitas suelen usar sub-estructuras estrictas
data Set a = Tip | Bin ! Int a !( Set a ) !( Set a )
• Conviene tener el tamaño precalculado – por eso el Int
• Conviene tener la estructura de subárboles precalculada.
• Los contenidos se mantienen perezosos.
• $! es la versión estricta de $.
• Si f x utiliza una composición h (g x) que no es estricta en x
vale la pena h $! g x – eso simplifica al máximo el argumento de h.
• Caso particular – procure inyectar valores estrictos en un Monad.
return $ ! foo x
Hernández-Novich (USB)
Programación Funcional Avanzada
2015
15 / 43
Tipos de Datos
Conozca los tipos de datos
Tipos de Datos
• Sistema de Tipos de Haskell extremadamente flexible
• Tipos escalares nativos.
• Equivalencia estructural – type
• Equivalencia por nombres – data y newtype.
Hernández-Novich (USB)
Programación Funcional Avanzada
2015
16 / 43
Tipos de Datos
Conozca los tipos de datos
Tipos de Datos
• Sistema de Tipos de Haskell extremadamente flexible
• Tipos escalares nativos.
• Equivalencia estructural – type
• Equivalencia por nombres – data y newtype.
• Diseñar tipos de datos para lenguajes funcionales requiere tomar en
cuenta y balancear astucia de representación y pereza.
• One does not simply write functional data structures! –
lean lo que Chris Okasaki tiene que decir al respecto.
• La base del lenguaje incluye tipos optimizados.
• Las librerías de la plataforma también.
Hernández-Novich (USB)
Programación Funcional Avanzada
2015
16 / 43
Tipos de Datos
Conozca los tipos de datos
Tipos de Datos
• Sistema de Tipos de Haskell extremadamente flexible
• Tipos escalares nativos.
• Equivalencia estructural – type
• Equivalencia por nombres – data y newtype.
• Diseñar tipos de datos para lenguajes funcionales requiere tomar en
cuenta y balancear astucia de representación y pereza.
• One does not simply write functional data structures! –
lean lo que Chris Okasaki tiene que decir al respecto.
• La base del lenguaje incluye tipos optimizados.
• Las librerías de la plataforma también.
No reinventar la rueda ovalada ni cuadrada.
Veamos con qué contamos.
Hernández-Novich (USB)
Programación Funcional Avanzada
2015
16 / 43
Tipos de Datos
data vs newtype
Tipos de Datos
data vs. newtype
Al definir tipos con un constructor y un campo:
• Podríamos usar un tipo algebráico completo
data Foo a = Foo a
• Podríamos usar un tipo sinónimo
newtype Foo a = Foo a
El constructor del newtype se elimina
a tiempo de compilación – más eficiente.
Hernández-Novich (USB)
Programación Funcional Avanzada
2015
17 / 43
Tipos de Datos
data vs newtype
Prefiera constructores simples
GHC hace unpacking
• Una tupla tiene un constructor simple (,) – dos valores, una tupla.
• Cuando se compila la función
f (x , y ) = { - whatever -}
GHC genera código similar a
f z = case z of (x , y ) -> f ’ x y
f ’ x y = { - whatever -}
• f es el wrapper – inline en todos lados.
• f’ es el worker – hace el trabajo sin tuplas.
Hernández-Novich (USB)
Programación Funcional Avanzada
2015
18 / 43
Tipos de Datos
Boxed vs. Unboxed
Tipos de Datos
Boxed vs. Unboxed – via GHC.Exts
• Tipos lifted – boxed data
• Evaluados, parcialmente evaluados (thunk) o ⊥ (undefined).
• Hace falta una indirección.
• El contenedor – “hey, soy del tipo Foo”
• El contenido – el dato o el thunk que lo evaluará.
Hernández-Novich (USB)
Programación Funcional Avanzada
2015
19 / 43
Tipos de Datos
Boxed vs. Unboxed
Tipos de Datos
Boxed vs. Unboxed – via GHC.Exts
• Tipos lifted – boxed data
• Evaluados, parcialmente evaluados (thunk) o ⊥ (undefined).
• Hace falta una indirección.
• El contenedor – “hey, soy del tipo Foo”
• El contenido – el dato o el thunk que lo evaluará.
• Tipos unlifted – unboxed data
• Sólo pueden estar evaluados completamente – imposible representar ⊥.
• No se pueden pasar a funciones polimórficas.
• No se pueden usar como contenido de un newtype.
• No pueden existir como definiciones top-level.
• Si son escalares, no requieren indirección – ¡mejor desempeño!
• Aumenta la densidad de los contenedores.
• Disponibles al compilar usando -fglasgow-exts.
Hernández-Novich (USB)
Programación Funcional Avanzada
2015
19 / 43
Tipos de Datos
Boxed vs. Unboxed
Usando tipos unboxed
{ - # LANGUAGE MagicHash # -}
import GHC . Exts
n = I # 42#
c = I # ( ord # ’* ’#)
main = print c >> ( print $ show n )
• 42# es un Int# – 32 bits sin adornos.
• No puedo definir n = 42#.
• No se puede pasar a show, porque es polimórfica.
• GHC.Exts provee mecanismos para volver a levantar el tipo –
en este caso I# produce el Int habitual.
Se usan internamente en librerías optimizadas,
o para interactuar con librerías externas en C.
Hernández-Novich (USB)
Programación Funcional Avanzada
2015
20 / 43
Tipos de Datos
Boxed vs. Unboxed
Poca gente quiere escribir. . .
fac # n # = if n # ># 0# then n # *# fac # ( n # -# 1#)
else 1#
unboxInt ( I # i #) = i #
main = do
n <- ( read . head ) ‘ liftM ‘ getArgs
print $ I # ( fac # ( unboxInt n ))
• Los unboxed generalmente terminan en registros.
• Pero hay demasiado “agitar de manos” para hacerlos cómodos en
código general – además, el compilador lo hace cuando puede.
Son usados internamente en librerías optimizadas,
o para interactuar con librerías externas.
Hernández-Novich (USB)
Programación Funcional Avanzada
2015
21 / 43
Tipos de Datos
Las librerías
Tipos de Datos
Tipos numéricos
• Integer tiene precisión arbitraria costosa en espacio –
use las representaciones directas que aprovechan la máquina.
• Data.Int (con signo) – Int8, Int16, Int32 e Int64.
• Data.Word (sin signo) – Word8, Word16, Word32 y Word64.
• fromIntegral del Prelude optimizada para convertir entre ellos.
• Data.Bits – operaciones bit a bit.
• Use Double en lugar de Float.
• Todos los FPU en el fondo usan Double.
• Se reduce el error numérico.
• Si la máquina es de 64 bits, ambos ocupan 64 bits.
Hernández-Novich (USB)
Programación Funcional Avanzada
2015
22 / 43
Tipos de Datos
Las librerías
Funciones y Módulos
Sobrecarga no siempre es tu amiga
• Polimorfismo paramétrico se basa en despacho dinámico
( Num a ) = > a -> a -> a
• Requiere un tercer argumento oculto – tabla de despacho.
• La tabla particular se incorpora a tiempo de ejecución.
• Use firmas explícitas
• Evita sobrecarga sin necesidad (Integral vs. Int).
• ¿Quiere que el compilador le obligue a usar firmas? –
-fwarn-missing-signatures.
Hernández-Novich (USB)
Programación Funcional Avanzada
2015
23 / 43
Tipos de Datos
Las librerías
Módulos
• Exporte explícitamente las funciones, porque eso:
• Activa inlining para funciones que son usadas una sola vez.
• Activa inlining de funciones privadas al módulo.
• Detecta y elimina código inalcanzable.
• Minimiza el riesgo de polimorfismo excesivo.
• Otorga libertad al compilador en la generación de la secuencia de
llamada para funciones privadas.
Hernández-Novich (USB)
Programación Funcional Avanzada
2015
24 / 43
Tipos de Datos
Cadenas eficientes
Más tipos de Datos
Alternativas a String
• String en realidad es [Char] – y cada Char es boxed.
• Data.ByteString – cadenas empaquetadas.
• Vectores de Word8.
• pack y unpack – pasar desde y hacia [Word8]
• Funciones optimizadas para manipularlos – take, fold, map, . . .
• Importe calificado – evite conflictos con Prelude y Data.List.
Hernández-Novich (USB)
Programación Funcional Avanzada
2015
25 / 43
Tipos de Datos
Cadenas eficientes
Más tipos de Datos
Alternativas a String
• String en realidad es [Char] – y cada Char es boxed.
• Data.ByteString – cadenas empaquetadas.
• Vectores de Word8.
• pack y unpack – pasar desde y hacia [Word8]
• Funciones optimizadas para manipularlos – take, fold, map, . . .
• Importe calificado – evite conflictos con Prelude y Data.List.
• Según el juego de caracteres a procesar
• Data.BysteString.Char8 – ASCII, Latin-1, Unicode Basic Latin
• Data.ByteString.UTF8 – Unicode UTF-8
Hernández-Novich (USB)
Programación Funcional Avanzada
2015
25 / 43
Tipos de Datos
Cadenas eficientes
Más tipos de Datos
Alternativas a String
• String en realidad es [Char] – y cada Char es boxed.
• Data.ByteString – cadenas empaquetadas.
• Vectores de Word8.
• pack y unpack – pasar desde y hacia [Word8]
• Funciones optimizadas para manipularlos – take, fold, map, . . .
• Importe calificado – evite conflictos con Prelude y Data.List.
• Según el juego de caracteres a procesar
• Data.BysteString.Char8 – ASCII, Latin-1, Unicode Basic Latin
• Data.ByteString.UTF8 – Unicode UTF-8
• Ambas disponen de versiones perezosas en Data.ByteString.Lazy
capaces de procesar cadenas que no caben en memoria.
Hernández-Novich (USB)
Programación Funcional Avanzada
2015
25 / 43
Tipos de Datos
Cadenas eficientes
Alternativas a String
Una comparación
[Char]
import System . IO
main = readFile " / usr / share / dict / words "
> >= putStrLn . last . lines
Hernández-Novich (USB)
Programación Funcional Avanzada
2015
26 / 43
Tipos de Datos
Cadenas eficientes
Alternativas a String
Una comparación
[Char]
import System . IO
main = readFile " / usr / share / dict / words "
> >= putStrLn . last . lines
Data.ByteString.Char8
import qualified Data . ByteString . Char8 as B
main = B . readFile " / usr / share / dict / words "
> >= B . putStr . last . B . lines
Hernández-Novich (USB)
Programación Funcional Avanzada
2015
26 / 43
Tipos de Datos
Cadenas eficientes
Tipos de Datos
Listas vs. Secuencias
• Listas convencionales ([a])
• O(1) sobre la cabeza de la lista – (:) y head.
• O(i) para acceder al i−ésimo elemento – (!!).
• O(n) para acceder al último elemento – last o (++).
• Ideales para representar pilas o streams.
• Data.Sequence (2-3 finger trees)
• O(1) sobre ambos extremos – (<|) y (|>).
• O(log(min(i, n − i))) para el i−ésimo elemento – index, take y drop.
• O(log(min(n, m))) para concatenar – (><).
• Ideales para representar colas o deques.
• En el Monad Writer siempre se usa Data.Sequence.
Hernández-Novich (USB)
Programación Funcional Avanzada
2015
27 / 43
Tipos de Datos
Contenedores
Contenedores
Estructuras de datos para comer con cubiertos
• Conjuntos
• Data.Set – árboles balanceados.
• Data.IntSet – Big-endian Patricia Trees (Radix Trie)
Hernández-Novich (USB)
Programación Funcional Avanzada
2015
28 / 43
Tipos de Datos
Contenedores
Contenedores
Estructuras de datos para comer con cubiertos
• Conjuntos
• Data.Set – árboles balanceados.
• Data.IntSet – Big-endian Patricia Trees (Radix Trie)
• Diccionarios
• Data.Map – de clave a valor (árboles balanceados).
• Data.IntMap – de enteros a valores (Patricia Trees).
• Versiones perezosas o estrictas en los valores.
Hernández-Novich (USB)
Programación Funcional Avanzada
2015
28 / 43
Tipos de Datos
Contenedores
Contenedores
Estructuras de datos para comer con cubiertos
• Conjuntos
• Data.Set – árboles balanceados.
• Data.IntSet – Big-endian Patricia Trees (Radix Trie)
• Diccionarios
• Data.Map – de clave a valor (árboles balanceados).
• Data.IntMap – de enteros a valores (Patricia Trees).
• Versiones perezosas o estrictas en los valores.
• Data.Graph – grafos y sus algoritmos.
Hernández-Novich (USB)
Programación Funcional Avanzada
2015
28 / 43
Tipos de Datos
Contenedores
Contenedores
Estructuras de datos para comer con cubiertos
• Conjuntos
• Data.Set – árboles balanceados.
• Data.IntSet – Big-endian Patricia Trees (Radix Trie)
• Diccionarios
• Data.Map – de clave a valor (árboles balanceados).
• Data.IntMap – de enteros a valores (Patricia Trees).
• Versiones perezosas o estrictas en los valores.
• Data.Graph – grafos y sus algoritmos.
• Data.Tree – Rose Trees
Hernández-Novich (USB)
Programación Funcional Avanzada
2015
28 / 43
Tipos de Datos
Contenedores
Contenedores
Estructuras de datos para comer con cubiertos
• Conjuntos
• Data.Set – árboles balanceados.
• Data.IntSet – Big-endian Patricia Trees (Radix Trie)
• Diccionarios
• Data.Map – de clave a valor (árboles balanceados).
• Data.IntMap – de enteros a valores (Patricia Trees).
• Versiones perezosas o estrictas en los valores.
• Data.Graph – grafos y sus algoritmos.
• Data.Tree – Rose Trees
• Data.Sequence – 2-3 finger trees.
Hernández-Novich (USB)
Programación Funcional Avanzada
2015
28 / 43
Tipos de Datos
Arreglos
Si tan sólo tuviera arreglos
• Función de índices a valores – nadie quiere escribir todos los casos. . .
• Data.Ix – noción generalizada de “tipo índice”
class Ord a
range
index
inRange
rangeSize
=>
::
::
::
::
Ix a where
(a , a ) -> [ a ]
(a , a ) -> a -> Int
(a , a ) -> a -> Bool
(a , a ) -> Int
• Biyección entre tipo ordenado y los enteros.
• Tamaño y verificación del rango explícitas.
Si algo es ordenable, puede servir de índice. . .
Hernández-Novich (USB)
Programación Funcional Avanzada
2015
29 / 43
Tipos de Datos
Arreglos
Indices. . . te los tengo generalizados!
data MetaVar = Foo | Bar | Baz | Qux | Grok
deriving ( Eq , Ord , Ix , Show )
> range ( Foo , Baz )
[ Foo , Bar , Baz ]
> index ( Bar , Qux ) Baz
1
> inRange ( Foo , Qux ) Grok
False
• Sirve cualquier sub-rango de un rango de valores ordenados.
• Si puedes ordenar cosas, puedes usarlas como índices.
• Números, enumeraciones, tuplas . . .
Hernández-Novich (USB)
Programación Funcional Avanzada
2015
30 / 43
Tipos de Datos
Arreglos
Arreglos. . . te los tengo!
Representación clásica
data Ix i = > Array i e
array :: Ix i = > (i , i ) -> [( i , e )] -> Array i e
(!)
:: Ix i = > Array i e -> i -> e
• array – construye a partir del rango y lista de elementos
correspondientes.
• (!) – es el operador de subindizado.
• Estricto en los límites del rango y en los índices –
perezoso en los valores almacenados en el arreglo.
Hernández-Novich (USB)
Programación Funcional Avanzada
2015
31 / 43
Tipos de Datos
Arreglos
Arreglos. . . te los tengo!
Representación clásica
sqs = array (1 ,100) [( i , i * i ) | i <- [1..100]]
nms = array ( Foo , Baz ) [( m , v ) |
m <- range ( Foo , Baz ) ,
v <- [0.. rangeSize ( Foo , Baz ) - 1]]
> sqs
49
> nms
array
> nms
2
> sqs
4
! 7
( Foo , Baz ) [( Foo ,2) ,( Bar ,2) ,( Baz ,2)]
! Bar
! ( nms ! Bar )
Hernández-Novich (USB)
Programación Funcional Avanzada
2015
32 / 43
Tipos de Datos
Arreglos
Arreglos. . . te los tengo!
Definición recursiva y perezosa
fibs
:: Int -> Array Int Int
fibs n = a
where a = array
(0 , n ) $
[(0 , 1) , (1 , 1)] ++
[( i , a !( i -2) + a !( i -1)) | i <- [2.. n ]]
> fibs 5
array (0 ,6) [(0 ,1) ,(1 ,1) ,(2 ,2) ,(3 ,3) ,(4 ,5) ,(5 ,8)]
> fibs ! 4
5
• El arreglo se define en función de si mismo.
• Muy útil en algunos problemas de programación dinámica.
Hernández-Novich (USB)
Programación Funcional Avanzada
2015
33 / 43
Tipos de Datos
Arreglos
Arreglos. . . te los tengo!
¡En forma de matriz recursiva!
wavefront
:: Int -> Array ( Int , Int ) Int
wavefront n = a
where a =
array ((1 ,1) ,( n , n )) $
[((1 , j ) , 1) | j <- [1.. n ]] ++
[(( i ,1) , 1) | i <- [2.. n ]] ++
[(( i , j ) , a !( i ,j -1) + a !( i -1 ,j -1) + a !( i -1 , j ))
| i <- [2.. n ] , j <- [2.. n ]]
• Uso tuplas como índices – ¡en forma de matriz!
• Primera fila y primera columna llenas de unos.
• Cada celda es la suma de sus vecinos norte, oeste y noroeste.
Hernández-Novich (USB)
Programación Funcional Avanzada
2015
34 / 43
Tipos de Datos
Arreglos
Por favor dime que son mutables
(//) :: ( Ix a ) = > Array a b -> [( a , b )] -> Array a b
• Dado un arreglo reemplazar ciertas posiciones.
• Arreglos clásicos son monolíticos y puros.
• Elementos individuales son inmutables.
• (//) copia el arreglo incorporando los cambios.
• Suficientes si uno necesita una tabla multidimensional estática –
insuficientes si uno necesita transformar la tabla progresivamente.
Por eso es que hay librerías alternativas. . .
Hernández-Novich (USB)
Programación Funcional Avanzada
2015
35 / 43
Tipos de Datos
Arreglos
Una taxonomía de arreglos
. . . y sus repercusiones
• Array – puros e inmutables
• STArray – mónadicos mutables en el Monad ST
• IOArray – mónadicos mutables en el Monad IO
Hernández-Novich (USB)
Programación Funcional Avanzada
2015
36 / 43
Tipos de Datos
Arreglos
Array – Arreglos Inmutables
Absolutamente puros
import Data . Array
change :: ( Array Int Int , Array Int Int )
change = ( original , cambiado )
where original = listArray (1 ,4) ( repeat 42)
cambiado = original // [(2 , 69)]
main = print change
• Excelentes para código puro con búsquedas al azar.
• Costosos para modificaciones – siempre se copian.
• accumArray – quizás no necesitabas mutarlo.
• UArray de Data.Array.Unboxed almacena valores unboxed.
Hernández-Novich (USB)
Programación Funcional Avanzada
2015
37 / 43
Tipos de Datos
Arreglos
STArray – Arreglos Mutables en el Monad ST
Al borde de la impureza, pero libres de I/O
import Control . Monad . ST
import Data . Array . ST
change :: ST s ( Int , Int )
change = do
m <- newArray (1 ,4) 42 :: ST s ( STArray s Int Int )
a <- readArray m 2
writeArray m 2 69
b <- readArray m 2
return (a , b )
main = print $ runST change
• Excelentes para código monádico con búsquedas al azar.
• Modificación económica – Monad ST mantiene el cambio.
• STUArray de Data.Array.ST almacena valores unboxed.
Hernández-Novich (USB)
Programación Funcional Avanzada
2015
38 / 43
Tipos de Datos
Arreglos
IOArray – Arreglos Mutables en el Monad IO
Arreglos sin escapatoria de I/O
import Data . Array . IO
main = do
m <- newArray (1 ,4) 42 :: IO ( IOArray Int Int )
a <- readArray m 2
writeArray m 2 69
b <- readArray m 2
return (a , b )
• Cuando los contenidos van y vienen vía IO –
aprovechar hGetArray y hPutArray para el intercambio.
• IOUArray de Data.Array.IO almacena valores unboxed.
Hernández-Novich (USB)
Programación Funcional Avanzada
2015
39 / 43
Tipos de Datos
Arreglos
Ida y vuelta
De mutable a inmutable, y de regreso
freeze ::
=>
thaw
::
=>
( Ix
a i
( Ix
a i
i , MArray
e -> m ( b
i , IArray
e -> m ( b
a
i
a
i
e m , IArray b e )
e)
e , MArray b e m )
e)
• IArray es la clase de arreglos inmutables – Array
• MArray es la clase de arreglos mutables – IOArray y STArray
• Ambas operaciones requieren sacar una copia completa del arrelgo.
Hernández-Novich (USB)
Programación Funcional Avanzada
2015
40 / 43
Tipos de Datos
Arreglos
Algunas condiciones aplican. . .
• Versiones unboxed sólo pueden almacenar valores con tamaño fijo.
• Tipos primitivos van bien – Bool, Int, Double, Char, Word. . .
• No puedes usar Integer, String, tuplas, . . .
• Como son unboxed deben evaluarse todos al intentar usar el arreglo –
pierdes los beneficios de la evaluación perezosa.
• A efectos prácticos son como los arreglos de C.
• Muchos arreglos mutables fastidian al recolector de basura –
evítelos o use +RTS -A8m -RTS para aliviar el problema.
Hernández-Novich (USB)
Programación Funcional Avanzada
2015
41 / 43
Tips para programas concurrentes
Tips para programas concurrentes
Programas concurrentes
• No compile -threaded para máquinas con un sólo núcleo.
• No use el hilo principal para hacer el trabajo.
• La comunicación entre el hilo principal y el resto es mucho más lenta
que entre los hilos subordinados.
• El hilo principal corresponde a un hilo del sistema operativo y tiene un
costo mayor de mantenimiento.
Hernández-Novich (USB)
Programación Funcional Avanzada
2015
42 / 43
Bibliografía
Quiero saber más. . .
• Documentación de Data.Bits
• Documentación de Data.Int
• Documentación de Data.Word
• Documentación de Data.ByteString
• Documentación de Data.Array
• Documentación del paquete containers
• Documentación de GHC en relación a unboxed types
• Purely Functional Data Structures
Okasaki, 1996
Hernández-Novich (USB)
Programación Funcional Avanzada
2015
43 / 43

Download Report