Spenn deg fast for en liten reise inn i funksjonelle trestrukturer og da spesifikt rosetrær. Du vil også få en lyninnføring i hvordan glidlåser kan være nyttige for traversering og modifisering av trestrukturer. For at vi ikke skal kunne jukse med mutering og annet sideeffektfanteri bruker vi eksempler i Elm.

Hva er det vi skal lage

Vi har en søkeside for å søke i det norske regelverket. Filteret vi skal lage i dette eksemplet lar deg filtrere på en hierarkisk struktur av rettskilder. Selve søket foregår på backend via en søkemotor og er utenfor scope av det vi skal lage.

Noen krav vi må sørge for å tilfredstille i filterkoden vår er;

  • Fra backend får vi kun antall på løvnoder, vi skal vise aggreggerte tall oppover i rettskildetreet.
  • Dersom du skrur på filter for en node med etterfølger, skal ingen av dens etterfølger være skrudd på
  • Dersom du skrur på filter for en node med forfedre, skal ikke dens forfedre være skrudd på
  • Du har lov til å skru på filter for flere noder på samme nivå (altså søskennoder)

Trær i Elm

Rettskildehierarkiet er en trestruktur med flere nivåer og mange noder på hvert nivå. Det er et multiway tree dvs et tre hvor en node kan ha 0-n undernoder. En vanlig måte man kan representere det på i Elm er som følger;

type Tree a = Leaf a | Node (List Tree a)

Et tre er enten en løvnode eller en node som kan ha et ubegrenset antall sub-trær.

Alternativt kan man uttrykke et multiway tre på denne måten:

type Tree a = Tree a (List (Tree a))

Her beskriver vi tretypen som en slags tuppel. Første parameter er innholdet i selve trenoden, andre parameter er en liste med undernodene. Dersom listen er tom, er det en løvnode!

For å traversere / modifisere denne strukturen, må vi lage hjelpefunksjoner. Det høres litt for slitsomt ut selvom det hadde vært skøy. Heldigvis er det mange andre som har tatt seg bryet å dele biblioteker vi kan lene oss på. Det biblioteket vi skal benytte oss av er; gampleman/elm-rosetree. Dette benytter seg av den sistnevne representasjonen av et multiway tre.

Hvordan summere opp antall fra løvnoder ?

Det første vi begynner med er å finne ut hva vi ønsker å holde på av data i nodene våre (representert ved typevariabelen a for tretypen).

type alias NodeData =
    { label: String
    , count: Int -- Denne er bare satt på løvnoder fra backend
    }

Vi får sikkert datastrukturen fra backend som en json, men la oss manuelt konstruere et lite eksempeltre.

example =
    Tree.tree (NodeData "Rettsavgjørelser" 0)
        [ Tree.singleton (NodeData "Tingretter" 5)
        , Tree.tree (NodeData "Lagmannsretter" 0)
            [ Tree.singleton (NodeData "Lagmannsretter - straff" 7)
            , Tree.singleton (NodeData "Lagmannsretter - sivile" 2)
            ]
        ]

Gitt dette eksemplet, kan vi få summert opp ved følgende hendige funksjon:

exampleCounted =
    Tree.sumUp
        identity
        (\node children -> {node | count = children |> List.map .count |> List.sum } )
        example


-- sumUp : (a -> b) -> (a -> List b -> b) -> Tree a -> Tree b
-- første parameter er en funksjon som kan transformere løvnoder. Den har vi ikke behov for
   -- `Identity` funksjonen i Elm  returner bare hva den får inn!
-- andre parameter er en funksjon som sender inn selve noden og en liste med dens direkte undernoder.
-- Vi lager en anonym funksjon som summerer opp antall i undernoder og tilordner det til `count` i denne noden

Resultatet blir et tre som er tilsvarende:

    Tree.tree (NodeData "Rettsavgjørelser" 14)
        [ Tree.singleton (NodeData "Tingretter" 5)
        , Tree.tree (NodeData "Lagmannsretter" 9)
            [ Tree.singleton (NodeData "Lagmannsretter - straff" 7)
            , Tree.singleton (NodeData "Lagmannsretter - sivile" 2)
            ]
        ]

