Práce se složitějšími datovými strukturami
(zippers, lenses)
IB016 Seminář z funkcionálního programování
Vladimír Štill, Martin Ukrop
Fakulta informatiky, Masarykova univerzita
Jaro 2018
IB016: Cvičení 08 Jaro 2018 1 / 24
Motivace I.
Příklad: chceme naprogramovat funkci
findContext :: (a -> Bool) -> Int -> [a] -> Maybe [a]
kde findContext p n l bude vyhledávat v 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ě.
findContext even 2 [1,3,5,6,7,9,11,13]
      ∗ Just [3,5,6,7,9]
IB016: Cvičení 08 Jaro 2018 2 / 24
Motivace II.
import Data.List (findIndex)
findContext1 :: (a->Bool) -> Int -> [a] -> Maybe [a]
findContext1 p n xs = do
   index <- findIndex p xs
   return . drop (index - n) $ take (index + n + 1) xs
IB016: Cvičení 08 Jaro 2018 3 / 24
Motivace II.
import Data.List (findIndex)
findContext1 :: (a->Bool) -> Int -> [a] -> Maybe [a]
findContext1 p n xs = do
   index <- findIndex p xs
   return . drop (index - n) $ take (index + n + 1) xs
Jak to naprogramovat tak, abychom seznam xs neprocházeli
zbytečně vícekrát?
IB016: Cvičení 08 Jaro 2018 3 / 24
Motivace III.
findContext2 :: (a->Bool) -> Int -> [a] -> Maybe [a]
findContext2 p n xs = fn xs []
   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í 08 Jaro 2018 4 / 24
Seznamy
Co když budeme chtít jinou funkci na seznamech, která pracuje s
lokálním kontextem velkého seznamu?
IB016: Cvičení 08 Jaro 2018 5 / 24
Seznamy
Co když budeme chtít jinou funkci na seznamech, která pracuje s
lokálním kontextem velkého seznamu?
Zevšeobecníme kontextové procházení seznamů:
data LZipper a = LZip [a] [a]
goForward   :: LZipper a -> Maybe (LZipper a)
goBackward :: LZipper a -> Maybe (LZipper a)
modifyLZip :: (a -> a) -> LZipper a -> LZipper a
listToZip :: [a] -> LZipper a
zipToList :: LZipper a -> [a]
IB016: Cvičení 08 Jaro 2018 5 / 24
Binární stromy I.
Jak si pamatovat pozici v binárním stromu, abychom mohli
efektivně zpracovávat okolí aktuálního uzlu?
data BinTree a = BNode (BinTree a) a (BinTree a)
                     | BEmpty
IB016: Cvičení 08 Jaro 2018 6 / 24
Binární stromy I.
Jak si pamatovat pozici v binárním stromu, abychom mohli
efektivně zpracovávat okolí aktuálního uzlu?
data BinTree a = BNode (BinTree a) a (BinTree a)
                     | BEmpty
Můžeme si pamatovat trasu k upravovanému uzlu
data Direction = L | R
modify :: BinTree a -> [Direction] -> a -> BinTree a
Neefektivní při opakovaných úpravách, úpravách blízkých uzlů!
IB016: Cvičení 08 Jaro 2018 6 / 24
Binární stromy II.
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
IB016: Cvičení 08 Jaro 2018 7 / 24
Binární stromy II.
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í 08 Jaro 2018 7 / 24
Binární 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í 08 Jaro 2018 8 / 24
Binární stromy: příklad
[] 1
2 3
4 5 6 7
goLeft zipper
IB016: Cvičení 08 Jaro 2018 8 / 24
Binární 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í 08 Jaro 2018 8 / 24
Binární stromy: příklad
[]
L 1 2 3
4 5 6 7
goRight zipper
IB016: Cvičení 08 Jaro 2018 8 / 24
Binární 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í 08 Jaro 2018 8 / 24
Binární stromy: příklad
[]
L 1
R 2
3
4 5 6 7
modify (+ 37) zipper
IB016: Cvičení 08 Jaro 2018 8 / 24
Binární 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í 08 Jaro 2018 8 / 24
Binární stromy: příklad
[]
L 1
R 2
3
4 42 6 7
goUp zipper
IB016: Cvičení 08 Jaro 2018 8 / 24
Binární 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í 08 Jaro 2018 8 / 24
Binární stromy: implementace
Manipulaci můžeme realizovat například pomocí:
goLeft   :: TZipper a -> TZipper a
goRight :: TZipper a -> TZipper a
goUp      :: TZipper a -> TZipper a
modify   :: (a -> a) -> TZipper a -> TZipper a
IB016: Cvičení 08 Jaro 2018 9 / 24
Zippers: Shrnutí
zipper pro danou datovou strukturu je datová struktura obohacená
o „kontext“, který umožňuje efektivně manipulovat pozici ve
struktuře
seznam:
zipper je dvojice seznamů: jeden obsahuje dosud neprojitý
seznam, druhý prvky, které již byly projity v opačném pořadí
binární strom:
zipper je aktuální strom spolu se seznamem kroků zpět ke
kořeni (vrchol + levý nebo pravý podstrom)
obdobně pro složitější struktury
IB016: Cvičení 08 Jaro 2018 10 / 24
Lenses: Motivační příklad
data Person = Person {
      eid :: Int ,
      name :: String } deriving Show
