Katlama ve farkı azaltma?

Question

F # öğrenmek çalışıyorum ama fold ve reduce ayırt çalışırken karıştı. Fold, same thing yapılıyor gibi görünüyor, ancak fazladan bir parametre alıyor. Bu iki fonksiyonun var olmasının meşru bir sebebi var mı yoksa farklı geçmişlere sahip insanlar mı var? (Örnek: C# dizisi ve dizi) Burada

kod parçacığını örneği kopyalanır:

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 akümülatör için açık bir başlangıç ​​değerini alır reduce ilk olarak giriş listesinin birinci elemanı kullanır iken akümülatör değeri.

Bu akümülatörü anlamına gelir ve bu nedenle, akümülatör ayrıca sağlanır onlar fold farklı olabilir, oysa türü, liste eleman türü ile eşleşmelidir sonuçlanır. Bu tipler, yansımaktadır: Ayrıca reduce olarak

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

boş giriş listesindeki bir durum atar. Lee söylediklerine ek olarak

Answer 2

, sen tersidir (kolayca) fold açısından reduce tanımlamak, ancak edemez:

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

fold da akümülatör için açık bir başlangıç ​​değerini alır gerçeği fold işlevinin sonucunun listedeki değerlerin türünden farklı olabileceği anlamına gelir. Örneğin, bir metinsel gösterimi içine listedeki tüm numaraları bitiştirmek için tip string arasında akümülatörü kullanabilirsiniz:

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

reduce kullanarak, akümülatör tipi listesinde değerlerin türü aynıdır - Bu bir sayı listeniz varsa, sonucun bir sayı olması gerektiği anlamına gelir. Bir önceki örneği uygulamak için, daha sonra string birinci ve numaralar dönüştürmek zorundayız birikir:

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

Answer 3

en imzalarında bakalım:

: bazı önemli farklılıklar vardır

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

• unsurlarından biri türüne reduce eserler sadece fold yılında akümülatör ve liste elemanları farklı tipte olabilir iken.

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

• reduce ile, ilki başlayarak her liste öğesine bir işlev f geçerlidir. fold ile

  , biriktiricide s başlayarak f geçerlidir:

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

nedenle, boş listede bir ArgumentException içinde reduce sonuçlanır. Ayrıca, fold, reduce'dan daha geniştir; reduce'u kolayca uygulamak için fold'u kullanabilirsiniz. reduce kullanarak bazı durumlarda

, daha özlü olduğu:

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

veya herhangi makul akümülatör orada değilse daha uygun: Genel olarak

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

, fold bir an akümülatör ile daha güçlü isteğe bağlı tür:

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

Answer 4

fold, reduce'dan çok daha değerli bir işlevdir. Birçok farklı işlevi fold olarak tanımlayabilirsiniz.

reduce sadece fold alt grubudur. kıvrımın

Tanım: katlık açısından tanımlanan fonksiyonların

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

Örnekler:

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