Perbedaan antara Lipat dan Reduksi?

121

Mencoba mempelajari F # tetapi bingung ketika mencoba membedakan antara lipat dan kurangi . Lipat tampaknya melakukan hal yang sama tetapi membutuhkan parameter tambahan. Adakah alasan yang sah mengapa kedua fungsi ini ada atau ada untuk mengakomodasi orang-orang dengan latar belakang yang berbeda? (Misalnya: String dan string di C #)

Berikut cuplikan kode yang disalin dari contoh:

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])
Wallace
sumber
1
Anda dapat menulis mengurangi dan melipat satu sama lain, misalnya fold f a ldapat ditulis sebagai reduce f a::l.
Neil
9
@Neil - Menerapkan folddalam istilah reducelebih rumit dari itu - jenis akumulator foldtidak harus sama dengan jenis benda dalam daftar!
Tomas Petricek
@TomasPetricek Kesalahan saya, awalnya saya bermaksud untuk menulis sebaliknya.
Neil

Jawaban:

171

Foldmengambil nilai awal eksplisit untuk akumulator sementara reducemenggunakan elemen pertama dari daftar input sebagai nilai akumulator awal.

Artinya, akumulator dan oleh karena itu jenis hasil harus cocok dengan jenis elemen daftar, sedangkan foldakumulator dapat berbeda karena akumulator disediakan secara terpisah. Ini tercermin dalam jenis:

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

Selain reducemelontarkan pengecualian pada daftar masukan kosong.

Lee
sumber
Jadi pada dasarnya daripada melakukan fold, Anda cukup menambahkan nilai awal itu ke awal daftar dan lakukan reduce? Lalu apa gunanya fold?
Pacerier
2
@Pacerier - Fungsi akumulator untuk lipatan memiliki jenis yang berbeda: 'state -> 'a -> 'stateuntuk lipatan vs 'a -> 'a -> 'auntuk mengurangi, jadi pengurangan membatasi jenis hasil agar sama dengan jenis elemen. Lihat jawaban Tomas Petricek di bawah ini.
Lee
178

Selain apa yang Lee katakan, Anda dapat mendefinisikan reducedalam istilah fold, tetapi tidak (dengan mudah) sebaliknya:

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

Fakta yang foldmengambil nilai awal eksplisit untuk akumulator juga berarti bahwa hasil dari foldfungsi dapat memiliki tipe yang berbeda dari tipe nilai dalam daftar. Misalnya, Anda dapat menggunakan akumulator tipe stringuntuk menggabungkan semua angka dalam daftar menjadi representasi tekstual:

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

Saat menggunakan reduce, jenis akumulator sama dengan jenis nilai dalam daftar - ini berarti bahwa jika Anda memiliki daftar angka, hasilnya harus berupa angka. Untuk menerapkan contoh sebelumnya, Anda harus mengonversi angkanya menjadi yang stringpertama lalu mengakumulasikan:

[1 .. 10] |> List.map string
          |> List.reduce (fun s1 s2 -> s1 + "," + s2)
Tomas Petricek
sumber
2
Mengapa mendefinisikan pengurangan sedemikian rupa sehingga dapat membuat kesalahan saat runtime?
Fresheyeball
1 untuk catatan tentang keumuman fold' & its ability to express pengurangan '. Beberapa bahasa memiliki konsep chirality struktural (Haskell, saya sedang melihat Anda), Anda dapat melipat ke kiri atau ke kanan yang digambarkan secara visual di wiki ini ( en.wikipedia.org/wiki/Fold_%28higher-order_function ). Dengan konstruksi identitas, dua operator FP 'fundamental' lainnya (filter dan fmap) juga dapat diimplementasikan dengan konstruksi bahasa kelas satu `lipat 'yang ada (semuanya adalah konstruksi isomorfik). ( cs.nott.ac.uk/~pszgmh/fold.pdf ) Lihat: HoTT, Princeton (Bagian komentar ini terlalu kecil untuk diisi ..)
Andrew
Karena penasaran .. apakah ini akan membuat kinerja mengurangi lebih cepat daripada melipat karena kurang asumsi tentang jenis dan pengecualian?
sksallaj
19

Mari kita lihat tanda tangan mereka:

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

Ada beberapa perbedaan penting:

  • Saat reducebekerja pada satu jenis elemen saja, elemen akumulator dan list di folddapat memiliki tipe yang berbeda.
  • Dengan reduce, Anda menerapkan fungsi fke setiap elemen daftar mulai dari yang pertama:

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

    Dengan fold, Anda melamar fmulai dari akumulator s:

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

Oleh karena itu, reducemenghasilkan ArgumentExceptiondaftar kosong. Selain itu, foldlebih umum dari reduce; dapat Anda gunakan folduntuk menerapkan reducedengan mudah.

Dalam beberapa kasus, penggunaan reducelebih ringkas:

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

atau lebih nyaman jika tidak ada akumulator yang masuk akal:

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

Secara umum, foldlebih kuat dengan akumulator tipe arbitrer:

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

foldadalah fungsi yang jauh lebih berharga daripada reduce. Anda dapat mendefinisikan berbagai fungsi dalam istilah fold.

reducehanyalah sebagian dari fold.

Definisi lipatan:

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

Contoh fungsi yang didefinisikan dalam istilah lipatan:

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
Raz Megrelidze
sumber
1
Anda mendefinisikan Anda foldberbeda dari List.foldsebagai jenis List.foldyaitu ('a -> 'b -> 'a) -> 'a -> 'b list -> 'akasus, tetapi dalam Anda ('a -> 'b -> 'b) -> 'b -> 'a list -> 'b. Hanya untuk membuatnya eksplisit. Selain itu, penerapan append Anda salah. Ini akan berfungsi jika Anda menambahkan pengikatan padanya, misalnya List.collect id (fold (fun x y -> x :: y) [] [xs;ys]), atau mengganti kontra dengan operator tambahan. Jadi, append bukanlah contoh terbaik dalam daftar ini.
jpe