Sự khác biệt giữa gấp và giảm?

Question

Đang cố gắng tìm hiểu F # nhưng bị nhầm lẫn khi cố gắng phân biệt giữa fold và reduce. Gấp dường như thực hiện same thing nhưng có thêm tham số. Có một lý do chính đáng nào cho hai chức năng này để tồn tại hay chúng ở đó để thích ứng với những người có nguồn gốc khác nhau? (Ví dụ: String và chuỗi trong C#)

Dưới đây là đoạn mã sao chép từ mẫu:

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

Fold mất một giá trị ban đầu rõ ràng cho accumulator khi reduce sử dụng phần tử đầu tiên của danh sách đầu vào như ban đầu giá trị tích lũy.

Điều này có nghĩa là bộ tích lũy và do đó loại kết quả phải khớp với loại phần tử danh sách, trong khi chúng có thể khác nhau trong fold khi bộ tích lũy được cung cấp riêng. Điều này được phản ánh trong các loại:

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

Ngoài ra reduce ném ngoại lệ vào danh sách đầu vào trống.

Answer 2

Ngoài những gì Lee nói, bạn có thể xác định reduce về fold, nhưng không (dễ dàng) theo chiều ngược lại:

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

Thực tế là fold mất một giá trị ban đầu rõ ràng cho accumulator cũng có nghĩa là kết quả của hàm fold có thể có một loại khác với loại giá trị trong danh sách. Ví dụ, bạn có thể sử dụng ắc quy loại string để nối tất cả các số trong danh sách thành một đại diện văn bản:

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

Khi sử dụng reduce, loại ắc cũng giống như các loại của các giá trị trong danh sách - đây có nghĩa là nếu bạn có một danh sách các số, kết quả sẽ phải là một số. Để thực hiện các mẫu trước đó, bạn sẽ phải chuyển đổi các con số để string đầu tiên và sau đó tích lũy:

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

Answer 3

Hãy nhìn vào chữ ký của họ:

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

Có một số khác biệt quan trọng:

• Trong khi reduce chỉ hoạt động trên một loại yếu tố, phần tử tích lũy và danh sách trong fold có thể ở các loại khác nhau.

• Với reduce, bạn áp dụng một hàm f để mọi phần tử danh sách bắt đầu từ cái đầu tiên:

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

  Với fold, bạn áp dụng f bắt đầu từ ắc s:

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

Vì vậy, reduce dẫn đến ArgumentException trong danh sách trống. Hơn nữa, fold là tổng quát hơn reduce; bạn có thể sử dụng fold để thực hiện dễ dàng reduce.

Trong một số trường hợp, sử dụng reduce là gọn gàng hơn:

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

hoặc thuận tiện hơn nếu không có bất kỳ ắc hợp lý:

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

Nói chung, fold mạnh mẽ hơn với một ắc của một loại tùy ý:

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

Answer 4

fold là hàm có giá trị hơn nhiều so với reduce. Bạn có thể xác định nhiều hàm khác nhau theo số fold.

reduce chỉ là một tập con của fold.

Định nghĩa về chuồng:

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

Ví dụ về các chức năng được xác định về mặt gấp:

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