Mikä on WikiWiki?
nettipäiväkirja
koko wiki (etsi)
viime muutokset
Opin tällä viikolla asian, jonka minua coolimmat tyypit ovat varmaan tienneet jo kauan: jokainen toisentyyppisiä tietoja sisältävä induktiivinen tietotyyppi ja jokainen tällaisen tietotyypin derivaatta (niinkutsuttu "zipper") toteuttavat komonadin. Ja komonadia taas voi käyttää laskemaan tietorakenteesta uuden tietorakenteen, jossa jokaisen solun sisältö voi riippua koko tietorakenteesta. Zipperien lisähyöty on siinä, että tulos voi riippua myös laskettavan kohdan ulkopuolella olevista asioista, kun taas induktiivisten tietorakenteiden komonadissa se voi riippua vain laskettavan kohdan alla olevista asioista.
Yritän antaa tästä joitain esimerkkejä. Löysin koko jutun yrittäessäni etsiä esimerkkejä, mitä hyötyä komonadeista voisi edes olla. Oikeasti muiden esimerkit ovat parempia, mutta ei se mitään. Voin vaikka huvikseni kirjoittaa esimerkit Schemellä, ehkä siinä on jotain lisäarvoa.
Ensin induktiiviset tietorakenteet. Esimerkiksi ei-tyhjän listanhan voi määritellä:
;; list a :-- Single a | Cons a (list a) (define (single h) `(single ,h)) (define (cons h t) `(cons ,h ,t)) (define (single? list) (eq? (car list) 'single)) (define (cons? list) (eq? (car list) 'cons)) (define (head list) (and (or (single? list) (cons? list)) (cadr list))) (define (tail list) (and (cons? list) (caddr list)))
Minusta komonadit on helpompaa hahmottaa cojoin-operaation kautta kuin cobind-operaation kautta. (Useissa netissä olevissa esimerkeissä cobind on kirjoitettu suoraan fmap:n ja cojoinin yhdistelmänä.) Nyt kun listaa tarkastellaan komonadina, sen ensimmäinen elementti on "varsinainen tieto" ja loput elementit ovat "lisätietoa" tai "ympäristö" varsinaiselle tiedolle. (Tämä on myös syy, miksi käsittelemme juuri epätyhjiä listoja: tyhjä lista ei sovi komonadiin, koska varsinainen tieto puuttuu.) Komonadi tarjoaa seuraavat operaatiot:
Counit ja fmap ovat itsestään selviä listoille, ainakin jos on ollut yhtään listojen kanssa tekemisissä. Kuten sanottu, counit ottaa ulos "varsinaisen tiedon" eli ensimmäisen elementin ja fmap on perinteinen map joka soveltaa funktion joka kohtaan listaa:
(define list-counit head)
(define (list-map f list)
(if (single? list) (single (f (head list)))
(cons (f (head list)) (list-map f (tail list)))))
;; (list-map (lambda (x) (+ 3 x)) (cons 1 (cons 2 (single 3))))
;; ==> (cons 4 (cons 5 (single 6)))
Jee, vihdoinkin päästään siihen jännittävään eli cojoiniin. Cojoinin pitää siis korvata listan jokainen kohta kokonaisella listalla. Millä listalla? Sillä listalla, joka kyseisestä listan kohdasta käsin "näkyy". Yksi komonadilaki nimittäin on se, että counit . cojoin == id. Tavallaan cojoin korvaa listan kaikilla niillä näkymillä, jotka listan sisältöön voi olla. Esimerkiksi listasta [1, 3, 4, 5] tulee listalista [[1, 3, 4, 5], [3, 4, 5], [4, 5], [5]]. Listan toinen kohta korvautuu sillä, mitä listasta näkyy toisesta kohdasta käsin, ja niin edelleen.
(define (list-cojoin list)
(if (single? list) (single list)
(cons list (list-cojoin (tail list)))))
;; (list-cojoin (cons 1 (cons 2 (single 3))))
;; ==> (cons (cons 1 (cons 2 (single 3)))
;; (cons (cons 2 (single 3))
;; (single (single 3))))
Ja nyt: mitä helvettiä tämmöisellä cojoinilla tekee? Sillä voi laskea nätisti algoritmeja, jotka ovat "vähän niin kuin map" mutta kukin tulos ei riipu vain yhdestä elementistä vaan mahdollisesti myös sen ympäristöstä eli niistä "lisätiedoista". Esimerkiksi, ajatellaan että lista sisältää yhden Pascalin kolmion rivin. Siitä voi laskea seuraavan rivin ynnäämällä listasta kaksi peräkkäistä lukua. Ei-komonadinen tapa laskea se voisi olla vaikka näin:
(define (next-pascal list)
(if (single? list) list
(cons (+ (head list) (head (tail list))) (next-pascal (tail list)))))
Cojoinin avulla taas tarvitsee kirjoittaa vain funktio, joka ottaa tietyn näkymän listaan ja laskee siitä tuloksen siinä kohtaa listaa:
(define (count-pascal environment)
(if (single? environment) (head environment)
(+ (head environment) (head (tail environment)))))
(define (next-pascal list)
(list-map count-pascal (list-cojoin list)))
;; (next-pascal (cons 0 (cons 2 (cons 1 (single 1)))))
;; ==> (cons 2 (cons 3 (cons 2 (single 1))))
Toinen esimerkki cojoinin avulla toteutettavasta algoritmista voisi olla sellainen, joka täggää jokaiseen listan kohtaan, kuinka monta kappaletta kyseisen kohdan elementtiä on listassa:
(define (count-occurrences element list)
(let ((head-occurrences (if (eq? element (head list)) 1 0)))
(if (single? list) head-occurrences
(+ head-occurrences (count-occurrences element (tail list))))))
;; (count-occurrences 'foo (cons 'foo (cons 'foo (cons 'bar (single 'foo)))))
;; ==> 3
(define (frequencies list)
(list-map (lambda (ls) `(,(head ls) ,(count-occurrences (head ls) ls)))
(list-cojoin list)))
;; (frequencies (cons 'foo (cons 'foo (cons 'bar (single 'foo)))))
;; ==> (cons (foo 3) (cons (foo 2) (cons (bar 1) (single (foo 1)))))
Samaan tapaan esimerkiksi epätyhjä puu voidaan nähdä komonadina, jossa juurisolmun arvo on "varsinainen arvo" ja alipuut ovat lisätietoa. Cojoin on jälleen operaatio, joka korvaa puun jokaisen solmun sillä puulla, joka on kyseisen solmun alla.
;; tree a :-- Leaf a | Tree a (tree a) (tree a)
(define (leaf a) `(leaf ,a))
(define (tree a l r) `(tree ,a ,l ,r))
(define (leaf? t) (eq? (car t) 'leaf))
(define (tree? t) (eq? (car t) 'tree))
(define (value t) (and (or (leaf? t) (tree? t)) (cadr t)))
(define (left t) (and (tree? t) (caddr t)))
(define (right t) (and (tree? t) (cadddr t)))
(define example-tree (tree 6 (tree 2 (leaf 1) (tree 8 (leaf 3) (leaf 5)))
(tree 9 (leaf 7) (leaf 11))))
;; (right (left example-tree))
;; ==> (tree 8 (leaf 3) (leaf 5))
Jälleen counit on juuressa oleva arvo, fmap soveltaa funktiota kaikkiin puun solmujen arvoihin, ja cojoin, komonadin varsinainen taika, muuttaa puun "puunäkymiksi" eri solmuista.
(define tree-counit value)
(define (tree-map f t)
(if (leaf? t) (leaf (f (value t)))
(tree (f (value t)) (tree-map f (left t)) (tree-map f (right t)))))
;; (tree-map (lambda (x) (+ x 3)) example-tree)
;; ==> (tree 9 (tree 5 (leaf 4)
;; (tree 11 (leaf 6) (leaf 8)))
;; (tree 12 (leaf 10) (leaf 14)))
(define (tree-cojoin t)
(if (leaf? t) (leaf t)
(tree t (tree-cojoin (left t)) (tree-cojoin (right t)))))
;; (tree-cojoin (tree 1 (leaf 2) (leaf 3)))
;; ==> (tree (tree 1 (leaf 2) (leaf 3)) (leaf (leaf 2)) (leaf (leaf 3)))
... ja edelleen, cojoinin avulla pystyy laskemaan sellaisia algoritmeja, jotka laskevat solmulle uuden arvon solmusta itsestään ja sen ympäristöstä. Esimerkiksi algoritmi, joka kertoo jokaisesta solmusta, onko sen vasen alipuu tagattu pienemmällä numerolla ja oikea suuremmalla (eli onko puu tässä kohtaa oikeaoppinen binäärihakupuu):
(define (tree-ordered-at-root? t) (or (leaf? t) (<= (value (left t)) (value t) (value (right t))))) (define (well-ordered-places t) (tree-map tree-ordered-at-root? (tree-cojoin t))) ;; (well-ordered-places example-tree) ;; ==> (tree #t (tree #t (leaf #t) (tree #f (leaf #t) (leaf #t))) ;; (tree #t (leaf #t) (leaf #t)))
Puussa tosiaan on yksi väärinjärjestetty paikka, jossa 8-solmun oikeassa alipuussa on 5.
Tässä vaiheessa muutama huomio. Ensinnäkin cojoin tuottaa lähes poikkeuksetta aika paljon tauhkaa, joka ei ole välttämättä ollenkaan hyödyllistä. Nämä algoritmit vaikuttavat siistimmiltä laiskassa kielessä, jossa komonadinen operaatio (esim. tree-ordered-at-root? :: Tree int -> bool) voi ihan rauhassa päättää, kuinka paljon se oikeasti lueskelee tietorakennetta, ja kieli huolehtii siitä, ettei sitä muodosteta turhaan enempää kuin on tarpeen. Toisekseen, komonadi tosiaan sisältää aina jonkin arvon, joten useimmat sisäänrakennetut tietotyypit (esim. lista, joka voi olla tyhjä) eivät kelpaa komonadeiksi; sen sijaan äärettömät tietorakenteet ovat hyviä kandidaatteja komonadeiksi. Ja vielä kolmanneksi, zipperit tekevät aina komonadisesta laskennasta näppärämpää, koska niiden kautta pääsee käsiksi koko tietorakenteeseen, ei ainoastaan siihen osaan, jonka juuresta lähtee liikkeelle.
Määritetään nyt sitten vielä esimerkiksi listazipperi ja sen komonadioperaatiot. Listazipperin voi nähdä monella tavalla, mutta minä valitsen näkökulman, jossa se on tiettyyn kohtaan kelattu lista ja niinpä esitän sen valitun kohdan arvolla, sitä edeltävien elementtien listalla ja sitä seuraavien elementtien listalla. Nämä edeltävien ja seuraavien elementtien listat saavat olla tyhjiä, koska fokuksessa oleva elementti on kuitenkin aina olemassa. Listaa voi kelata haluamaansa suuntaan ja hakea siitä fokuksessa olevan elementin.
;; lzip :-- LZip a [a] [a]
(define (lzip v prev next) `(lzip ,v ,prev ,next))
(define (lzip? lz) (and (pair? lz) (eq? (car lz) 'lzip)))
(define (val lz) (and (lzip? lz) (cadr lz)))
(define (prevs lz) (and (lzip? lz) (caddr lz)))
(define (nexts lz) (and (lzip? lz) (cadddr lz)))
(define (left lz)
(and (lzip? lz) (not (null? (prevs lz)))
(lzip (car (prevs lz)) (cdr (prevs lz)) `(,(val lz) . ,(nexts lz)))))
(define (right lz)
(and (lzip? lz) (not (null? (nexts lz)))
(lzip (car (nexts lz)) `(,(val lz) . ,(prevs lz)) (cdr (nexts lz)))))
(define example-lzip (lzip 3 '(2 1) '(4 5)))
;; (left example-lzip)
;; ==> (lzip 2 (1) (3 4 5))
Cojoin korvaa listazipperissä olevat kohdat zipperillä itsellään, mutta kyseiseen kohtaan fokusoituna:
(define (iterate-while ready? f arg)
(if (ready? arg) `(,arg . ,(iterate-while ready? f (f arg))) '()))
(define (lzip-cojoin lz)
(lzip lz (iterate-while identity left (left lz))
(iterate-while identity right (right lz))))
;; (lzip-cojoin example-lzip)
;; ==> (lzip (lzip 3 (2 1) (4 5))
;; ((lzip 2 (1) (3 4 5)) (lzip 1 () (2 3 4 5)))
;; ((lzip 4 (3 2 1) (5)) (lzip 5 (4 3 2 1) ())))
(define lzip-counit val)
(define (lzip-map f lz)
(lzip (f (val lz)) (map f (prevs lz)) (map f (nexts lz))))
;; (lzip-map 1+ example-lzip)
;; ==> (lzip 4 (3 2) (5 6))
Mitäs tämmöisellä sitten voi tehdä? No jos niitä laittaa vaikka kaksi sisäkkäin, sillä voi esittää karttaa siitä kohdasta nähden, jossa pelaaja on. Cojoinin avulla voi päivittää karttaa siten, että jokainen kohta voidaan laskea uusiksi ympäristönsä perusteella. (Esimerkiksi joka kohdalle voidaan tarkastaa, onko sen vieressä romahtava vuori, ja muuttaa se kivimurskaksi, jos on.) En tiedä, onko tämä hirveän luonteva tapa hahmottaa pelimaailma, että jokaisesta pisteestä lasketaan erikseen, mitä siinä seuraavalla päivityksellä on. Toisaalta esimerkiksi soluautomaateille se on juuri se, mitä tarvitaan. (http://blog.sigfpe.com/2006/12/evaluating-cellular-automata-is.html)
Mutta asioiden pitämiseksi yksinkertaisena voisin näyttää yksiulotteisen version perinteisestä konvoluutioefektistä, jossa emuloidaan aaltojen leviämistä. Ideana on kohdan ja sen ympäristön perusteella löytää, mihin "suuntaan" veden (tai ilman) pinta (tai paine) on muuttumassa. Jos peräkkäiset kohdat ovat [a, b, c, d, e], niin kohdan c paineeseen lisätään (a + b - 4c + d + e) jaettuna jollain luvulla riippuen, miten voimakas efektistä halutaan.
(define (valp lz) (or (val lz) 0))
(define *ripple-factor* 0.38)
(define (ripple-effect lz)
(+ (val lz) (* (+ (valp (left (left lz))) (valp (left lz)) (* -4 (val lz))
(valp (right lz)) (valp (right (right lz))))
*ripple-factor*)))
;; (ripple-effect example-lzip)
;; ==> 3.0
;; (ripple-effect (right example-lzip))
;; ==> 1.72
(define (ripple lz)
(lzip-map ripple-effect (lzip-cojoin lz)))
;; (ripple example-lzip)
;; ==> (lzip 3.0 (2.0 1.38) (1.72 0.06))
;; (ripple (ripple example-lzip))
;; ==> (lzip 0.4008 (1.278 1.1824) (1.0284 1.7624))
;; (ripple (ripple (ripple (lzip 0 '() '(0 0 0 0 0 3 5 5 3 0 0 0 0 0)))))
;; ==> (lzip 0.164616 ()
;; (0.768208 0.915496 -0.008664 0.765928 2.601784 1.811664 0.980968
;; 0.980968 1.811664 2.601784 0.765928 -0.008664 0.915496 0.768208))
Sitten voisin vielä näyttää, miten näistä listazippereistä saa väsäillyksi sen karttazipperin, jonka mainitsin. Idis on sama kuin taulukoissa, pannaan listazippereitä (kartan "rivejä") toiseen listazipperiin.
;; mapzip :-- lzip lzip a
(define (mzip-value mz) (val (val mz)))
(define mzip-up left)
(define mzip-down right)
(define (mzip-left mz) (lzip-map left mz))
(define (mzip-right mz) (lzip-map right mz))
(define example-map (lzip (lzip 'player '() '(grass grass grass water)) '()
`(,(lzip 'grass '() '(grass grass water water))
,(lzip 'road '() '(grass stone water water))
,(lzip 'road '() '(road road road road))
,(lzip 'stone '() '(stone grass water water)))))
;; (mzip-right example-map)
;; ==> (lzip (lzip grass (player) (grass grass water)) ()
;; ((lzip grass (grass) (grass water water))
;; (lzip grass (road) (stone water water))
;; (lzip road (road) (road road road))
;; (lzip stone (stone) (grass water water))))
;; (mzip-down (mzip-down example-map))
;; ==> (lzip (lzip road () (grass stone water water))
;; ((lzip grass () (grass grass water water))
;; (lzip player () (grass grass grass water)))
;; ((lzip road () (road road road road))
;; (lzip stone () (stone grass water water))))
Sitten komonadiset operaatiot. Tietorakenne on ihan hyödyllinen ilman niitäkin, mutta niillä voi tosiaan tehdä algoritmeja, jotka laskevat maailman uuden tilan näppärästi vanhan perusteella.
(define mzip-counit mzip-value)
(define (mzip-map f mz) (lzip-map (lambda (row) (lzip-map f row)) mz))
;; (mzip-map (lambda (x) (eq? x 'stone)) example-map)
;; ==> (lzip (lzip #f () (#f #f #f #f)) ()
;; ((lzip #f () (#f #f #f #f))
;; (lzip #f () (#f #t #f #f))
;; (lzip #f () (#f #f #f #f))
;; (lzip #t () (#t #f #f #f))))
(define (mzip-cojoin-row mz)
(lzip mz (iterate-while mzip-value mzip-left (mzip-left mz))
(iterate-while mzip-value mzip-right (mzip-right mz))))
(define (mzip-cojoin mz)
(lzip-map mzip-cojoin-row
(lzip mz (iterate-while mzip-value mzip-up (mzip-up mz))
(iterate-while mzip-value mzip-down (mzip-down mz)))))
;; (mzip-cojoin (lzip (lzip 'player '() '(water)) '()
;; (list (lzip 'grass '() '(stone)))))
;; ==> (lzip (lzip
;; (lzip (lzip player () (water))
;; ()
;; ((lzip grass () (stone))))
;; ()
;; ((lzip (lzip water (player) ())
;; ()
;; ((lzip stone (grass) ())))))
;; ()
;; ((lzip
;; (lzip (lzip grass () (stone))
;; ((lzip player () (water)))
;; ())
;; ()
;; ((lzip (lzip stone (grass) ())
;; ((lzip water (player) ()))
;; ())))))
Tässä siis cojoinin tulos on kartta kartoista, tiettyyn kohtaan fokusoituina. Sillä voi sitten toteuttaa vaikkapa veden leviämisen näin:
(define (water-at? mz) (eq? 'water (mzip-value mz)))
(define (maybe-turn-to-water mz)
(if (or (water-at? (mzip-up mz)) (water-at? (mzip-down mz))
(water-at? (mzip-right mz)) (water-at? (mzip-left mz)))
'water
(mzip-value mz)))
(define (spread-water mz)
(mzip-map maybe-turn-to-water (mzip-cojoin mz)))
;; (spread-water example-map)
;; ==> (lzip (lzip player () (grass grass water water)) ()
;; ((lzip grass () (grass water water water))
;; (lzip road () (grass water water water))
;; (lzip road () (road road water water))
;; (lzip stone () (stone water water water))))
Voi ei, silta joutui veden valtaan! :( :(