data Project = Project {
      lead :: Person ,
      techLead :: Person } deriving Show
data Team = Team {
      job1 :: Project ,
      job2 :: Project } deriving Show
IB016: Cvičení 08 Jaro 2018 11 / 24
Porovnání s jinými jazyky
data Person   = Person   { eid :: Int, name :: String }
data Project = Project { lead :: Person, techLead :: Person }
data Team      = Team      { job1 :: Project, job2 :: Project }
Jak změnit EID vedoucího prvního projektu v týmu t?
IB016: Cvičení 08 Jaro 2018 12 / 24
Porovnání s jinými jazyky
data Person   = Person   { eid :: Int, name :: String }
data Project = Project { lead :: Person, techLead :: Person }
data Team      = Team      { job1 :: Project, job2 :: Project }
Jak změnit EID vedoucího prvního projektu v týmu t?
V Haskellu (využívajíc záznamů):
t { job1 = (job1 t) { lead =
      (lead $ job1 t) { eid = 123 }
   } }
IB016: Cvičení 08 Jaro 2018 12 / 24
Porovnání s jinými jazyky
data Person   = Person   { eid :: Int, name :: String }
data Project = Project { lead :: Person, techLead :: Person }
data Team      = Team      { job1 :: Project, job2 :: Project }
Jak změnit EID vedoucího prvního projektu v týmu t?
V Haskellu (využívajíc záznamů):
t { job1 = (job1 t) { lead =
      (lead $ job1 t) { eid = 123 }
   } }
V „běžných“ jazycích (C, Java, ...):
t.job1.lead.eid = 123;
IB016: Cvičení 08 Jaro 2018 12 / 24
Datové struktury: setters & updaters
data Person   = Person   { eid :: Int, name :: String }
data Project = Project { lead :: Person, techLead :: Person }
data Team      = Team      { job1 :: Project, job2 :: Project }
Napišme si „setter“ a „updater“:
setEid :: Int -> Person -> Person
overLead :: (Person -> Person) -> Project -> Project
overJob1 :: (Project -> Project) -> Team -> Team
IB016: Cvičení 08 Jaro 2018 13 / 24
Datové struktury: setters & updaters
data Person   = Person   { eid :: Int, name :: String }
data Project = Project { lead :: Person, techLead :: Person }
data Team      = Team      { job1 :: Project, job2 :: Project }
Napišme si „setter“ a „updater“:
setEid :: Int -> Person -> Person
overLead :: (Person -> Person) -> Project -> Project
overJob1 :: (Project -> Project) -> Team -> Team
Změna EID vedoucího prvního projektu v týmu t:
(overJob1 . overLead . setEid) 123 t
Pozorování: Modifikační funkce se dobře skládají.
IB016: Cvičení 08 Jaro 2018 13 / 24
Lenses: základní myšlenka
lens ≈ kombinace „getter“ a „setter“ funkcí pro manipulaci
s (pod)částí dané datové struktury
lze je skládat, brát jako argumenty, modifikovat, vracet, ...
ulehčují práci se složitými (vnorenými) datovými strukturami
IB016: Cvičení 08 Jaro 2018 14 / 24
Lenses: základní myšlenka
lens ≈ kombinace „getter“ a „setter“ funkcí pro manipulaci
s (pod)částí dané datové struktury
lze je skládat, brát jako argumenty, modifikovat, vracet, ...
ulehčují práci se složitými (vnorenými) datovými strukturami
První (naivní) implementace:
data Lens'' s a = Lens''
      { view ::                  s -> a
      , set   ::         a   -> s -> s
      , over :: (a -> a) -> s -> s
      }
IB016: Cvičení 08 Jaro 2018 14 / 24
Příklad
data Person = Person { eid :: Int, name :: String }
data Lens'' s a = Lens''
      { view ::                  s -> a
      , set   ::         a   -> s -> s
      , over :: (a -> a) -> s -> s }
