Listsammanställning

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 29 maj 2021; verifiering kräver 1 redigering .

Listfoldning ( engelsk  foldning , även känd som reducera , ackumulera ) i programmering  är en högre ordningsfunktion som omvandlar en datastruktur till ett enda atomvärde med hjälp av en given funktion. Vikningsoperationen används ofta i funktionell programmering vid bearbetning av listor . Vikning kan generaliseras till en godtycklig algebraisk datatyp genom att använda begreppet katamorfism från kategoriteorin .

En samlad funktion tar vanligtvis tre argument: en kombinerande funktion f, ett initialt värde startoch en datastruktur seq(en lista i sin enklaste form). Beroende på egenskaperna för kombinationsfunktionen kan det finnas olika implementeringar och olika strategier för att beräkna . Ibland tar inte rollup-funktionen ett initialt värde, utan kräver en icke-tom lista; men i många fall kan det vara önskvärt att ange ett initialt värde som inte är noll, vilket kommer att användas första gången kombinationsfunktionen tillämpas. Användningen av ett initialvärde är nödvändigt när resultattypen för den kombinerande funktionen skiljer sig från typen av listelement, i vilket fall det initiala värdet måste vara av samma typ som resultattypen.

Associativitet

För vikning med en associativ operation påverkar beräkningsordningen inte resultatet, t.ex. beräkning av summan av listans nummer (1 2 3 4 5), det vill säga dess vikning med summan, kan göras i valfri ordning: eller eller , vilket tillåter du att beräkna vikningen av olika delar av listan samtidigt, det vill säga att parallellisera beräkningslistvikningen i multiprocessor- och klustersystem.

För icke-associativa operationer är ordningen avgörande, därför, i det allmänna fallet, för vikning, krävs det att ange ordningen för beräkningar, i samband med detta, högervikning ( högerassociativ ) och vänstervikning ( vänster -associativ ) särskiljs. Till exempel, för en lista seq := (elem_1 elem_2 ... elem_n), kommer den vänstra associativa vikfunktionen att utvärdera värdet på uttrycket:

(f ... (f (f start elem_1) elem_2) ... elem_n)

och rätt associativ:

(f elem_1 (f elem_2 ... (f elem_n start) ... )).

Exempel

Faktorial n kan representeras som en lista med tal från 2 till n vikta med hjälp av multiplikationsoperationen (till exempel på Haskell-språket ):

fac n = vikl ( * ) 1 [ 2 .. n ]

Här:

fac - deklaration av den faktoriella funktionen
n - ingångsparameter
efter tecknet =(lika) kommer definitionen av funktionen
foldl - faltningsfunktion
1 — initialt värde för faltning
[2..n] - en lista anges för att vika - nummer från 2 till n

Ett exempel på en liknande funktion i Scala :

def fac ( n : BigInt ) = ( BigInt ( 2 ) till n ). foldLeft ( BigInt ( 1 ))( _ * _ )

Litteratur