Haskell Hero

Haskell Hero es un manual interactivo del lenguaje Haskell para principiantes.

Tipo de funciones compuestas

<= Eta conversión lección anterior lección siguiente foldr, foldl =>

Un ejemplo simple 1

¿Qué es el tipo de la función (odd . snd)?

En la lección Funciones útiles podéis encontrar esta función representada por una caja. Para repetir: ¿Qué es el tipo de función? Es una definición de tipos de valores que entran en la función y el tipo del valor al que se evalúa la función. Todas las partes están separadas por flechas ->.

El tipo de una función compuesta consta entonces de valores que entran al principio y de las que se devuelven al fin. Valores de resultados intermedio no nos interesan.

Como podemos ver en el imagen de la otra lección, la función (odd . snd) toma una dupla que consta de cualquier cosa y un número entero. La función después devuelve un valor booleano. El tipo de nuestra función es entonces:

odd . snd :: (a, Integer) -> Bool

Un ejemplo simple 2

¿Qué es el tipo de la función head . head?

La función head toma una lista y devuelve su primer elemento. Por ejemplo de esta manera:

head [3,4,5]  ~>  3

Sin embargo, si aplicamos la función head . head a esta lista, el cálculo termina con un error:

   (head . head) [3,4,5]
~> head (head [3,4,5])
~> head 3
~/>

Quisieramos que la primera aplicación de la función head devolviera una lista para que la segunda aplicación de la función head pudeira sacar el primer elemento de ella. ¿Cómo lo vamos a hacer? Dejamos la función head . head tomar una lista de listas.

   (head . head) [[3,10,14], [8,4,13,15], []]
~> head (head [[3,10,14], [8,4,13,15], []])
~> head [3,10,14]
~> 3

Ya que el tipo de lista de entrada no es importante para la función head, podemos darle una lista de cualquier cosa. El tipo final es el siguiente:

head . head :: [[a]] -> a

Convertimos en pointwise

Pointwise es una notación opuesta a la notación en estilo pointfree. En la expresión pointfree la lambda se sustituye por operadores (.), en el estilo pointwise los operadores (.) se sustituyen por lambdas.

Para la conversión de pointfree a pointwise necesitamos solo tres reglas:

la definición de la función (.):
```
(f . g) x = f (g x)
```
todas las maneras como escribir la aplicación de una función binaria a sus parámetros. En otras palabras, necesitamos saber que todas las expresiónes son sustituibles:
```
5 + 3
(+) 5 3
(5+) 3
(+3) 5
```
la adición de un parámetro al lado derecho de la expresión
```
[expresión] = \x -> ([expresión]) x
```

Por medio de estas reglas podemos convertir cualquier expresión del estilo pointfree al estilo pointwise.

Un ejemplo más complejo

Definid el tipo más general de la función (.(,)) . (.) . (,).

Esta tarea se puede resolver de muchas maneras. Aquí mostramos la conversión de la función al estilo pointwise y después la declaración de tipo de ella.

Primero hay que decidir donde poner las paréntesis.

((.(,)) . (.)) . (,)

(.(,)) . ((.) . (,))

En la tabla de prioridades y asociación encontramos que (.) asocia de la derecha, lo que significa que las paréntesis se deberían poner de manera siguiente:

(.(,)) . ((.) . (,))

Ahora ya podemos empezar con la propia conversión al estilo pointwise. Durante la conversión al estilo pointfree estabamos quitando los parámetros. Aquí vamos a añadirlos. Aplicamos entonces la nuestra función al parámetro x.

\x -> ((.(,)) . ((.) . (,))) x

La expresión la modificamos según la definición de (.): (nota: el signo ===> es solo un signo definido por nosotros para la reducción de la notación, no es un operador de Haskell. Significa "vamos a convertir esto en esto")

\x -> ((.(,)) . ((.) . (,))) x
      (--f--- . -----g-----) x

===>

\x -> (.(,)) (((.) . (,)) x)
      -- f - (---- g ---- x)

Ahora utilizamos el hecho de que (+5) 3 es lo mismo que 3 + 5.

\x -> (.(,)) (((.) . (,)) x)
      (+ 5 ) (----- 3 -----)

===>

\x -> (((.) . (,)) x) . (,) 
      (----- 3 -----) +  5

Ahora modificamos ((.) . (,)) x según la definición de (.).

\x -> (((.) . (,)) x) . (,) 
       ( f  .  g ) x

===>

\x -> ((.) ((,) x)) . (,)
        f  ( g  x)

Ahora ya hemos convertido todo lo que podíamos pero la función todavía no está en el estilo pointwise. Añadimos entonces un nuevo parámetro general, por ejemplo y.

\x y -> (((.) ((,) x)) . (,)) y

Ahora podemos utilizar la definición de (.) otra vez.

\x y -> (((.) ((,) x)) . (,)) y
        (----- f ----- .  g ) y

===>

\x y -> ((.) ((,) x)) ((,) y)
        ----- f ----- ( g  x)

En este momento tenemos la expresión en la forma ((+) 3) 5 y lo vamos a convertir en 3 + 5.

\x y -> ((.) ((,) x)) ((,) y)
        ((+) -- 3 --) -- 5 --

===>

\x y -> ((,) x) . ((,) y)
        -- 3 -- + -- 5 --

Ahora no podemos modificar la notación de ninguna manera pero todavía no es una expresión que se evalúe completamente. Por eso aplicamos toda la expresión a un argumento nuevo que llamamos por ejemplo z.

\x y z -> (((,) x) . ((,) y)) z

Después quitamos el operador (.) de manera típica.

\x y z -> (((,) x) . ((,) y)) z
          (-- f -- . -- g --) x

===>

\x y z -> ((,) x) (((,) y) z)
          -- f -- (-- g -- x)

Todos los operadores (.) están quitados, ahora nos queda solo convertir la definición en la notación infija para que sea más claro. Primero convertimos la subexpresión ((,) y) z.

\x y z -> ((,) x) (((,) y) z)
                   ((+) 3) 5

===>

\x y z -> ((,) x) (y,z)
                   3+5

Y luego toda la expresión.

\x y z -> ((,) x) (y,z)
          ((+) 3) - 5 -

===>

\x y z -> (x,(y,z))
           3+ -5-

¿A qué hemos llegado?

No podíamos decir nada sobre la función (.(,)) . (.) . (,) en el estilo pointfree. Sin embargo, podemos decir mucho sobre la función \x y z -> (x,(y,z)). Por ejemplo podemos decir que es una función ternaria que convierte los tres parámetros en una dupla en la que el primer elemento es el primer parámetro y el segundo elemento es una dupla formada por el segundo y el tercero parámetro.

¿Qué es entonces el tipo de la función (.(,)) . (.) . (,)? Es el mismo como el tipo de la función \x y z -> (x,(y,z)). El operador (,) no tiene ningunas restricciones de tipo. Podemos aplicarlo a cualquier dos parámetros y nos devuelve una dupla. El tipo de nuestra función entonces será el siguiente:

(.(,)) . (.) . (,) :: a -> b -> c -> (a,(b,c))

<= Eta conversión lección anterior lección siguiente foldr, foldl =>