Jak vypadá lens pro eid v rámci Person?
IB016: Cvičení 08 Jaro 2018 15 / 24
Příklad
data Person = Person { eid :: Int, name :: String }
data Lens'' s a = Lens''
      { view ::                  s -> a
      , set   ::         a   -> s -> s
      , over :: (a -> a) -> s -> s }
Jak vypadá lens pro eid v rámci Person?
eidLens :: Lens'' Person Int
eidLens = Lens''
      { view = ( \         p -> eid p )
      , set   = ( \neweid p -> p { eid = neweid } )
      , over = ( \f         p -> p { eid = f (eid p) } ) }
IB016: Cvičení 08 Jaro 2018 15 / 24
Příklad
data Person = Person { eid :: Int, name :: String }
data Lens'' s a = Lens''
      { view ::                  s -> a
      , set   ::         a   -> s -> s
      , over :: (a -> a) -> s -> s }
Jak vypadá lens pro eid v rámci Person?
eidLens :: Lens'' Person Int
eidLens = Lens''
      { view = ( \         p -> eid p )
      , set   = ( \neweid p -> p { eid = neweid } )
      , over = ( \f         p -> p { eid = f (eid p) } ) }
Použití:
view eidLens         p
set   eidLens 123   p
over eidLens (+1) p
IB016: Cvičení 08 Jaro 2018 15 / 24
A co vedlejší efekty?
A co když bude úprava mít vedlejší efekty?
adjustEidWithCheck :: Int -> IO Int
(kontroluje platnost daného EID v databázi)
IB016: Cvičení 08 Jaro 2018 16 / 24
A co vedlejší efekty?
A co když bude úprava mít vedlejší efekty?
adjustEidWithCheck :: Int -> IO Int
(kontroluje platnost daného EID v databázi)
Přidejme ještě „updater“ tvořící výsledek ve funktoru.
overF :: Functor f => (a -> f a) -> s -> f s
IB016: Cvičení 08 Jaro 2018 16 / 24
A co vedlejší efekty?
A co když bude úprava mít vedlejší efekty?
adjustEidWithCheck :: Int -> IO Int
(kontroluje platnost daného EID v databázi)
Přidejme ještě „updater“ tvořící výsledek ve funktoru.
overF :: Functor f => (a -> f a) -> s -> f s
Pro eidLens :: Lens'' Person Int
overF :: Functor f =>
      (Int -> f Int) -> Person -> f Person
overF f p = fmap
      (\neweid -> p { eid = neweid })
      (f $ eid p)
IB016: Cvičení 08 Jaro 2018 16 / 24
Zobecňování I.
data Lens'' s a = Lens''
      { view   ::                                          s ->   a
      , set   ::                                 a   -> s ->   s
      , over   ::                     (a ->   a) -> s ->   s
      , overF :: Functor f => (a -> f a) -> s -> f s }
Naše lens začíná mít příliš mnoho operátorů ...
Nemohli bychom vyjářit set pomocí ostatních částí Lens''?
IB016: Cvičení 08 Jaro 2018 17 / 24
Zobecňování I.
data Lens'' s a = Lens''
      { view   ::                                          s ->   a
      , set   ::                                 a   -> s ->   s
      , over   ::                     (a ->   a) -> s ->   s
      , overF :: Functor f => (a -> f a) -> s -> f s }
Naše lens začíná mít příliš mnoho operátorů ...
Nemohli bychom vyjářit set pomocí ostatních částí Lens''?
set :: a -> s -> s
set newval object = over (\_ -> newval) object
IB016: Cvičení 08 Jaro 2018 17 / 24
Zobecňování II.
data Lens'' s a = Lens''
      { view   ::                                          s ->   a
      , over   ::                     (a ->   a) -> s ->   s
      , overF :: Functor f => (a -> f a) -> s -> f s }
Nemohli bychom vyjářit over pomocí ostatních částí Lens''?
IB016: Cvičení 08 Jaro 2018 18 / 24
Zobecňování II.
data Lens'' s a = Lens''
      { view   ::                                          s ->   a
      , over   ::                     (a ->   a) -> s ->   s
      , overF :: Functor f => (a -> f a) -> s -> f s }
Nemohli bychom vyjářit over pomocí ostatních částí Lens''?
Knihovní funktor Identity:
newtype Identity a = Identity { runIdentity :: a }
instance Functor Identity where
   fmap f (Identity x) = Identity (f x)
