Listan kokoaminen

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 29.5.2021 tarkistetusta versiosta . vahvistus vaatii 1 muokkauksen .

Ohjelmoinnissa luettelon taitto ( englanniksi  taitto , joka tunnetaan myös nimellä vähentää , akkumuloida )  on korkeamman asteen funktio , joka muuntaa tietorakenteen yhdeksi atomiarvoksi tiettyä funktiota käyttämällä. Taittotoimintoa käytetään usein toiminnallisessa ohjelmoinnissa listojen käsittelyssä . Taitto voidaan yleistää mielivaltaiseksi algebralliseksi tietotyypiksi käyttämällä katamorfismin [ käsitettä kategoriateoriasta .

Kokoonpanofunktiolla on yleensä kolme argumenttia: yhdistämisfunktio f, alkuarvo startja tietorakenne seq(luettelo yksinkertaisimmassa muodossaan). Yhdistelmäfunktion ominaisuuksista riippuen laskentaan voi olla erilaisia ​​toteutuksia ja erilaisia ​​strategioita . Joskus koontifunktio ei ota alkuarvoa, mutta vaatii ei-tyhjän luettelon; mutta monissa tapauksissa voi olla toivottavaa määrittää nollasta poikkeava alkuarvo, jota käytetään ensimmäisen kerran, kun yhdistämistoimintoa käytetään. Alkuarvon käyttö on tarpeen, kun yhdistämisfunktion tulostyyppi on eri kuin listaelementtien tyyppi, jolloin alkuarvon tulee olla samaa tyyppiä kuin tulostyyppi.

Assosiatiivisuus

Assosiatiivisella taitolla laskentajärjestys ei vaikuta tulokseen, esimerkiksi listan numeroiden summan laskeminen (1 2 3 4 5), eli sen taittaminen summalla, voidaan tehdä missä tahansa järjestyksessä: tai tai , joka mahdollistaa voit laskea listan eri osien taittamisen samanaikaisesti, eli rinnakkaista laskentalistan taittamisen moniprosessori- ja klusterijärjestelmissä.

Ei-assosiatiivisissa operaatioissa järjestyksellä on väliä, joten yleensä taittoa varten on määritettävä laskelmien järjestys, tämän yhteydessä oikeanpuoleinen taitto ( oikea- assosiatiivinen ) ja vasen taitto ( vasen -assosiatiivinen ) erotetaan. Esimerkiksi luettelossa seq := (elem_1 elem_2 ... elem_n)vasen assosiatiivinen taittofunktio arvioi lausekkeen arvon:

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

ja oikea assosiaatio:

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

Esimerkkejä

Tekijäluku n voidaan esittää lukujen luettelona 2 :sta n : ään taitettuna kertolaskuoperaatiolla (esimerkiksi Haskell-kielellä ):

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

Tässä:

fac - tekijäfunktion ilmoitus
n - syöttöparametri
merkin =(yhtä) jälkeen tulee funktion määritelmä
foldl - konvoluutiofunktio
1 — konvoluution alkuarvo
[2..n] - on määritetty luettelo, jonka mukaan taitettava - numerot 2 :sta n :ään

Esimerkki samanlaisesta toiminnosta Scalassa :

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

Kirjallisuus