Sök…
Introduktion till veck, med en handfull exempel
Vikningar är (högre ordning) funktioner som används med sekvenser av element. De kollapsar seq<'a> till 'b där 'b är vilken typ som helst (kanske fortfarande 'a ). Det här är lite abstrakt så att vi får konkreta praktiska exempel.
Beräkna summan av alla siffror
I detta exempel är 'a ett int . Vi har en lista med siffror och vi vill beräkna summan av alla nummer. För att summera listans siffror [1; 2; 3] vi skriver
List.fold (fun x y -> x + y) 0 [1; 2; 3] // val it : int = 6
Låt mig förklara, eftersom vi har att göra med listor, använder vi fold i List modulen därmed List.fold . det första argumentet fold krävs är en binär funktion, mappen. Det andra argumentet är initialvärdet . fold börjar vika listan genom att konsekvent tillämpa mappfunktionen på element i listan som börjar med det initiala värdet och det första elementet. Om listan är tom returneras initalsvärdet!
Schematisk översikt över ett exekveringsexempel ser så här ut:
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
Funktionen List.sum är ungefär List.fold add LanguagePrimitives.GenericZero där den generiska nollan gör den kompatibel med heltal, flottörer, stora heltal etc.
Räkna elemet i en lista (genomförande count )
Detta görs nästan samma sak som ovan, men genom att ignorera det faktiska värdet på elementet i listan och istället lägga till 1.
List.fold (fun x y -> x + 1) 0 [1; 2; 3] // val it : int = 3
Detta kan också göras så här:
[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
Så du kan definiera count sätt:
let count xs =
xs
|> List.map (fun x -> 1)
|> List.fold (+) 0 // or List.sum
Hitta maxlistan
Den här gången kommer vi att använda List.reduce som är som List.fold men utan ett initialt värde som i det här fallet där vi inte vet vad typen är av de värden vi jämför med:
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
Hitta minsta lista
Precis som när du hittar max, är mappen annorlunda
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
Slå samman listor
Här tar vi en lista med listor Mappfunktionen är operatören @
// [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]
Eller så kan du använda binära operatörer som din mappfunktion:
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...
Beräkning av faktorn för ett nummer
Samma idé som när vi summerar siffrorna, men nu multiplicerar vi dem. om vi vill ha fabriken om n multiplicerar vi alla element i listan [1 .. n] . Koden blir:
// 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]
Implementering för forall , exists och contains
funktionen forall kontrollerar om alla element i en sekvens uppfyller ett villkor. exists kontrollerar om minst ett element i listan uppfyller villkoret. Först måste vi veta hur man kollapsar en lista med bool . Vi använder naturligtvis veck! booleska operatörer är våra mappfunktioner.
För att kontrollera om alla element i en lista är true kollapsar vi dem med && funktionen med true som initialvärde.
List.fold (&&) true [true; true; true] // true
List.fold (&&) true [] // true, empty list -> return inital value
List.fold (&&) true [false; true] // false
På samma sätt, för att kontrollera om ett element är true i en lista booleaner, kollapsar vi det med || operatör med false som initialvärde:
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
Tillbaka till forall och exists . Här tar vi en lista över vilken typ som helst, använder villkoret för att omvandla alla element till booleska värden och sedan kollapsar vi den ned:
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
För att kontrollera om alla element i [1; 2; 3; 4] är mindre än 5:
forall (fun n -> n < 5) [1 .. 4] // true
definiera contains metoden med exists :
let contains x xs = exists (fun y -> y = x) xs
Eller ens
let contains x xs = exists ((=) x) xs
Kontrollera nu om listan [1 .. 5] innehåller värdet 2:
contains 2 [1..5] // true
Genomförande reverse :
let reverse xs = List.fold (fun acc x -> x :: acc) [] xs
reverse [1 .. 5] // [5; 4; 3; 2; 1]
Implementera map och 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]
Finns det något fold inte kan göra? Jag vet inte riktigt
Beräkna summan av alla element i en lista
För att beräkna summan av termer (av typen flyta, int eller stort heltal) i en siffrelista är det att föredra att använda List.sum I andra fall är List.fold den funktion som är bäst lämpad för att beräkna en sådan summa.
- Summan av komplexa siffror
I det här exemplet förklarar vi en lista med komplexa siffror och vi beräknar summan av alla termer i listan.
Lägg till en referens till System.Numerics i början av programmet
öppna System.Numerics
För att beräkna summan initialiserar vi ackumulatorn till komplexet nummer 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
Resultat:
(3, 51)
- Summan av antalet unionstyp
Anta att en lista består av siffror av unionstyp (float eller int) och vill beräkna summan av dessa nummer.
Förklara före följande nummertyp:
type number =
| Float of float
| Int of int
Beräkna summan av numren av typnumret i en lista:
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
Resultat:
13.5
Den första parametern för funktionen, som representerar ackumulatorn, är av typen float och den andra parametern, som representerar ett objekt i listan är av typnummer. Men innan vi lägger till måste vi använda ett mönstermatchning och gjuta för att skriva float när elem är av typ Int.