Dette var jo ikke så vanskelig. Spesielt siden det var en funksjon som nærmest var laget for formålet. Juks?

Hvordan kan vi tilfredstille bryterkravene ?

Konseptuelt er det jo ikke så vanskelig;

  1. Først finner du noden som skal slås på
  2. Flipp brytertilstand på noden
  3. Dersom noden ble skrudd på;
    1. Skru av alle forfedre-noder
    2. Skru av alle etterkommer-noder

Vi kan jo ikke mutere treet, men pkt 1. og 2. kunne man enkelt løst med f.eks en map funksjon. Pkt 3 er litt verre, vi ønsker jo å modifisere noden, deretter modifisere forfedre og tilslutt modifisere alle etterkommere. For hver modifikasjon må vi holde orden på hvor vi er i treet og til enhver tid sende modifisert tre videre til neste funksjon.

Hadde det ikke vært digg om man hadde en måte å traversere treet på (/og evt modifisere noder), som til enhver tid holdt orden på hvor du var i treet ? Det er her Zippers kommer inn i bildet.

Kort intro til glidlåser

Med en zipper implementasjon kan du fokusere på en node, og ved hjelp av funksjoner enkelt og effektivt flytte fokus til andre noder vha funksjoner. Du kan også typisk funksjonelt modifisere de underliggende nodene og beholde fokus, eller alternativ flytte fokus dersom det gir mest mening. Du åpner typisk glidlåsen ved å sende inn et tre, og etter at du er ferdig med å traversere/modifisere lukker du glidlåsen og får et tre tilbake.

Zippers fungerer på andre datastrukturer enn tre-strukturer (f.eks lister), men det er en annen historie

Zippers API’et til elm-rosetree tilbyr funksjoner for å traversere et tre ved en dybde-først strategi. Det har hendige basisfunksjoner som f.eks forward, backward og parent.

Følgende illustrer hvordan treet navigeres (dvs vi flytter fokus) via funksjonen forward: Forward

Hvordan vet vi at vi har nådd slutten da?

forward : Zipper a -> Maybe (Zipper a)

Alle de tre overnevnte (og flere andre) navigasjonsfunksjonene returnerer en Maybe type. Dersom du får Just a fikk du flyttet fokus og får du Nothing tilbake ved du at du er ved veis ende.

En liten tilstandsutvidelse

Det første vi gjør er å utvide typen for nodedata med et tilstandsfelt for bryter

type alias NodeData =
    { label: String
    , count: Int -- Denne er bare satt på løvnoder fra backend
    , isOn: Bool -- Er bryter på eller av
    }

For å opprette et eksempeltre, må vi legge inn det ekstra feltet. La oss si at ingen noder er skrudd på enda.

example =
    Tree.tree (NodeData "Rettsavgjørelser" 0 False)
        [ Tree.singleton (NodeData "Tingretter" 5 False)
        , Tree.tree (NodeData "Lagmannsretter" 0 False)
            [ Tree.singleton (NodeData "Lagmannsretter - straff" 7 False)
            , Tree.singleton (NodeData "Lagmannsretter - sivile" 2 False)
            ]
        ]

Finne en node i treet vårt og sette fokus

    maybeZipperNode =
        Zipper.fromTree example
            |> Zipper.findFromRoot (\node -> node.label == "Lagmannsretter")


    case maybeZipperNode of
        Just zipperNode ->
            -- Fokus er nå på "Lagmannsretter" noden, da kan vi begynne med moroa

        Nothing ->
            -- DOH, håndtere at noden ikke ble funnet. Skal ikke kunne skje, men gjorde det lell osv...

Gitt fokus på en node, hvordan oppdatere alle dens forfedre?

Vi vet jo ikke hvor mange nivåer opp det er, så vi trenger en måte å iterere til vi er på toppen mens vi modifiserer! Det ser ikke ut som API’et vi bruker har akkurat det vi ønsker oss. Da får vi snekre sammen noe selv.

-- Hjelpefunksjon for å oppdatere alle forfedre inklusive rotnoden

