"Recordar" valores en la programación funcional

He decidido asumir la tarea de aprender programación funcional. Hasta ahora ha sido una explosión, y he 'visto la luz' por así decirlo. Desafortunadamente, en realidad no conozco a ningún programador funcional del que pueda rechazar preguntas. Presentamos Stack Exchange.

Estoy tomando un curso de desarrollo web / software, pero mi instructor no está familiarizado con la programación funcional. Está bien que lo use, y solo me pidió que lo ayudara a entender cómo funciona para que pueda leer mejor mi código.

Decidí que la mejor manera de hacerlo sería ilustrando una función matemática simple, como elevar un valor a una potencia. En teoría, podría hacerlo fácilmente con una función preconstruida, pero eso anularía el propósito de un ejemplo.

De todos modos, tengo algunas dificultades para descubrir cómo mantener un valor. Como se trata de programación funcional, no puedo cambiar la variable. Si tuviera que codificar esto imperativamente, se vería así:

(El siguiente es todo pseudocódigo)

f(x,y) {
  int z = x;
  for(int i = 0, i < y; i++){
    x = x * z;
  }
  return x;
}

En programación funcional, no estaba seguro. Esto es lo que se me ocurrió:

f(x,y,z){
  if z == 'null',
    f(x,y,x);
  else if y > 1,
    f(x*z,y-1,z);
  else
    return x;
}

¿Es esto correcto? Necesito mantener un valor, zen ambos casos, pero no estaba seguro de cómo hacerlo en la programación de funciones. En teoría, la forma en que lo hice funciona, pero no estaba seguro de si era "correcto". Hay una mejor manera de hacerlo?

En primer lugar, felicidades por "ver la luz". Has hecho del mundo del software un lugar mejor al expandir tus horizontes.

En segundo lugar, honestamente no hay forma de que un profesor que no entienda la programación funcional pueda decir algo útil sobre su código, aparte de comentarios triviales como "la sangría se ve". Esto no es tan sorprendente en un curso de desarrollo web, ya que la mayoría del desarrollo web se realiza utilizando HTML / CSS / JavaScript. Dependiendo de lo mucho que realmente le interese aprender el desarrollo web, es posible que desee esforzarse por aprender las herramientas que su profesor está enseñando (aunque sea doloroso, lo sé por experiencia).

Para abordar la pregunta planteada: si su código imperativo usa un bucle, entonces es probable que su código funcional sea recursivo.

(* raises x to the power of y *)
fun pow (x: real) (y: int) : real = 
    if y = 1 then x else x * (pow x (y-1))

Tenga en cuenta que este algoritmo es en realidad más o menos idéntico al código imperativo. De hecho, uno podría considerar que el ciclo anterior es azúcar sintáctico para procesos recursivos iterativos.

Como nota al margen, de hecho no hay necesidad de un valor zen su código imperativo o funcional. Deberías haber escrito tu función imperativa de la siguiente manera:

def pow(x, y):
    var ret = 1
    for (i = 0; i < y; i++)
         ret = ret * x
    return ret

en lugar de cambiar el significado de la variable x.

Esto es realmente solo una adición a la respuesta de gardenhead, pero me gustaría señalar que hay un nombre para el patrón que estás viendo: plegado.

En la programación funcional, un pliegue es una forma de combinar una serie de valores que "recuerdan" un valor entre cada operación. Considere agregar una lista de números imperativamente:

def sum_all(xs):
  total = 0
  for x in xs:
    total = total + x
  return total

Tomamos una lista de valores xsy un estado inicial de 0(representado por totalen este caso). Entonces, para cada xen xs, combinamos ese valor con el estado actual de acuerdo con alguna operación de combinación (en este caso la adición), y utilizar el resultado como el nuevo estado. En esencia, sum_all([1, 2, 3])es equivalente a (3 + (2 + (1 + 0))). Este patrón se puede extraer en una función de orden superior , una función que acepta funciones como argumentos:

def fold(items, initial_state, combiner_func):
  state = initial_state
  for item in items:
    state = combiner_func(item, state)
  return state

def sum_all(xs):
  return fold(xs, 0, lambda x y: x + y)

Esta implementación de foldtodavía es imprescindible, pero también se puede hacer de forma recursiva:

def fold_recursive(items, initial_state, combiner_func):
  if not is_empty(items):
    state = combiner_func(initial_state, first_item(items))
    return fold_recursive(rest_items(items), state, combiner_func)
  else:
    return initial_state

Expresado en términos de un pliegue, su función es simplemente:

def exponent(base, power):
  return fold(repeat(base, power), 1, lambda x y: x * y))

... donde repeat(x, n)devuelve una lista de ncopias de x.

