Zippers
IB016 Seminář z funkcionálního programování
Vladimír Štill, Martin Ukrop
Fakulta informatiky, Masarykova univerzita
Jaro 2015
IB016: Cvičení 12 Jaro 2015 1 / 2
Motivace
Příklad: chceme naprogramovat funkci
findWithContext :: (a -> Bool) -> Int -> [a]
-> Maybe [a]
kde findWithContext p n l bude vyhledávat s seznamu l
hodnotu splňující predikát p, ale vrátí nejen nalezenou hodnotu, ale
navíc i n hodnot před a po této hodnotě.
Jak to naprogramovat tak, abychom l neprocházeli zbytečně
vícekrát?
IB016: Cvičení 12 Jaro 2015 2 / 2
Motivace
Příklad: chceme naprogramovat funkci
findWithContext :: (a -> Bool) -> Int -> [a]
-> Maybe [a]
kde findWithContext p n l bude vyhledávat s seznamu l
hodnotu splňující predikát p, ale vrátí nejen nalezenou hodnotu, ale
navíc i n hodnot před a po této hodnotě.
Jak to naprogramovat tak, abychom l neprocházeli zbytečně
vícekrát?
findWithContext p n l = fn l []
where
fn [] _ = Nothing
fn (x:xs) back
| p x = prepend (take n back) (x : take n xs)
| otherwise = fn xs (x : back)
prepend [] xs = Just xs
prepend (b:bs) xs = prepend bs (b:xs)
IB016: Cvičení 12 Jaro 2015 2 / 2
Stromy
data BinTree a = BNode (BinTree a) a (BinTree a)
| BEmpty
Jak efektivně procházet binární strom a pamatovat si pozici v něm?
IB016: Cvičení 12 Jaro 2015 3 / 2
Stromy
data BinTree a = BNode (BinTree a) a (BinTree a)
| BEmpty
Jak efektivně procházet binární strom a pamatovat si pozici v něm?
pamatovat si trasu k upravovanému uzlu
data Direction = L | R
deriving ( Eq, Ord, Show, Read )
type Trace = [Direction]
modify :: BinTree a -> Trace -> a -> BinTree a
IB016: Cvičení 12 Jaro 2015 3 / 2
Stromy
data BinTree a = BNode (BinTree a) a (BinTree a)
| BEmpty
Jak efektivně procházet binární strom a pamatovat si pozici v něm?
pamatovat si trasu k upravovanému uzlu
data Direction = L | R
deriving ( Eq, Ord, Show, Read )
type Trace = [Direction]
modify :: BinTree a -> Trace -> a -> BinTree a
neefektivní při opakovaných úpravách, úpravách blízkých uzlů!
IB016: Cvičení 12 Jaro 2015 3 / 2
Stromy
Ve stromě se budeme pohybovat, ale zároveň si budeme pamatovat
i trasu zpět pro rekonstrukci stromu.
data BinTree a = BNode (BinTree a) a (BinTree a)
| BEmpty
data TreeDir a = TLeft a (BinTree a)
| TRight (BinTree a) a
deriving ( Eq, Show, Read )
data TreeZipper a = TZip [TreeDir a] (BinTree a)
deriving ( Eq, Show, Read )
IB016: Cvičení 12 Jaro 2015 4 / 2
Stromy
Ve stromě se budeme pohybovat, ale zároveň si budeme pamatovat
i trasu zpět pro rekonstrukci stromu.
data BinTree a = BNode (BinTree a) a (BinTree a)
| BEmpty
data TreeDir a = TLeft a (BinTree a)
| TRight (BinTree a) a
deriving ( Eq, Show, Read )
data TreeZipper a = TZip [TreeDir a] (BinTree a)
deriving ( Eq, Show, Read )
Manipulaci můžeme realizovat například pomocí:
goLeft :: TreeZipper a -> TreeZipper a
goRight :: TreeZipper a -> TreeZipper a
goUp :: TreeZipper a -> TreeZipper a
modify :: (a -> a) -> TreeZipper a -> TreeZipper a
IB016: Cvičení 12 Jaro 2015 4 / 2
Stromy: příklad
[] 1
2 3
4 5 6 7
zipper = TZip [] (N (N (N E 4 E) 2 (N E 5 E) 1 (N (N
E 6 E) 3 (N E 7 E)))
IB016: Cvičení 12 Jaro 2015 5 / 2
Stromy: příklad
[] 1
2 3
4 5 6 7
goLeft zipper
IB016: Cvičení 12 Jaro 2015 5 / 2
Stromy: příklad
[]
L 1 2 3
4 5 6 7
zipper TZip [L 1 (N (N E 6 E) 3 (N E 7 E))] (N (N E
4 E) 2 (N E 5 E))
IB016: Cvičení 12 Jaro 2015 5 / 2
Stromy: příklad
[]
L 1 2 3
4 5 6 7
goRight zipper
IB016: Cvičení 12 Jaro 2015 5 / 2
Stromy: příklad
[]
L 1
R 2
3
4 5 6 7
zipper TZip [R (N E 4 E) 2, L 1 (N (N E 6 E) 3 (N E
7 E))] (N E 5 E)
IB016: Cvičení 12 Jaro 2015 5 / 2
Stromy: příklad
[]
L 1
R 2
3
4 5 6 7
modify (+ 37) zipper
IB016: Cvičení 12 Jaro 2015 5 / 2
Stromy: příklad
[]
L 1
R 2
3
4 42 6 7
zipper = TZip [R (N E 4 E) 2, L 1 (N (N E 6 E) 3 (N
E 7 E))] (N E 42 E)
IB016: Cvičení 12 Jaro 2015 5 / 2
Stromy: příklad
[]
L 1
R 2
3
4 42 6 7
goUp zipper
IB016: Cvičení 12 Jaro 2015 5 / 2
Stromy: příklad
[]
L 1 2 3
4 42 6 7
zipper TZip [L 1 (N (N E 6 E) 3 (N E 7 E))] (N (N E
4 E) 2 (N E 42 E))
IB016: Cvičení 12 Jaro 2015 5 / 2
Zipper
obecně zipper pro danou datovou strukturu je datová
struktura obohacená o „kontext“, který umožňuje efektivně
manipulovat pozici ve struktuře
pro seznam: data ListZip a = LZip [a] [a]
dvojice seznamů: jeden obsahuje dosud neprojitý seznam,
druhý prvky, které již byly projity v opačném pořadí
pro strom: strom spolu se seznamem kroků zpět ke kořeni –
vrchol + levý nebo pravý podstrom
obdobně pro složitější struktury
IB016: Cvičení 12 Jaro 2015 6 / 2