Personal tools

Ce se intelege prin fold ?

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
m
Line 3: Line 3:
 
Stim cu totii ca prelucrarea unei liste se poate face adesea dupa o schema recursiva. Aceasta schema depinde de doua lucruri:
 
Stim cu totii ca prelucrarea unei liste se poate face adesea dupa o schema recursiva. Aceasta schema depinde de doua lucruri:
 
- un caz initial, nerecursiv, (care apare in demonstratii ca baza a inductiei )
 
- un caz initial, nerecursiv, (care apare in demonstratii ca baza a inductiei )
- o formula folosita in cazul exprimarii recursive atunci cand descriem cum se foloseste valoarea din capul listei si '''rezultatul prelucrarii ''' cozii listei pentru a obtine rezultatul final.
+
- o formula folosita in cazul exprimarii recursive atunci cand descriem cum se foloseste valoarea din capul listei si <br>'''rezultatul prelucrarii ''' cozii listei pentru a obtine rezultatul final.
   
 
Ca o prima idee puteti considera ca pe o lista [1,2,9,3,4] care este de fapt 1:2:9:3:4:[] <br> '''fold f v ''' inlocuieste constructorul : cu o functie '''f''' data de dumneavoastra si [] cu o valoare '''v''' data de dumneavoastra.
 
Ca o prima idee puteti considera ca pe o lista [1,2,9,3,4] care este de fapt 1:2:9:3:4:[] <br> '''fold f v ''' inlocuieste constructorul : cu o functie '''f''' data de dumneavoastra si [] cu o valoare '''v''' data de dumneavoastra.

Revision as of 17:08, 19 January 2008

Fold este numele unui sablon recursiv de procesarea a listelor. El este implementat in Haskell sub numele foldr.

Stim cu totii ca prelucrarea unei liste se poate face adesea dupa o schema recursiva. Aceasta schema depinde de doua lucruri:

- un caz initial, nerecursiv, (care apare in demonstratii ca baza a inductiei )
- o formula folosita in cazul exprimarii recursive atunci cand descriem cum se foloseste valoarea din capul listei si 
rezultatul prelucrarii cozii listei pentru a obtine rezultatul final.

Ca o prima idee puteti considera ca pe o lista [1,2,9,3,4] care este de fapt 1:2:9:3:4:[]
fold f v inlocuieste constructorul : cu o functie f data de dumneavoastra si [] cu o valoare v data de dumneavoastra.

Exemplu: Inlocuind (:) cu (+) si [] cu 0 puteti obtine 1+2+9+3+4+0 care este suma elementelor listei. Adica puteti reinventa functia de sumare a elementelor unei liste scriind: fold (+) 0

O serie de alti algoritmi si functii uzuale se pot scrie folosind fold. Acest sablon are o serie mare de alte aplicatii.

O foarte buna lucrare despre fold, existenta sa si implicatiile ei se putea gasi aici: A tutorial on the universality and expressiveness of fold - by Graham Hutton, Univ. of Nottingham, UK .

Nota: Deoarece functia aplicata poate sa nu fie comutativa in Haskell exista 2 de fold: foldl si foldr, care parcurg lista asociind de la stanga respectiv de la dreapta. Cel la care ne-am referit mai sus e implemnentat sub numele de foldr.


<= Inapoi la pagina principala Ro/Haskell