Liste oprulning

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 29. maj 2021; verifikation kræver 1 redigering .

Listefoldning ( engelsk folding , også kendt som reducere , akkumulere ) i programmering er en højere-ordens funktion , der konverterer en datastruktur til en enkelt atomværdi ved hjælp af en given funktion. Foldeoperationen bruges ofte i funktionel programmering ved behandling af lister . Folding kan generaliseres til en vilkårlig algebraisk datatype ved at bruge begrebet catamorphism fra kategoriteori .

En opsamlingsfunktion tager normalt tre argumenter: en kombinerende funktion f, en begyndelsesværdi startog en datastruktur seq(en liste i sin enkleste form). Afhængigt af egenskaberne for kombinationsfunktionen kan der være forskellige implementeringer og forskellige strategier til beregning af . Nogle gange tager rollup-funktionen ikke en startværdi, men kræver en ikke-tom liste; men i mange tilfælde kan det være ønskeligt at angive en begyndelsesværdi, der ikke er nul, og som vil blive brugt første gang, kombinationsfunktionen anvendes. Brugen af en startværdi er nødvendig, når resultattypen for kombinationsfunktionen er forskellig fra typen af listeelementer, i hvilket tilfælde startværdien skal være af samme type som resultattypen.

Associativitet

For foldning ved en associativ operation påvirker beregningsrækkefølgen ikke resultatet, for eksempel beregning af summen af listens numre (1 2 3 4 5), dvs. dens foldning med summen, kan udføres i enhver rækkefølge: eller eller , som tillader dig til at beregne foldningen af forskellige dele af listen på samme tid, det vil sige at parallelisere beregningslistefoldningen i multiprocessor- og klyngesystemer. $1+(2+(3+(4+(5+0))))$ $((((0+1)+2)+3)+4)+5$ $0+(1+2)+((3+4)+5)$

For ikke-associative operationer har rækkefølgen betydning, derfor, i det generelle tilfælde, for foldning, er det påkrævet at specificere rækkefølgen af beregninger, i forbindelse med dette, højrehåndsfoldning ( højre- associativ ) og venstrehåndsfoldning ( venstre -associative ) skelnes. For en liste seq := (elem_1 elem_2 ... elem_n)vil den venstre associative foldfunktion f.eks. evaluere værdien af udtrykket:

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

og ret associativ:

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

Eksempler

Faktorialet n kan repræsenteres som en liste over tal fra 2 til n foldet ved hjælp af multiplikationsoperationen (for eksempel på Haskell-sprog ):

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

Her:

fac - erklæring om den faktorielle funktion
n - input parameter
efter tegnet =(lig) kommer definitionen af funktionen
foldl - foldningsfunktion
1 — begyndelsesværdi for foldning
[2..n] - der er angivet en liste, som skal foldes - tal fra 2 til n

Et eksempel på en lignende funktion i Scala :

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

Litteratur

Fugl, Richard. Perler af funktionelt algoritmedesign . - Cambrigde : University Press , 2010. - 277 s. - ISBN 978-0-521-51338-8 .
Bird R. Pearls of Functional Algorithm Design. - DMK Press , 2013. - 330 s. - ISBN 978-5-94074-867-0 . (utilgængeligt link)
Hutton, Graham. En tutorial om universalitet og udtryksfuldhed ved fold // Journal of Functional Programming . — Bd. 9 , nr. 4 . — S. 355–372 . — ISSN 0956-7968 .