Lista de fragmentos de código funcionales para programadores de procedimientos?

Question

A veces sigo atascado tratando de traducir código de procedimiento en código funcional.

¿Hay una lista de modismos/frases funcionales que se asignan a modismos/fragmentos de procedimientos?

Editar

Dado que no parece ser un sitio web centralizado de estos fragmentos, estoy convirtiendo esto en un wiki de la comunidad. Pegue aquí cualquier fragmento de procedimiento -> funcional.

Answer 1

(Editado de this post en fshub)

La primera vez que fui a alcanzar para pausa/continuar en OCaml/F #, me lanzó para un (infinita) loop, por así decirlo, ¡porque no existe tal cosa! En OCaml, se pueden usar excepciones para romper un bucle porque son muy barato, pero en F # (pulg.NET) la sobrecarga es bastante alta y no es útil para el control de flujo "normal".

Esto apareció cuando se jugaba con algoritmos de ordenación un tiempo atrás (para matar el tiempo), que hace un uso intensivo de repetir/hasta y romper. Me llamó la atención que las funciones de llamada de cola recursivas pueden lograr exactamente el mismo resultado, con solo un ligero toque de legibilidad. Entonces, lancé 'mutable bDone' y 'while not bDone' e intenté escribir el código sin estos constructos imperativos. Lo siguiente destila solo las partes en bucle y muestra cómo escribir repetir/hasta, do/while, while/do, break/continue, y test-in-the-middle código de estilo usando tailcalls. Todo esto parece ejecutarse exactamente a la misma velocidad que una instrucción tradicional F # 'while', pero su kilometraje puede variar (algunas plataformas pueden no implementar correctamente tailcall y, por lo tanto, pueden acumular fallas hasta que se remenquen). Al final hay un algoritmo de clasificación (malo) escrito en ambos estilos, para comparar.

Comencemos con un ciclo 'do/while', escrito en estilo imperativo F # tradicional, luego observemos variaciones funcionales que proporcionan el mismo tipo de bucle, así como semánticas diferentes como while/do, repeat/until, prueba 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 (do/while).

Aquí está el mismo código, pero en un estilo funcional. Tenga en cuenta que no necesitamos declarar un mutable aquí.

let funDoWhile() = 
    let rec loop x = 
     f()    (*Do*) 
     if x < N then (*While*) 
      loop (x+1) 
    loop 0 

Nos puede girar que a un do tradicional/mientras 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é le parece repetir un bloque hasta que alguna condición sea verdadera (repetir/hasta)? Lo 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 un descanso de mónada? Bueno, solo introduce una expresión condicional que devuelve '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 solo otra llamada a loop! En primer lugar, con una muleta 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, de nuevo sin el (feo) muleta sintaxis:

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() 

fácil como pastel!

Un buen resultado de estas formas de bucle es que facilita la detección e implementación de estados en sus bucles. Por ejemplo, un tipo de burbuja continuamente realiza un bucle en 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, entonces cada valor debe estar en el lugar correcto, por lo que el género puede finalizar. Como optimización, en cada pasada a través de la matriz, el último valor de la matriz termina ordenado en el lugar correcto. Por lo tanto, el ciclo se puede acortar en uno cada vez. La mayoría de los algoritmos buscan 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á establecido en verdadero!

Aquí está el código F # que implementa un tipo de burbuja (sí, el tipo de burbuja es un algoritmo terrible; las rocas de quicksort). Al final es una implementación imperativa que no cambia el estado; actualiza el indicador bModified para cada intercambio.Curiosamente, la solución imperativa es más rápida en arreglos pequeños y solo un uno o dos por ciento más lenta en los 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 

Answer 2

Oh, ahora esta es una pregunta ingeniosa. Éstos son algunos, code snips in python o algo cloe:

• para los bucles pueden ser sustituidos por los iteradores

  stripped_list = [line.strip() for line in line_list]

• para los bucles se pueden sustituir por aplicar o mapa o filtrar

  mapa (superior, ['oración', 'fragmento']) [ 'frase', 'fragmento']

• anidado para bucles con composición de funciones

• cola de recursión en lugar de bucles

• expresiones de generadores en lugar de para bucles

  sum(x*x for x in range(10))

Answer 3

vieja pregunta tareas:

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))) 

está en un estilo típico imprescindible, con misiones y bucle. Escriba una función equivalente f-funcional que no utilice las funciones imperativas begin (sequencing), while (goto) y set (assignment). Puede usar tantas `` funciones auxiliares '' como quiera, siempre que se definan usando 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. 

Answer 4

El doblez 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ía una variable de acumulador y la establecería en 0, luego iteraría por la lista e incrementaría el acumulador por el artículo.

En Ocaml, que realizan la misma acción de una manera funcional mediante el uso de pliegue:

List.fold_left (+) 0 [1; 2; 3];; 
- : int = 6 

Usando veces, puede, por ejemplo, contar el número de palabras en la lista y concatenar 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 doblez es copiar un vector en un conjunto. Como los conjuntos en Ocaml son inmutables, efectivamente necesita 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 objetivo inicial es un conjunto vacío, y en cada llamada, se crea un nuevo conjunto, basado en la serie anterior y el elemento actual utilizando IntSet.add.

Implemente doblar recursivamente usted mismo una vez, para saber cómo se hace debajo del capó, luego use la versión incorporada en todas partes. ¡Incluso en C++, con std::accumulate!

Answer 5

El proyecto PLEAC tiene casi exactamente esta como su objetivo: implementar todos los ejemplos en el libro de cocina 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