Zoeken…
Inleiding tot vouwen, met een handvol voorbeelden
Vouwen zijn (hogere volgorde) functies die worden gebruikt met reeksen elementen. Ze vouwen seq<'a> in 'b waarbij 'b elk type is (mogelijk nog 'a ). Dit is een beetje abstract, dus laten we in concrete praktische voorbeelden komen.
De som van alle getallen berekenen
In dit voorbeeld is 'a een int . We hebben een lijst met getallen en we willen alle getallen optellen. Om de nummers van de lijst op te tellen [1; 2; 3] we schrijven
List.fold (fun x y -> x + y) 0 [1; 2; 3] // val it : int = 6
Laat het me uitleggen, omdat we te maken hebben met lijsten, gebruiken we fold in de List module, vandaar List.fold . het eerste argument dat fold is een binaire functie, de map . Het tweede argument is de beginwaarde . fold begint met het vouwen van de lijst door de mapfunctie opeenvolgend toe te passen op elementen in de lijst die beginnen met de beginwaarde en het eerste element. Als de lijst leeg is, wordt de beginwaarde geretourneerd!
Schematisch overzicht van een uitvoeringsvoorbeeld ziet er als volgt uit:
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
De functie List.sum is grofweg List.fold add LanguagePrimitives.GenericZero waarbij de generieke nul het compatibel maakt met gehele getallen, drijvers, grote gehele getallen enz.
Elemets in een lijst count ( count )
Dit gebeurt bijna hetzelfde als hierboven, maar door de werkelijke waarde van het element in de lijst te negeren en in plaats daarvan 1 toe te voegen.
List.fold (fun x y -> x + 1) 0 [1; 2; 3] // val it : int = 3
Dit kan ook als volgt worden gedaan:
[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
Dus je zou het count als volgt kunnen definiëren:
let count xs =
xs
|> List.map (fun x -> 1)
|> List.fold (+) 0 // or List.sum
Het maximum van de lijst vinden
Deze keer gebruiken we List.reduce die lijkt op List.fold maar zonder een beginwaarde, zoals in dit geval waarin we niet weten wat het type is van de waarden die we vergelijken:
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
Het minimum van een lijst vinden
Net zoals bij het vinden van het maximum, is de map anders
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
Lijsten samenvoegen
Hier nemen we een lijst met lijsten. De mapfunctie is de 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]
Of u kunt binaire operatoren gebruiken als uw mapfunctie:
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...
De faculteit van een getal berekenen
Hetzelfde idee als bij het optellen van de getallen, maar nu vermenigvuldigen we ze. als we de faculteit van n willen, vermenigvuldigen we alle elementen in de lijst [1 .. n] . Code wordt:
// 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]
forall , exists en contains
de functie forall controleert of alle elementen in een reeks aan een voorwaarde voldoen. exists controleert of ten minste één element in de lijst aan de voorwaarde voldoet. Eerst moeten we weten hoe we een lijst met bool waarden kunnen samenvouwen. Nou, we gebruiken natuurlijk vouwen! Booleaanse operatoren zullen onze mapfuncties zijn.
Om te controleren of alle elementen in een lijst true , vouwen we ze samen met de functie && met true als beginwaarde.
List.fold (&&) true [true; true; true] // true
List.fold (&&) true [] // true, empty list -> return inital value
List.fold (&&) true [false; true] // false
Evenzo, om te controleren of een element true in een lijst Booleans, vouwen we het samen met de || operator met false als beginwaarde:
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
Terug naar forall en exists . Hier nemen we een lijst van elk type, gebruiken we de voorwaarde om alle elementen om te zetten in Booleaanse waarden en vouwen we deze samen:
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
Om te controleren of alle elementen in [1; 2; 3; 4] zijn kleiner dan 5:
forall (fun n -> n < 5) [1 .. 4] // true
definieer de methode contains met exists :
let contains x xs = exists (fun y -> y = x) xs
Of zelfs
let contains x xs = exists ((=) x) xs
Controleer nu of de lijst [1 .. 5] de waarde 2 bevat:
contains 2 [1..5] // true
reverse implementeren:
let reverse xs = List.fold (fun acc x -> x :: acc) [] xs
reverse [1 .. 5] // [5; 4; 3; 2; 1]
map en filter implementeren
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]
Is er iets dat fold niet kan doen? Ik weet het niet echt
De som van alle elementen van een lijst berekenen
Om de som van termen (van het type float, int of groot geheel getal) van een nummerlijst te berekenen, verdient het de voorkeur om List.sum te gebruiken. In andere gevallen is List.fold de functie die het meest geschikt is om een dergelijke som te berekenen.
- Som van complexe getallen
In dit voorbeeld declareren we een lijst met complexe getallen en berekenen we de som van alle termen in de lijst.
Voeg aan het begin van het programma een verwijzing naar System.Numerics toe
open System.Numerics
Om de som te berekenen, initialiseren we de accumulator op het complexe getal 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
Resultaat:
(3, 51)
- Som van aantallen van unietype
Stel dat een lijst bestaat uit getallen van het type unie (float of int) en de som van deze getallen wilt berekenen.
Verklaar vóór het volgende nummertype:
type number =
| Float of float
| Int of int
Bereken de som van getallen van typenummer van een lijst:
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
Resultaat:
13.5
De eerste parameter van de functie, die de accumulator vertegenwoordigt, is van het type float en de tweede parameter, die een item in de lijst vertegenwoordigt, is van het typenummer. Maar voordat we toevoegen, moeten we een patroonovereenkomst gebruiken en casten om float te typen wanneer elem van het type Int is.
