Folding Cheat Sheet #2

Programmatic and Mathematical definitions of right fold and left fold.

Keywords: folding, list, left fold, right fold, mathematical definition, programmatic definition

Transcript

1. CHEAT-SHEET Folding #2 ∶ / \ 𝒂𝟎 ∶ / \ 𝒂𝟏 ∶ / \ 𝒂𝟐 ∶ / \ 𝒂𝟑 𝒇 / \ 𝒂𝟎 𝒇 / \ 𝒂𝟏 𝒇 / \ 𝒂𝟐 𝒇 / \ 𝒂𝟑 𝒆 @philip_schwarz slides by https://fpilluminated.com/
2. ∶ / \ 𝑎0 ∶ / \ 𝑎1 ∶ / \ 𝑎2 ∶ / \ 𝑎3 𝑓 / \ 𝑓 𝑎3 / \ 𝑓 𝑎2 / \ 𝑓 𝑎1 / \ 𝑏 𝑎0 𝑓 / \ 𝑎0 𝑓 / \ 𝑎1 𝑓 / \ 𝑎2 𝑓 / \ 𝑎3 𝑏 𝑎0 : (𝑎1 : 𝑎2 : 𝑎3 : ) 𝑓 𝑓 𝑓 𝑓 𝑏 𝑎0 𝑎1 𝑎2 𝑎3 var 𝑎𝑐𝑐 = 𝑏 foreach(𝑎 in 𝑎𝑠) 𝑎𝑐𝑐 = 𝑓(𝑎𝑐𝑐, 𝑎) return 𝑎𝑐𝑐 𝑓𝑜𝑙𝑑𝑟 𝑓 𝑏 𝑎𝑠 𝑓𝑜𝑙𝑑𝑙 𝑓 𝑏 𝑎𝑠 𝑎𝑠 = [𝑎0 , 𝑎1 , 𝑎2 , 𝑎3 ] 𝑓𝑜𝑙𝑑𝑟 ∷ 𝛼 → 𝛽 → 𝛽 → 𝛽 → 𝛼 → 𝛽 𝑓𝑜𝑙𝑑𝑟 𝑓 𝑏 = 𝑏 𝑓𝑜𝑙𝑑𝑟 𝑓 𝑏 𝑥: 𝑥𝑠 = 𝑓 𝑥 𝑓𝑜𝑙𝑑𝑟 𝑓 𝑏 𝑥𝑠 𝑓𝑜𝑙𝑑𝑙 ∷ 𝛽 → 𝛼 → 𝛽 → 𝛽 → 𝛼 → 𝛽 𝑓𝑜𝑙𝑑𝑙 𝑓 𝑏 = 𝑏 𝑓𝑜𝑙𝑑𝑙 𝑓 𝑏 𝑥: 𝑥𝑠 = 𝑓𝑜𝑙𝑑𝑙 𝑓 𝑓 𝑏 𝑥 𝑥𝑠 𝑟𝑒𝑝𝑙𝑎𝑐𝑒: ∶ 𝑤𝑖𝑡ℎ 𝑓 𝑤𝑖𝑡ℎ 𝑏 𝑓𝑜𝑙𝑑𝑟 𝑓 𝑏 [𝑎0 , 𝑎1 , 𝑎2 , 𝑎3 ] 𝑓 𝑎0 𝑓𝑜𝑙𝑑𝑟 𝑓 𝑏 [𝑎1 , 𝑎2 , 𝑎3 ] 𝑓 𝑎0 (𝑓 𝑎1 (𝑓𝑜𝑙𝑑𝑟 𝑓 𝑏 [𝑎2 , 𝑎3 ])) 𝑓 𝑎0 (𝑓 𝑎1 (𝑓 𝑎2 (𝑓𝑜𝑙𝑑𝑟 𝑓 𝑏 [𝑎3 ]))) 𝑓 𝑎0 (𝑓 𝑎1 (𝑓 𝑎2 (𝑓 𝑎3 (𝑓𝑜𝑙𝑑𝑟 𝑓 𝑏 [ ])))) 𝑓 𝑎0 (𝑓 𝑎1 (𝑓 𝑎2 (𝑓 𝑎3 𝑏))) 𝑓 𝑎0 (𝑓 𝑎1 (𝑓 𝑎2 (𝑓 𝑎3 𝑏))) 𝑓𝑜𝑙𝑑𝑙 𝑓 𝑏 [𝑎0 , 𝑎1 , 𝑎2 , 𝑎3 ] 𝑓𝑜𝑙𝑑𝑙 𝑓 𝑓 𝑏 𝑎0 [𝑎1 , 𝑎2 , 𝑎3 ] 𝑓𝑜𝑙𝑑𝑙 𝑓 𝑓 𝑓 𝑏 𝑎0 𝑎1 [𝑎2 , 𝑎3 ] 𝑓𝑜𝑙𝑑𝑙 𝑓 𝑓 𝑓 𝑓 𝑏 𝑎0 𝑎1 𝑎2 [𝑎3 ] 𝑓𝑜𝑙𝑑𝑙 𝑓 𝑓 𝑓 𝑓 𝑓 𝑏 𝑎0 𝑎1 𝑎2 𝑎3 [ ] 𝑓 𝑓 𝑓 𝑓 𝑏 𝑎0 𝑎1 𝑎2 𝑎3 Programmatic definition of right fold and left fold 𝑓𝑜𝑙𝑑𝑟 associates 𝑓 from the right 𝑓𝑜𝑙𝑑𝑙 associates 𝑓 from the left
3. ∶ / \ 𝑎0 ∶ / \ 𝑎1 ∶ / \ 𝑎2 ∶ / \ 𝑎3 𝑓 / \ 𝑓 𝑎3 / \ 𝑓 𝑎2 / \ 𝑓 𝑎1 / \ 𝑏 𝑎0 𝑓 / \ 𝑎0 𝑓 / \ 𝑎1 𝑓 / \ 𝑎2 𝑓 / \ 𝑎3 𝑏 𝑎0 : (𝑎1 : 𝑎2 : 𝑎3 : ) 𝑓(𝑓 𝑓 𝑓 𝑏, 𝑎0 , 𝑎1 , 𝑎2 , 𝑎3 ) 𝑓𝑜𝑙𝑑𝑟 𝑎𝑠 𝑓𝑜𝑙𝑑𝑙 𝑎𝑠 𝑎𝑠 = [𝑎0 , 𝑎1 , 𝑎2 , 𝑎3 ] 𝑓(𝑎0 , 𝑓(𝑎1 , 𝑓(𝑎2 , 𝑓(𝑎3 , 𝑏)))) 𝑓𝑜𝑙𝑑𝑙 = 𝑏; 𝑓𝑜𝑙𝑑𝑙 𝑥𝑠 ⧺ [𝑥] = 𝑓(𝑓𝑜𝑙𝑑𝑙 𝑥𝑠 , 𝑥) 𝑓𝑜𝑙𝑑𝑟 = 𝑏; 𝑓𝑜𝑙𝑑𝑟 𝑥 ⧺ 𝑥𝑠 = 𝑓(𝑥, 𝑓𝑜𝑙𝑑𝑟(𝑥𝑠)) 𝑓𝑜𝑙𝑑𝑙 𝑎0 , 𝑎1 , 𝑎2 , 𝑎3 , 𝑓 𝑓𝑜𝑙𝑑𝑙 𝑎0 , 𝑎1 , 𝑎2 , 𝑎3 𝑓(𝑓(𝑓𝑜𝑙𝑑𝑙 [𝑎0 , 𝑎1 ] , 𝑎2 ), 𝑎3 ) 𝑓 𝑓 𝑓 𝑓𝑜𝑙𝑑𝑙 𝑎0 , 𝑎1 , 𝑎2 , 𝑎3 𝑓 𝑓 𝑓 𝑓 𝑓𝑜𝑙𝑑𝑙 [ ] , 𝑎0 , 𝑎1 , 𝑎2 , 𝑎3 𝑓 𝑓 𝑓 𝑓 𝑏, 𝑎0 , 𝑎1 , 𝑎2 , 𝑎3 𝑓𝑜𝑙𝑑𝑟([𝑎0 , 𝑎1 , 𝑎2 , 𝑎3 ]) 𝑓(𝑎0 , 𝑓𝑜𝑙𝑑𝑟([𝑎1 , 𝑎2 , 𝑎3 ])) 𝑓(𝑎0 , 𝑓(𝑎1 , 𝑓𝑜𝑙𝑑𝑟([𝑎2 , 𝑎3 ]))) 𝑓(𝑎0 , 𝑓(𝑎1 , 𝑓(𝑎2 , 𝑓𝑜𝑙𝑑𝑟([𝑎3 ])))) 𝑓(𝑎0 , 𝑓(𝑎1 , 𝑓(𝑎2 , 𝑓(𝑎3 , 𝑓𝑜𝑙𝑑𝑟([]))))) 𝑓(𝑎0 , 𝑓(𝑎1 , 𝑓(𝑎2 , 𝑓(𝑎3 , 𝑏)))) Mathematical definition of right fold and left fold 𝑓𝑜𝑙𝑑𝑟 associates 𝑓 from the right 𝑓𝑜𝑙𝑑𝑙 associates 𝑓 from the left 𝑥 = the Birst element 𝑥s = all but the Birst element 𝑥 = the last element 𝑥𝑠 = all but the last element
4. https://fpilluminated.com/ based on