updateParents : (a -> a) -> Zipper a -> Zipper a
updateParents mapFn zipper =
    updateNodeWhen Zipper.parent mapFn zipper


-- Hjelpefunksjon for å navigere til og oppdatere en node så lenge `zipperNavFn` ikke returnerer `Nothing`
-- zipperNavnFn argumentet har en signatur som matcher typiske navigasjonsfunksjoner som `parent`, `forward` og `backward`

updateNodeWhen : (Zipper a -> Maybe (Zipper a)) -> (a -> a) -> Zipper a -> Zipper a
updateNodeWhen zipperNavFn mapFn zipper =
    case zipperNavFn zipper of
        Nothing ->
            zipper

        Just newZipper ->
            let
                updZipper =
                    Zipper.updateLabel mapFn newZipper
            in
            updateNodeWhen zipperNavFn mapFn updZipper

La oss illustrere vår flunkende nye funksjon i bruk

    maybeZipperNode =
        Zipper.fromTree example
            |> Zipper.findFromRoot (\node -> node.label == "Lagmannsretter")


    case maybeZipperNode of
        Just zipperNode ->
            -- Fokus er nå på "Lagmannsretter" noden, sett alle foreldre til **av**
            updateParents (\node -> { node | isOn = False }) zipperNode



        Nothing ->
            -- DOH, håndtere at noden ikke ble funnet. Skal ikke kunne skje, men gjorde det lell osv...

Gitt fokus på en node, hvordan oppdatere alle dens etterkommere ?

Funksjonen toTree lar deg lage et tre av en fokusert node og dens etterkommere. Funksjonen replaceTree lar deg erstatte et en fokusert node med et ny (nytt subtre). Med litt triksing så vår vi det greit til.

    maybeZipperNode =
        Zipper.fromTree example
            |> Zipper.findFromRoot (\node -> node.label == "Lagmannsretter")


    case maybeZipperNode of
        Just zipperNode ->
            -- Fokus er nå på "Lagmannsretter" noden
            let
                -- Flipp bryter for funnet node, sett alle andre i dette sub-treet til av
                replacement =
                    Zipper.tree zipperNode
                        |> Tree.map (\node ->
                            if node.label == "Lagmannsretter" then
                                {node | isOn = not node.isOn}
                            else
                                {node | isOn = False }
                           )
            in
            Zipper.replaceTree replacement zipperNode



        Nothing ->
            -- DOH, håndtere at noden ikke ble funnet. Skal ikke kunne skje, men gjorde det lell osv...

En funksjon som syr det hele sammen

Vi har nå alle byggeblokkene som skal til for å flippe brytere i treet vårt. La oss lage en fet funksjon:

toggleNode : String -> Tree NodeData -> Tree NodeData
toggleNode label nodeTree =
    case Zipper.findFromRoot (\node -> node.label == label) (Zipper.fromTree nodeTree) of
        Nothing ->
            nodeTree

        Just zipperNode ->
            let
                setOff node =
                    { node | isOn = False }

                -- Oppdaterte nodedata med flippet bryter
                updNodeData =
                    Zipper.label zipperNode
                        |> \node -> { node | isOn = not node.isOn }
            in
                if updNodeData.isOn then
                    zipperNode
                        -- 1. Slå av for alle noder i sub-treet til funnet fokusert node
                        |> Zipper.replaceTree (Zipper.tree zipperNode |> Tree.map setOff)
                        -- 2. Fokus er fortsatt på funnet node, bytt dennes nodedata hvor bryter er flippet
                        |> Zipper.updateLabel (always updNodeData)
                        -- 3. Slå av bryter for alle forfedre
                        |> updateParents setOff
                        -- 4. Lukk igjen glidlåsen og returner oppdatert tre
                        |> Zipper.toTree
                else
                    Zipper.updateLabel (always updNodeData) zipperNode
                        |> Zipper.toTree

Suksess

Vi kom frem til en veldig enkel måte å aggreggere antall i filter hierarkiet. Det krevde litt mer innsats å implementere bryterlogikken for de fiffige kravene, men det er jo artig med en utfordring også ?

Brytere in action: