Difference between revisions of "Ce se intelege prin fold ?"
m |
|||
(4 intermediate revisions by the same user not shown) | |||
Line 1: | Line 1: | ||
+ | [[Category:Ro]] |
||
+ | |||
Fold este numele unui sablon recursiv de procesarea a listelor. El este implementat in Haskell sub numele ''foldr''. |
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: |
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 <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:[] '''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. |
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 |
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 |
||
Line 13: | Line 15: | ||
O foarte buna lucrare despre fold, existenta sa si implicatiile ei se putea gasi aici: |
O foarte buna lucrare despre fold, existenta sa si implicatiile ei se putea gasi aici: |
||
− | [http://www.cs.nott.ac.uk/~gmh/foldl.pdf A tutorial on the universality and expressiveness of fold ]- by Graham Hutton, Univ. of Nottingham, UK |
+ | [http://www.cs.nott.ac.uk/~gmh/foldl.pdf 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''. |
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''. |
||
+ | Vedeti si [[Care este deosebirea dintre foldl si foldr ?]]. |
||
+ | ---- |
||
+ | Pagina indexata la indexul [[Category:Ro]] [http://www.haskell.org/haskellwiki/Category:Ro Categories:Ro] |
||
+ | ---- |
||
+ | [http://www.haskell.org/haskellwiki/Ro/Haskell <= Inapoi la pagina principala Ro/Haskell. ]<br> <br> |
||
+ | [http://www.haskell.org/haskellwiki/Intrebarile_incepatorului <'''-''' Inapoi la inceputul paginii 'Intrebarile incepatorului Ro/Haskell'. ] |
Latest revision as of 14:58, 10 February 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. Vedeti si Care este deosebirea dintre foldl si foldr ?.
Pagina indexata la indexul Categories:Ro
<= Inapoi la pagina principala Ro/Haskell.
<- Inapoi la inceputul paginii 'Intrebarile incepatorului Ro/Haskell'.