IB016: Cvičení 08 Jaro 2018 18 / 24
Zobecňování II.
data Lens'' s a = Lens''
      { view   ::                                          s ->   a
      , over   ::                     (a ->   a) -> s ->   s
      , overF :: Functor f => (a -> f a) -> s -> f s }
Nemohli bychom vyjářit over pomocí ostatních částí Lens''?
Knihovní funktor Identity:
newtype Identity a = Identity { runIdentity :: a }
instance Functor Identity where
   fmap f (Identity x) = Identity (f x)
over :: (a -> a) -> s -> s
over f object = runIdentity $ overF (Identity . f) s
IB016: Cvičení 08 Jaro 2018 18 / 24
Zobecňování III.
data Lens'' s a = Lens''
      { view   ::                                          s ->   a
      , overF :: Functor f => (a -> f a) -> s -> f s }
Nemohli bychom vyjářit view pomocí ostatních částí Lens''?
IB016: Cvičení 08 Jaro 2018 19 / 24
Zobecňování III.
data Lens'' s a = Lens''
      { view   ::                                          s ->   a
      , overF :: Functor f => (a -> f a) -> s -> f s }
Nemohli bychom vyjářit view pomocí ostatních částí Lens''?
Knihovní funktor Const:
newtype Const a b = Const { getConst :: a }
instance Functor (Const a) where
   fmap _ (Const a) = Const a
IB016: Cvičení 08 Jaro 2018 19 / 24
Zobecňování III.
data Lens'' s a = Lens''
      { view   ::                                          s ->   a
      , overF :: Functor f => (a -> f a) -> s -> f s }
Nemohli bychom vyjářit view pomocí ostatních částí Lens''?
Knihovní funktor Const:
newtype Const a b = Const { getConst :: a }
instance Functor (Const a) where
   fmap _ (Const a) = Const a
view :: s -> a
view s = getConst $ overF Const s
IB016: Cvičení 08 Jaro 2018 19 / 24
Příklad
data Person = Person { eid :: Int, name :: String }
eidLens :: Lens'' Person Int
eidLens = Lens'' {overF = \f p -> fmap (\x -> p {eid=x}) (f $ eid p)}
newtype Const a b = Const { getConst :: a }
fmap _ (Const a) = Const a
view s = getConst $ overF Const s
viewEid p
      where p = (Person 123 "John Doe")
IB016: Cvičení 08 Jaro 2018 20 / 24
Příklad
data Person = Person { eid :: Int, name :: String }
eidLens :: Lens'' Person Int
eidLens = Lens'' {overF = \f p -> fmap (\x -> p {eid=x}) (f $ eid p)}
newtype Const a b = Const { getConst :: a }
fmap _ (Const a) = Const a
view s = getConst $ overF Const s
viewEid p
      where p = (Person 123 "John Doe")
getConst $ (overF eidLens) Const p
IB016: Cvičení 08 Jaro 2018 20 / 24
Příklad
data Person = Person { eid :: Int, name :: String }
eidLens :: Lens'' Person Int
eidLens = Lens'' {overF = \f p -> fmap (\x -> p {eid=x}) (f $ eid p)}
newtype Const a b = Const { getConst :: a }
fmap _ (Const a) = Const a
view s = getConst $ overF Const s
viewEid p
      where p = (Person 123 "John Doe")
getConst $ (overF eidLens) Const p
getConst $ fmap (\x -> p {eid=x}) (Const $ eid p)
IB016: Cvičení 08 Jaro 2018 20 / 24
Příklad
data Person = Person { eid :: Int, name :: String }
eidLens :: Lens'' Person Int
eidLens = Lens'' {overF = \f p -> fmap (\x -> p {eid=x}) (f $ eid p)}
newtype Const a b = Const { getConst :: a }
fmap _ (Const a) = Const a
view s = getConst $ overF Const s
viewEid p
      where p = (Person 123 "John Doe")
getConst $ (overF eidLens) Const p
getConst $ fmap (\x -> p {eid=x}) (Const $ eid p)
getConst $ fmap (\x -> p {eid=x}) (Const 123)
IB016: Cvičení 08 Jaro 2018 20 / 24
Příklad
data Person = Person { eid :: Int, name :: String }
eidLens :: Lens'' Person Int
eidLens = Lens'' {overF = \f p -> fmap (\x -> p {eid=x}) (f $ eid p)}
newtype Const a b = Const { getConst :: a }
fmap _ (Const a) = Const a
view s = getConst $ overF Const s
viewEid p
      where p = (Person 123 "John Doe")
