f# - Diferencia entre doblar y reducir?

functional-programming reduce

Question

Tratando de aprender F #, pero se confundió al tratar de distinguir entre fold y reduce . Fold parece hacer lo mismo pero toma un parámetro extra. ¿Existe una razón legítima para que estas dos funciones existan o están ahí para dar cabida a personas con diferentes antecedentes? (Por ejemplo: Cadena y cuerda en C #)

Aquí hay un fragmento de código copiado de la muestra:

let sumAList list =
    List.reduce (fun acc elem -> acc + elem) list

let sumAFoldingList list =
    List.fold (fun acc elem -> acc + elem) 0 list

printfn "Are these two the same? %A " 
             (sumAList [2; 4; 10] = sumAFoldingList [2; 4; 10])

Answer 1

Además de lo que dijo Lee, puede definir reduce en términos de fold , pero no (fácilmente) al revés:

let reduce f list = 
  match list with
  | head::tail -> List.fold f head tail
  | [] -> failwith "The list was empty!"

El hecho de que fold tome un valor inicial explícito para el acumulador también significa que el resultado de la función fold puede tener un tipo diferente al tipo de valores en la lista. Por ejemplo, puede usar el acumulador de tipo string para concatenar todos los números en una lista en una representación textual:

[1 .. 10] |> List.fold (fun str n -> str + "," + (string n)) ""

Cuando se usa reduce , el tipo de acumulador es el mismo que el tipo de valores en la lista; esto significa que si tiene una lista de números, el resultado tendrá que ser un número. Para implementar la muestra anterior, primero debe convertir los números a string y luego acumular:

[1 .. 10] |> List.map string
          |> List.reduce (fun s1 s2 -> s1 + "," + s2)

Answer 2

Veamos sus firmas:

> List.reduce;;
val it : ((''a -> ''a -> ''a) -> ''a list -> ''a) = <fun:clo@1>
> List.fold;;
val it : ((''a -> ''b -> ''a) -> ''a -> ''b list -> ''a) = <fun:clo@2-1>

Hay algunas diferencias importantes:

• Mientras que reduce funciona solo en un tipo de elementos, el acumulador y los elementos de lista en fold pueden ser de diferentes tipos.

• Con reduce , aplica una función f a cada elemento de la lista comenzando desde el primero:

  f (... (f i0 i1) i2 ...) iN .

  Con fold , aplica f comenzando desde el acumulador s :

  f (... (fs i0) i1 ...) iN .

Por lo tanto, reduce resultados en una ArgumentException en la lista vacía. Además, fold es más genérico que reduce ; puedes usar fold para implementar reduce fácilmente.

En algunos casos, usar reduce es más sucinto:

// Return the last element in the list
let last xs = List.reduce (fun _ x -> x) xs

o más conveniente si no hay ningún acumulador razonable:

// Intersect a list of sets altogether
let intersectMany xss = List.reduce (fun acc xs -> Set.intersect acc xs) xss

En general, fold es más potente con un acumulador de un tipo arbitrario:

// Reverse a list using an empty list as the accumulator
let rev xs = List.fold (fun acc x -> x::acc) [] xs

Answer 3

Fold toma un valor inicial explícito para el acumulador mientras que reduce usa el primer elemento de la lista de entrada como el valor inicial del acumulador.

Esto significa que el acumulador y, por lo tanto, el tipo de resultado debe coincidir con el tipo de elemento de lista, mientras que pueden diferir en fold ya que el acumulador se proporciona por separado. Esto se refleja en los tipos:

List.fold : (''State -> ''T -> ''State) -> ''State -> ''T list -> ''State
List.reduce : (''T -> ''T -> ''T) -> ''T list -> ''T

Además reduce throws una excepción en una lista de entrada vacía.

Answer 4

fold es una función mucho más valiosa que reduce . Puedes definir muchas funciones diferentes en términos de fold .

reduce es solo un subconjunto de fold .

Definición de fold:

let rec fold f v xs =
    match xs with 
    | [] -> v
    | (x::xs) -> f (x) (fold f v xs )

Ejemplos de funciones definidas en términos de fold:

let sum xs = fold (fun x y -> x + y) 0 xs

let product xs = fold (fun x y -> x * y) 1 xs

let length xs = fold (fun _ y -> 1 + y) 0 xs

let all p xs = fold (fun x y -> (p x) && y) true xs

let reverse xs = fold (fun x y -> y @ [x]) [] xs

let map f xs = fold (fun x y -> f x :: y) [] xs

let append xs ys = fold (fun x y -> x :: y) [] [xs;ys]

let any p xs = fold (fun x y -> (p x) || y) false xs 

let filter p xs = 
    let func x y =
        match (p x) with
        | true -> x::y
        | _ -> y
    fold func [] xs