¿Diferencia entre plegar y reducir?

Intenté aprender F # pero me confundí al intentar distinguir entre plegar y reducir . Fold parece hacer lo mismo pero toma un parámetro adicional. ¿Existe una razón legítima para que existan estas dos funciones o están allí para dar cabida a personas de diferentes orígenes? (Por ejemplo: cadena y cadena 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])

Foldtoma un valor inicial explícito para el acumulador mientras reduceusa el primer elemento de la lista de entrada como valor inicial del acumulador.

Esto significa que el acumulador y, por lo tanto, el tipo de resultado deben coincidir con el tipo de elemento de la lista, mientras que pueden diferir foldporque 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, reducelanza una excepción en una lista de entrada vacía.

Además de lo que dijo Lee, puede definir reduceen 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 foldtome un valor inicial explícito para el acumulador también significa que el resultado de la foldfunción puede tener un tipo diferente al tipo de valores en la lista. Por ejemplo, puede usar un acumulador de tipo stringpara concatenar todos los números de 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, stringprimero tendría que convertir los números a y luego acumular:

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

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:

• Si bien reducefunciona solo con un tipo de elementos, los elementos de lista y acumulador foldpueden ser de diferentes tipos.

• Con reduce, aplicas una función fa cada elemento de la lista empezando por el primero:

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

  Con fold, se aplica fpartiendo del acumulador s:

  f (... (f s i0) i1 ...) iN.

Por lo tanto, reduceda como resultado una ArgumentExceptionlista vacía. Además, foldes más genérico que reduce; que puede utilizar foldpara implementar reducefácilmente.

En algunos casos, el uso reducees 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, foldes más potente con un acumulador de tipo arbitrario:

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

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

reducees solo un subconjunto de fold.

Definición de pliegue:

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 pliegue:

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