Muchos lenguajes, particularmente aquellos orientados a la programación funcional, ofrecen plegado en su biblioteca estándar. Incluso Javascript lo proporciona bajo el nombre reduce. En general, si te encuentras usando la recursividad para "recordar" un valor en un bucle de algún tipo, probablemente quieras un pliegue.

Esta es una respuesta complementaria para ayudar a explicar mapas y pliegues. Para los ejemplos a continuación, usaré esta lista. Recuerde, esta lista es inmutable, por lo que nunca cambiará:

var numbers = [1, 2, 3, 4, 5]

Usaré números en mis ejemplos porque conducen a un código fácil de leer. Sin embargo, recuerde que los pliegues se pueden usar para cualquier cosa para la que se pueda usar un ciclo imperativo tradicional.

Un mapa toma una lista de algo y una función, y devuelve una lista que fue modificada usando la función. Cada elemento se pasa a la función y se convierte en lo que devuelve la función.

El ejemplo más fácil de esto es simplemente agregar un número a cada número en una lista. Usaré pseudocódigo para que sea independiente del lenguaje:

function add-two(n):
    return n + 2

var numbers2 =
    map(add-two, numbers) 

Si imprimiste numbers2, verías [3, 4, 5, 6, 7]cuál es la primera lista con 2 agregados a cada elemento. Observe que la función add-twose le dio mapa usar.

Los pliegues son similares, excepto que la función que debe darles debe tomar 2 argumentos. El primer argumento suele ser el acumulador (en un pliegue izquierdo, que son los más comunes). El acumulador son los datos que se pasan durante el bucle. El segundo argumento es el elemento actual de la lista; al igual que arriba para la mapfunción.

function add-together(n1, n2):
    return n1 + n2

var sum =
    fold(add-together, 0, numbers)

Si imprimiera sum, vería la suma de la lista de números: 15.

Aquí están los argumentos a foldhacer:

1. Esta es la función que le estamos dando al doblez. El pliegue pasará la función al acumulador actual y al elemento actual de la lista. Lo que devuelva la función se convertirá en el nuevo acumulador, que pasará a la función la próxima vez. Así es como "recuerda" los valores cuando se repite al estilo FP. Le di una función que toma 2 números y los agrega.

2. Este es el acumulador inicial; cómo comienza el acumulador antes de que se procesen los elementos de la lista Cuando sumas números, ¿cuál es el total antes de que hayas sumado números? 0, que pasé como segundo argumento.

3. Por último, al igual que con el mapa, también pasamos la lista de números para que se procese.

Si los pliegues aún no tienen sentido, considere esto. Cuando escribes:

# Notice I passed the plus operator directly this time, 
#  instead of wrapping it in another function. 
fold(+, 0, numbers)

Básicamente, coloca la función aprobada entre cada elemento de la lista y agrega el acumulador inicial a la izquierda o a la derecha (dependiendo de si es un pliegue a la izquierda o a la derecha), entonces:

[1, 2, 3, 4, 5]

Se convierte en:

0 + 1 + 2 + 3 + 4 + 5
^ Note the initial accumulator being added onto the left (for a left fold).

Lo que equivale a 15.

Use a mapcuando desee convertir una lista en otra lista, de la misma longitud.

Use a foldcuando desee convertir una lista en un solo valor, como sumar una lista de números.

Sin embargo, como señaló @Jorg en los comentarios, el "valor único" no necesita ser algo simple como un número; ¡podría ser cualquier objeto individual, incluida una lista o una tupla! La forma en que realmente hice pliegues para mí fue definir un mapa en términos de pliegue. Observe cómo el acumulador es una lista:

function map(f, list):
    fold(
        function(xs, x): # xs is the list that has been processed so far
            xs.add( f(x) ) # Add returns the list instead of mutating it
        , [] # Before any of the list has been processed, we have an empty list
        , list) 

Honestamente, una vez que comprenda cada uno, se dará cuenta de que casi cualquier bucle puede ser reemplazado por un pliegue o un mapa.

Es difícil encontrar buenos problemas que no se puedan resolver con la funcionalidad integrada. Y si está integrado, debería usarse como un ejemplo de buen estilo en el lenguaje x.

En haskell, por ejemplo, ya tienes la función (^)en Preludio.

O si quieres hacerlo más programáticamente product (replicate y x)

Lo que digo es que es difícil mostrar las fortalezas de un estilo / lenguaje si no usa las funciones que proporciona. Sin embargo, podría ser un buen paso para mostrar cómo funciona detrás de escena, pero creo que debe codificar la mejor manera en el idioma que esté usando y luego ayudar a la persona de allí a comprender lo que está sucediendo si es necesario.