Mere sjov med SP...

Jeg kunne selvfølgelig ikke lade være med at lege videre med scenariet i Sjov med SP - men lad mig lige starte med to undskyldninger:

1. Det har ikke så meget med SP at gøre, men mere med Scala og scala-fortolkeren (det er fordi, at det første kun er en undskyldning for at tale om det sidste!)
2. Jeg har sidste gang fået regnet afgiften, og ikke efter-afgift-provenuet.

Med det af vejen, så tilbage til mine kode-skriblerier: Man kan jo nemt indse, at der er tale om en konstruktion, som er meget populær indenfor skatte- og afgiftsystemet: Der er forskellige afgiftsatser på forskellige dele af et beløb. Vi ser der bl.a. med registreringsafgiften, og med personbeskatning (bundfradrag, mellem og topskat).

Funktionerne, som jeg er kommet frem til, har flg. signatur: et beløb, en liste af satstrin som tupler med sats og længde på satstrinnet, og så til sidst en sats for "resten". Man kunne formulere satsen for "resten" i listen af satstrin ved et angive det som et sidste satstrin med en meget stor længde; koden vil så blive kortere, men det virkede forkert - jeg gik derfor efter det lidt mere omstændige, men mere eksplicitte.

Nå, nok snak, lad os se noget kode! Først en rekursiv løsning baseret på pattern-matching:

   1:def calcsteps(amountleft: Double, steps: List[(Double,Int)], infrate: Double): Double = 
   2:  steps match {                  
   3:    case (rate, range)::tail => 
   4:      if (amountleft < range) 
   5:        amountleft*rate 
   6:      else 
   7:        range*rate + calcsteps(amountleft-range, tail, infrate)
   8:    case Nil => 
   9:      amountleft * infrate 
  10:  }

Princippet er, at linie 3-7 håndterer første satstrin i listen: kan det rumme hele beløbet, så er vi færdige - ellers regnes dette satstrins bidrag, og funktion kaldes rekursivt i linie 7 med resten af beløbet og resten af satstrinene. Linie 8-9 håndterer, når der ikke er flere satstrin, dvs. "resten".

Men det kan (selvfølgelig?) også gøres på andre måder, f.eks. vha. en "fold-left" operation på satstrin-listen:

   1:def calcstep(status: (Double, Double), step: (Double, Int)):(Double, Double) = {
   2:  val (amountLeft, resultSoFar) = status
   3:  val (rate, limit) = step
   4:  if (amountLeft < limit) 
   5:    (0, resultSoFar + amountLeft*rate) 
   6:  else    
   7:    (amountLeft-limit, resultSoFar + limit*rate)
   8:}
   9:
  10:def calc( amount: Double, steps: List[(Double, Int)], infrate: Double) : Double = {
  11:  val (amountLeft, resultSoFar) = ((amount, 0.0) /: steps) (calcstep)
  12:  resultSoFar + infrate * amountLeft
  13:}

En "fold-left"-operation består i at kalde en funktion med en initialværdi og første element i listen, og gentage kaldet af samme funktion med hhv. resultatet af foregående kald og næste element i listen indtil hele listen er løbet igennem.

Funktionen, som bliver kaldt for hvert trin, er defineret i linie 1-8, og ligner sjovt nok temmeligt meget det, som er vist det rekursive eksempel. Bemærk at tuplerne status og step "pakkes" ud vha. patternmatching i ln. 2 og 3.

Selve foldningen sker i linie 11; for dem, som ikke er vant til syntaksen, så er det "/:"-operatoren, som er en fold-left - tuplen foran er initialværdien, og efter den står listen - dette efterfølges af den funktion, som man ønsker at folde med ... jeg indrømmer, at det virker kryptisk ved første øjekast, men man vender sig foruroligende hurtigt til det!

Hvad er så bedst? Tjo, umiddelbart så vil jeg foretrække den rekursive løsning, og det simpelthen fordi, at den er meget nemmere at forklare - når vi skriver kode, så kommunikerer vi nok en smule "hvordan" til compileren, men i langt højere grad "hvad" med mennesker - både os selv nu og andre senere. Derfor er kode, som er kort og overskuelig, så langt at foretrække.

Men den anden løsning er nu ikke uden fordele:

• I modsætning til den rekursive løsning, som får en kaldstack med en dybde propertionalt med længden af satslisten, så vil foldningen have en stackdybde, som ikke varierer med inputtet.
• Trinnet er eksplicit og kan kvalitetssikres separat
• En folding terminerer naturligt, mens en rekursion skal have (mindst) et termineringstilfælde

Problemet med den dybe kaldstak for den rekursive løsning ville (afhængigt af compilers implementation) kunne forsvinde, hvis den blev formuleret "tail-recursive". Her er en lille udfordring:

1. Hvorfor er funktionen ikke tail-recursive?
2. Hvordan kan man formulere den tail-recursive?
3. Hvorfor ville det (måske) kunne gøre en forskel?