Szukaj…
Wprowadzenie do foldów z garstką przykładów
Fałdy to funkcje (wyższego rzędu) używane z sekwencjami elementów. Zwijają one seq<'a> w 'b gdzie 'b jest dowolnym typem (prawdopodobnie nadal 'a ). To jest trochę abstrakcyjne, więc przejdźmy do konkretnych praktycznych przykładów.
Obliczanie sumy wszystkich liczb
W tym przykładzie 'a jest liczbą int . Mamy listę liczb i chcemy obliczyć sumę wszystkich jej liczb. Aby zsumować liczby na liście [1; 2; 3] piszemy
List.fold (fun x y -> x + y) 0 [1; 2; 3] // val it : int = 6
Pozwól mi wyjaśnić, ponieważ mamy do czynienia z listami, używamy fold w module List , stąd List.fold . pierwszym argumentem fold jest funkcja binarna, folder . Drugi argument to wartość początkowa . fold zaczyna składać listę, stosując kolejno funkcję foldera do elementów na liście, zaczynając od wartości początkowej i pierwszego elementu. Jeśli lista jest pusta, zwracana jest wartość początkowa!
Schematyczny przykład wykonania wygląda następująco:
let add x y = x + y // this is our folder (a binary function, takes two arguments)
List.fold add 0 [1; 2; 3;]
=> List.fold add (add 0 1) [2; 3]
// the binary function is passed again as the folder in the first argument
// the initial value is updated to add 0 1 = 1 in the second argument
// the tail of the list (all elements except the first one) is passed in the third argument
// it becomes this:
List.fold add 1 [2; 3]
// Repeat untill the list is empty -> then return the "inital" value
List.fold add (add 1 2) [3]
List.fold add 3 [3] // add 1 2 = 3
List.fold add (add 3 3) []
List.fold add 6 [] // the list is empty now -> return 6
6
Funkcja List.sum jest z grubsza List.fold add LanguagePrimitives.GenericZero gdzie ogólne zero powoduje, że jest on zgodny z liczbami całkowitymi, liczbami List.fold add LanguagePrimitives.GenericZero , dużymi liczbami całkowitymi itp.
Zliczanie elementów na liście ( count implementacyjne)
Odbywa się to prawie tak samo jak powyżej, ale ignorując rzeczywistą wartość elementu na liście i zamiast tego dodając 1.
List.fold (fun x y -> x + 1) 0 [1; 2; 3] // val it : int = 3
Można to również zrobić w następujący sposób:
[1; 2; 3]
|> List.map (fun x -> 1) // turn every elemet into 1, [1; 2; 3] becomes [1; 1; 1]
|> List.sum // sum [1; 1; 1] is 3
Możesz więc zdefiniować count w następujący sposób:
let count xs =
xs
|> List.map (fun x -> 1)
|> List.fold (+) 0 // or List.sum
Znajdowanie maksimum listy
Tym razem użyjemy List.reduce który jest podobny do List.fold ale bez wartości początkowej, jak w tym przypadku, gdy nie wiemy, jaki jest typ wartości, które zestawiamy:
let max x y = if x > y then x else y
// val max : x:'a -> y: 'a -> 'a when 'a : comparison, so only for types that we can compare
List.reduce max [1; 2; 3; 4; 5] // 5
List.reduce max ["a"; "b"; "c"] // "c", because "c" > "b" > "a"
List.reduce max [true; false] // true, because true > false
Znalezienie minimum listy
Podobnie jak przy wyszukiwaniu maksimum, folder jest inny
let min x y = if x < y then x else y
List.reduce min [1; 2; 3; 4; 5] // 1
List.reduce min ["a"; "b"; "c"] // "a"
List.reduce min [true; false] // false
Listy konkatenacyjne
Tutaj bierzemy listę list. Funkcją folderu jest operator @
// [1;2] @ [3; 4] = [1; 2; 3; 4]
let merge xs ys = xs @ ys
List.fold merge [] [[1;2;3]; [4;5;6]; [7;8;9]] // [1;2;3;4;5;6;7;8;9]
Lub możesz użyć operatorów binarnych jako funkcji folderu:
List.fold (@) [] [[1;2;3]; [4;5;6]; [7;8;9]] // [1;2;3;4;5;6;7;8;9]
List.fold (+) 0 [1; 2; 3] // 6
List.fold (||) false [true; false] // true, more on this below
List.fold (&&) true [true; false] // false, more on this below
// etc...
Obliczanie silni liczby
Taki sam pomysł jak przy sumowaniu liczb, ale teraz pomnożymy je. jeśli chcemy silnię n , mnożymy wszystkie elementy na liście [1 .. n] . Kod staje się:
// the folder
let times x y = x * y
let factorial n = List.fold times 1 [1 .. n]
// Or maybe for big integers
let factorial n = List.fold times 1I [1I .. n]
Wdrożenie forall exists i contains
funkcja forall sprawdza, czy wszystkie elementy w sekwencji spełniają warunek. exists sprawdza, czy przynajmniej jeden element na liście spełnia warunek. Najpierw musimy wiedzieć, jak zwinąć listę wartości bool . Używamy fałd oczywiście! operatory logiczne będą naszymi funkcjami folderów.
Aby sprawdzić, czy wszystkie elementy na liście są true , zwijamy je za pomocą funkcji && z wartością true jako wartością początkową.
List.fold (&&) true [true; true; true] // true
List.fold (&&) true [] // true, empty list -> return inital value
List.fold (&&) true [false; true] // false
Podobnie, aby sprawdzić, czy jeden element jest true na boolach list, zwijamy go za pomocą || operator z wartością false jako wartość początkową:
List.fold (||) false [true; false] // true
List.fold (||) false [false; false] // false, all are false, no element is true
List.fold (||) false [] // false, empty list -> return inital value
Powrót do forall i exists . Tutaj bierzemy listę dowolnego typu, używamy warunku do przekształcenia wszystkich elementów w wartości boolowskie, a następnie zwijamy go:
let forall condition elements =
elements
|> List.map condition // condition : 'a -> bool
|> List.fold (&&) true
let exists condition elements =
elements
|> List.map condition
|> List.fold (||) false
Aby sprawdzić, czy wszystkie elementy w [1; 2; 3; 4] są mniejsze niż 5:
forall (fun n -> n < 5) [1 .. 4] // true
zdefiniuj metodę contains z exists :
let contains x xs = exists (fun y -> y = x) xs
Lub nawet
let contains x xs = exists ((=) x) xs
Teraz sprawdź, czy lista [1 .. 5] zawiera wartość 2:
contains 2 [1..5] // true
Realizacja reverse :
let reverse xs = List.fold (fun acc x -> x :: acc) [] xs
reverse [1 .. 5] // [5; 4; 3; 2; 1]
Wdrażanie map i filter
let map f = List.fold (fun acc x -> List.append acc [f x]) List.empty
// map (fun x -> x * x) [1..5] -> [1; 4; 9; 16; 25]
let filter p = Seq.fold (fun acc x -> seq { yield! acc; if p(x) then yield x }) Seq.empty
// filter (fun x -> x % 2 = 0) [1..10] -> [2; 4; 6; 8; 10]
Czy jest coś fold nie może zrobić? Naprawdę nie wiem
Obliczanie sumy wszystkich elementów listy
Aby obliczyć sumę terminów (typu float, int lub big integer) z listy liczb, najlepiej jest użyć List.sum. W innych przypadkach List.fold jest funkcją, która najlepiej nadaje się do obliczenia takiej sumy.
- Suma liczb zespolonych
W tym przykładzie deklarujemy listę liczb zespolonych i obliczamy sumę wszystkich terminów na liście.
Na początku programu dodaj odwołanie do System.Numerics
otwórz System.Numerics
Aby obliczyć sumę, inicjalizujemy akumulator do liczby zespolonej 0.
let clist = [new Complex(1.0, 52.0); new Complex(2.0, -2.0); new Complex(0.0, 1.0)]
let sum = List.fold (+) (new Complex(0.0, 0.0)) clist
Wynik:
(3, 51)
- Suma liczb typu unii
Załóżmy, że lista składa się z liczb typu unii (liczba zmiennoprzecinkowa lub liczba całkowita) i chcesz obliczyć sumę tych liczb.
Zadeklaruj przed następującym typem numeru:
type number =
| Float of float
| Int of int
Oblicz sumę liczb typu numeru listy:
let list = [Float(1.3); Int(2); Float(10.2)]
let sum = List.fold (
fun acc elem ->
match elem with
| Float(elem) -> acc + elem
| Int(elem) -> acc + float(elem)
) 0.0 list
Wynik:
13.5
Pierwszy parametr funkcji, która reprezentuje akumulator, jest typu float, a drugi parametr, który reprezentuje pozycję na liście, ma numer typu. Ale zanim dodamy, musimy użyć dopasowania wzorca i rzutować, by wpisać float, gdy elem jest typu Int.