getConst $ (overF eidLens) Const p
getConst $ fmap (\x -> p {eid=x}) (Const $ eid p)
getConst $ fmap (\x -> p {eid=x}) (Const 123)
getConst $ Const 123
123
IB016: Cvičení 08 Jaro 2018 20 / 24
Balík lens
Knihovní balík lens:
nejznámější Haskellová implementace lenses
„batteries included“ ⇒ mnoho funkcí i závislostí
moduly Control.Lens.*
obecnější, než naše lenses
umožňuje generovat lenses automaticky
IB016: Cvičení 08 Jaro 2018 21 / 24
Balík lens
Knihovní balík lens:
nejznámější Haskellová implementace lenses
„batteries included“ ⇒ mnoho funkcí i závislostí
moduly Control.Lens.*
obecnější, než naše lenses
umožňuje generovat lenses automaticky
type Lens' s a = Functor f => (a -> f a) -> s -> f s
view :: Lens' s a ->                  s -> a
over :: Lens' s a -> (a -> a) -> s -> s
set   :: Lens' s a ->         a   -> s -> s
set lens b = over lens (\_ -> b)
IB016: Cvičení 08 Jaro 2018 21 / 24
lens: Ukázka použití
{-# LANGUAGE TemplateHaskell #-}
import Control.Lens
data Person   = Person   { _eid :: Int, _name :: String }
data Project = Project { _lead :: Person, _techLead :: Person }
data Team      = Team      { _job1 :: Project, _job2 :: Project }
makeLenses ''Person
makeLenses ''Project
makeLenses ''Team
IB016: Cvičení 08 Jaro 2018 22 / 24
lens: Ukázka použití
{-# LANGUAGE TemplateHaskell #-}
import Control.Lens
data Person   = Person   { _eid :: Int, _name :: String }
data Project = Project { _lead :: Person, _techLead :: Person }
data Team      = Team      { _job1 :: Project, _job2 :: Project }
makeLenses ''Person
makeLenses ''Project
makeLenses ''Team
getJob1LeadEid :: Team -> Int
getJob1LeadEid t = view (job1 . lead . eid) t
setJob1LeadEid :: Int -> Team -> Team
setJob1LeadEid x t = set (job1 . lead . eid) x t
IB016: Cvičení 08 Jaro 2018 22 / 24
lens: Ukázka použití
{-# LANGUAGE TemplateHaskell #-}
import Control.Lens
data Person   = Person   { _eid :: Int, _name :: String }
data Project = Project { _lead :: Person, _techLead :: Person }
data Team      = Team      { _job1 :: Project, _job2 :: Project }
makeLenses ''Person
makeLenses ''Project
makeLenses ''Team
getJob1LeadEid :: Team -> Int
getJob1LeadEid t = view (job1 . lead . eid) t
setJob1LeadEid :: Int -> Team -> Team
setJob1LeadEid x t = set (job1 . lead . eid) x t
getJob1LeadEid' t = t^.job1.lead.eid
setJob1LeadEid' x = job1.lead.eid.~x
IB016: Cvičení 08 Jaro 2018 22 / 24
Lenses jsou jen začátek...
Implementace z balíka lens
lenses mohou měnit strukturu objektu:
type Lens   s t a b = Functor f => (a -> f b) -> s -> f t
existují pravidla pro validní lenses
možnost pracovat i s vícero hodnotami zaráz (traversals)
možnost pracovat s typy, které mají víc konstruktorů (prisms)
možnost využívat vztahy mezi typy (isos)
...
IB016: Cvičení 08 Jaro 2018 23 / 24
Lenses jsou jen začátek...
Implementace z balíka lens
lenses mohou měnit strukturu objektu:
type Lens   s t a b = Functor f => (a -> f b) -> s -> f t
existují pravidla pro validní lenses
možnost pracovat i s vícero hodnotami zaráz (traversals)
možnost pracovat s typy, které mají víc konstruktorů (prisms)
možnost využívat vztahy mezi typy (isos)
...
Další čtení v případě zájmu:
tutoriál na Jakub Arnold Blog
balík Control.Lens.Tutorial
IB016: Cvičení 08 Jaro 2018 23 / 24
Zippers, lenses: Samostatná práce
Princip zippers můžeme zobecnit typovou (konstruktorovou)
třídou. Zamyslete se, jak by deklarace/instance této třidy
vypadaly a pak se podívejte na naši implementaci v ISu.
Podívejte se na větší program, který používá lenses:
jednoduchou implementaci hry Pong od Edwarda Kmetta
přímo v balíku lens.
Přečtěte si motivaci a detaily k třídám Foldable a Traversable
a pak tutoriál k obecnějším lens na blogu Jakuba Arnolda.
IB016: Cvičení 08 Jaro 2018 24 / 24