haskell - ¿Lista de fragmentos de código funcional para programadores de procedimientos?
f# ocaml (5)
A veces todavía me quedo atascado tratando de traducir código de procedimiento en código funcional.
¿Hay una lista de idiomas / fragmentos funcionales que se asignan a los idiomas / fragmentos de procedimiento?
Editar
Dado que no parece haber un sitio web centralizado de estos fragmentos, estoy convirtiendo esto en una wiki de la comunidad. Por favor, pegue cualquier fragmento de procedimiento -> funcional aquí.
(Editado de este post en fshub )
La primera vez que fui a buscar un descanso / continuar en OCaml / F #, me lanzó a un bucle (infinito), por así decirlo, ¡porque no existe tal cosa! En OCaml, se pueden usar excepciones para romper un bucle porque son muy baratos, pero en F # (en .NET) la sobrecarga es bastante alta y no es útil para el control de flujo "normal".
Esto surgió cuando se jugaba con algoritmos de clasificación hace un tiempo (para matar algún tiempo), que hacen un uso intenso de repetir / hasta y romper. Me di cuenta de que las funciones de llamada de cola recursivas pueden lograr exactamente el mismo resultado, con solo un ligero toque de legibilidad. Por lo tanto, tiré ''bDone mutable'' y ''si bien no bDone'' e intenté escribir el código sin estas construcciones imperativas. Lo siguiente destila solo las partes en bucle y muestra cómo escribir repetir / hasta, hacer / mientras, mientras / hacer, romper / continuar y probar el código de estilo en el medio utilizando las llamadas de cola. Parece que todos estos se ejecutan exactamente a la misma velocidad que la declaración tradicional F # ''while'', pero su millaje puede variar (algunas plataformas pueden no implementar correctamente el tailcall y, por lo tanto, pueden acumular fallas hasta que estén parcheadas). Al final hay un algoritmo de clasificación (incorrecto) escrito en ambos estilos, para comparación.
Comencemos con un bucle ''do / while'', escrito en el estilo imperativo tradicional de F #, luego observemos las variaciones funcionales que proporcionan el mismo tipo de bucle, así como diferentes semánticas como while / do, repetir / hasta, probar en el medio , e incluso romper / continuar (sin mónadas .. um, flujos de trabajo!).
#light
(* something to work on... *)
let v = ref 0
let f() = incr v;
let g() = !v;
let N = 100000000
let imperDoWhile() =
let mutable x = 0
let mutable bDone = false
while not bDone do
f()
x <- x + 1
if x >= N then bDone <- true
Ok, eso es bastante fácil. Tenga en cuenta que f () siempre se llama al menos una vez (hacer / mientras).
Aquí está el mismo código, pero en un estilo funcional. Tenga en cuenta que no necesitamos declarar un objeto mutable aquí.
let funDoWhile() =
let rec loop x =
f() (*Do*)
if x < N then (*While*)
loop (x+1)
loop 0
Podemos convertir eso en un do / while tradicional poniendo la llamada a la función dentro del bloque if.
let funWhileDo() =
let rec loop x =
if x < N then (*While*)
f() (*Do*)
loop (x+1)
loop 0
¿Qué hay de repetir un bloque hasta que alguna condición sea verdadera (repetir / hasta)? Suficientemente fácil...
let funRepeatUntil() =
let rec loop x =
f() (*Repeat*)
if x >= N then () (*Until*)
else loop (x+1)
loop 0
¿Qué fue eso de una ruptura sin monada? Bueno, solo introduce una expresión condicional que devuelva ''unidad'', como en:
let funBreak() =
let rec loop() =
let x = g()
if x > N then () (*break*)
else
f()
loop()
loop()
¿Qué tal continuar? Bueno, eso es sólo otra llamada a bucle! Primero, con una muleta de sintaxis:
let funBreakContinue() =
let break'' () = ()
let rec continue'' () =
let x = g()
if x > N then break''()
elif x % 2 = 0 then
f(); f(); f();
continue''()
else
f()
continue''()
continue''()
Y luego otra vez sin la muleta de sintaxis (fea):
let funBreakContinue''() =
let rec loop () =
let x = g()
if x > N then ()
elif x % 2 = 0 then
f(); f(); f();
loop()
else
f()
loop ()
loop()
¡Muy fácil!
Un buen resultado de estas formas de bucle es que hace que sea más fácil detectar e implementar estados en sus bucles. Por ejemplo, una ordenación de burbujas continuamente recorre una matriz completa, intercambiando valores que están fuera de lugar a medida que los encuentra. Realiza un seguimiento de si un pase sobre la matriz produjo algún intercambio. Si no, cada valor debe estar en el lugar correcto, para que la clasificación pueda terminar. Como optimización, en cada paso a través de la matriz, el último valor de la matriz termina ordenado en el lugar correcto. Por lo tanto, el bucle se puede acortar en uno cada vez. La mayoría de los algoritmos comprueban un intercambio y actualizan un indicador "bModified" cada vez que hay uno. Sin embargo, una vez que se realiza el primer intercambio, no hay necesidad de esa asignación; ¡Ya está configurado como verdadero!
Aquí está el código F # que implementa una ordenación de burbuja (sí, la ordenación de burbuja es un algoritmo terrible; es una secuencia rápida). Al final es una implementación imperativa que no cambia de estado; actualiza la bandera bModified para cada intercambio. Curiosamente, la solución imperativa es más rápida en arreglos pequeños y solo uno o dos por ciento más lenta en los más grandes. (Hecho para un buen ejemplo, sin embargo).
let inline sort2 f i j (a:''a array) =
let i'' = a.[ i ]
let j'' = a.[ j ]
if f i'' j'' > 0 then
a.[ i ] <- j''
a.[ j ] <- i''
let bubble f (xs:''a array) =
if xs.Length = 0
then ()
let rec modified i endix =
if i = endix then
unmodified 0 (endix-1)
else
let j = i+1
sort2 f i j xs
modified j endix
and unmodified i endix =
if i = endix then
()
else
let j = i+1
let i'' = xs.[ i ]
let j'' = xs.[ j ]
if f i'' j'' > 0 then
xs.[ i ] <- j''
xs.[ j ] <- i''
modified j endix
else
unmodified j endix
in unmodified 0 (xs.Length-1)
let bubble_imperitive f (xs:''a array) =
let mutable bModified = true
let mutable endix = xs.Length - 1
while bModified do
bModified <- false
endix <- endix - 1
for i in 0..endix do
let j = i+1
let i'' = xs.[ i ]
let j'' = xs.[ j ]
if f i'' j'' > 0 then
xs.[ i ] <- j''
xs.[ j ] <- i''
bModified <- true
done
done
El pliegue es una función muy interesante, que es central en muchos algoritmos funcionales. Digamos que queremos agregar todos los elementos de una lista. En el código de procedimiento, generalmente creará una variable de acumulador y la establecerá en 0, luego recorrerá la lista e incrementará el acumulador según el elemento.
En Ocaml, realiza la misma acción de una manera funcional utilizando fold:
List.fold_left (+) 0 [1; 2; 3];;
- : int = 6
Usando fold, puede, por ejemplo, contar el número de palabras en la lista y concatenarlas al mismo tiempo:
List.fold_left (fun (count, concat) e -> (count + 1, concat ^ e)) (0, "") ["a"; "b"; "c"];;
- : int * string = (3, "abc")
Otra utilización útil del pliegue es copiar un vector en un conjunto. Como los conjuntos en Ocaml son inmutables, efectivamente debe crear para cada elemento de la lista un nuevo conjunto que contenga el conjunto anterior más ese nuevo elemento.
module Int = struct type t = int let compare = compare end;;
module IntSet = Set.Make(Int);;
let s = List.fold_left (fun set e -> IntSet.add e set) IntSet.empty [1; 2; 3];;
val s : IntSet.t = <abstr>
IntSet.elements s;;
- : IntSet.elt list = [1; 2; 3]
Aquí, nuestro objeto inicial es un conjunto vacío, y en cada llamada, se crea un conjunto nuevo, basado en el conjunto anterior y el elemento actual utilizando IntSet.add.
Implemente pliegue de forma recursiva una vez, para saber cómo se hace bajo el capó, luego use la versión incorporada en todas partes. Incluso en C ++, con std::accumulate !
El proyecto PLEAC tiene casi exactamente este objetivo: implementar todos los ejemplos en el libro de cocina de Perl en otros idiomas. Aquí están los enlaces a la versión de ocaml (que es uno de los tres 100% completos) http://pleac.sourceforge.net/pleac_ocaml/index.html
Oh, ahora esta es una pregunta ingeniosa. Éstos son algunos, recortes de código en python o algo cloe:
Para los bucles se pueden reemplazar con iteradores.
stripped_list = [line.strip() for line in line_list]Para los bucles se pueden reemplazar con aplicar o mapear o filtrar.
mapa (superior, [''frase'', ''fragmento'']) [''SENTENCIA'', ''FRAGMENTO'']
Anidado para bucles con composición de funciones.
Recursión de cola en lugar de bucles.
Generador de expresiones en lugar de para bucles.
sum(x*x for x in range(10))
Pregunta de la vieja tarea:
La función
(define f-imperative (y) (x) ; x is a local variable
(begin
(set x e)
(while (p x y)
(set x (g x y)))
(h x y)))
Se encuentra en un estilo imperativo típico, con asignación y bucle. Escriba una función equivalente f-funcional que no use las características imperativas comience (secuenciación), mientras que (goto), y establezca (asignación). Puede usar tantas "funciones auxiliares" como desee, siempre que estén definidas utilizando let o letrec y no en el nivel superior.
Una solución:
; The idea is simple:
; Use parameter passing for binding the values
; of the variables and recursion instead of iteration.
;
; For those who like theory this is the main argument for proving
; that recursive functions (LISP, lambda calculus) have the same
; computational power as any imperative programming language.
(define f-functional (y)
(letrec (
(f-helper (lambda (x y)
(if (p x y)
(f-helper (g x y) y)
(h x y)))))
(f-helper e y)))
; Notice that y in f-helper is invariant. Therefore, we can rewrite
; f-helper without y as follows.
(define f-functional (y)
(letrec (
(f-helper (lambda (x)
(if (p x y)
(f-helper (g x y))
(h x y)))))
(f-helper e)))
; This is not the only solution, though I think it is one of the
; nicer ones.