[F#] Funciones recursivas a lápiz y papel

Si hay algo que me ha gustado de la programación funcional (en lo poco que llevo estudiándole) es poder razonar sobre las funciones que escribo como meras funciones matemáticas, nada de tener que pensar en mutaciones de estado de un objeto o efectos colaterales al invocar determinada función. Y si hay algo que me gusta de las matemáticas, y la algoritmia en particular, es llenar hojas enteras de números, formulas y dibujos para razonar, abstraer y entender distintos conceptos y problemas. Hay gente que usa algún software u hojas de calculo para esto, a mi me gusta el lápiz y el papel.

El concepto de función recursiva es un tema fundamental en cualquier texto de programación funcional (al menos en los que yo he visto siempre tocan el tema), y en la web podemos encontrar definiciones, y en MSDN la implementación de F#

Lo que quiero exponer aquí es cómo razonar sobre las funciones recursivas cómo si estuviéramos operando sobre una función matemática. ¿Por qué? porqué hasta hace muy poco me complicaba y terminaba acudiendo a algún trace/log.

I'm a sad panda

Ahora veamos un ejemplo de cómo se puede analizar una función recursiva. Dada la función maxlist del tipo 'a list -> a que retornará el elemento mayor de una lista.

    let rec maxlist = 
        function
        | []    -> failwith "Lista vacia"
        | [x]   -> x
        | x::xs -> max x (maxlist xs)

Siempre que se usa recursividad con listas se puede sacar provecho del pattern matching para escribir código más expresivo. Viendo la función podemos deducir que: Para una lista vacía se lanzará una excepción, para una lista con un elemento regresaremos ese único elemento, y, para una lista con más de un elemento se aplicará la función max para el head de la lista y el resultado de llamar, nuevamente, la función maxlist con el tail de la lista como argumento. Entonces, usando lápiz y papel, podemos resolver la ecuación:

 
maxlist [5;1;3;7]
= max 5 (maxlist [1;3;7])
= max 5 (max 1 (maxlist [3;7]))
= max 5 (max 1 (max 3 (maxlist [7]))) //maxlist de una lista con un elemento retorna dicho elemento
= max 5 (max 1 (max 3 7))
= max 5 (max 1 7)
= max 5 7
= 7

De esta forma, resolviendo las ecuaciones como si fueran funciones matemáticas, podemos resolver las funciones recursivas.

En el siguiente ejemplo usaremos tres funciones: halve que partirá una lista en dos (retornando una tupla con las dos listas). La función mergeordlist que ordenará dos listas cuyos elementos ya estén ordenados dentro de una nueva lista. Y, finalmente, la función msort que usando estas otras dos funciones ordenará los elementos de una lista.

    let halve xs = List.splitAt (List.length xs / 2) xs

    let rec mergeordlists xs ys = 
        match (xs, ys) with
        | ([], ys) -> ys
        | (xs, []) -> xs
        | (x::xs, y::ys) -> 
            if x <= y then x :: mergeordlists xs (y::ys)
            else y :: mergeordlists (x::xs) ys

    let rec msort  =
        function
        | [] -> []
        | [x] -> [x]
        | xs -> 
            let (ys, zs) = halve xs
            mergeordlists (msort ys) (msort zs)

¿Cómo podemos resolver la función msort para un determinado conjunto de datos? ¡Fácil! reemplazando valores y resolviendo las ecuaciones siguiendo el orden de los paréntesis

msort [3;1;5;2]
= halve [3;1;5;2] // ([3;1],[5;2]) primero se resuelve halve
--> mergeordlist (msort [3;1]) (msort [5;2]) // reemplazamos los valores y se llama de nuevo a msort
= halve [3;1] // ([3],[1]) 
--> mergeordlist (mergeordlist (msort [3]) (msort [1])) (msort [5;2])
= mergeordlist (mergeordlist [3] (msort [1])) (msort [5;2]) //llamar a msort con una lista de un elemento devuelve la lista "[3]"
= mergeordlist (mergeordlist [3] [1]) (msort [5;2])
= halve [5;2] // ([5], [2])
--> mergeordlist (mergeordlist [3] [1]) (mergeordlist (msort [5]) (msort [2]))
= mergeordlist (mergeordlist [3] [1]) (mergeordlist [5] (msort [2]))
= mergeordlist (mergeordlist [3] [1]) (mergeordlist [5] [2])
= mergeordlist [1;3] (mergeordlist [5] [2])
= mergeordlist [1;3] [2;5]
= [1;2;3;5]

Entender una función recursiva usando lápiz y papel es como comerse una naranja

Espero les sea de útilidad.

Hasta el próximo post.

Anuncios
[F#] Funciones recursivas a lápiz y papel

Un comentario en “[F#] Funciones recursivas a lápiz y papel

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s