Kommentarer om poängsättning och rättning

Slarvfel har generellt lett till mindre poängavdrag än tankefel. Sådana slarvfel som ML-systemet direkt skulle upptäcka (smärre syntaxfel o.dyl.) har ofta inte lett till poängavdrag alls. Fel som beror på slarvig genomläsning av uppgiften har oftast lett till större poängavdrag. Missuppfattad fråga behöver inte ha lett till poängavdrag ifall det problem som blivit löst var åtminstonde lika svårt som det avsedda.

Vid rättning har vi försökt att visa på vad som är fel. Är det mycket fel i en uppgift har vi dock inte säkert markerat allt ­ bl.a. därför att det oftast inte är entydigt vad som är "rätt" i så fall.

Poängen på tentan ger ingen absolut sanning utan är ett hjälpmedel vid betygsättningen. Det innebär att alla lösta tentor med poäng som ligger strax under eller över en betygsgräns har granskats en extra gång för att avgöra vilket betyg som är rätt. I några fall har det lett till korrigering av poäng och betyg. Det innebär att om du ligger 0.5-1 poäng under en betygsgräns är chansen för att du kan diskutera upp din poäng över gränsen mycket liten.

Uppgift 1

a

(* addPositives l
   TYPE: int list -> int
   PRE: (ingen)
   POST: Summan av de positiva talen i l.
   EXAMPLES: addPositives [1,~2,3,~4] = 4 *)
(* VARIANT: length l *)
fun addPositives [] = 0
  | addPositives(x::l) = 
      if x < 0 then
        addPositives l
      else
        x + addPositives l

b

1: addPositives [] = 0
2: addPositives [1,~2,3,~4] = 4

Full kodtäckning: 2 (båda fall i testet).
Extremfall: 1 (tom lista)
Typiskt fall: 2.

Uppgift 2

a

Hitta längden av längsta följden av samma tecken i strängen s
Är s tom? JA: Svaret är 0. Klart.
NEJ: Bestäm hur många gånger det första tecknet i s förekommer i en följd i början av s. Kalla det l.
Tag bort de första l tecknen från s.
Hitta längden av längsta följden av samma tecken i resten av strängen s. Kalla resultatet ll.
Svaret är det största av l och ll.

Bestäm hur många gånger tecknet c förekommer i en följd i början av strängen s
Är s tom? JA: Svaret är 0. Klart.
NEJ: Är första elementet i s lika med c? JA: Tag bort första tecknet från s. Räkna hur många gånger tecknet c förekommer i en följd i början av resten av s. Lägg till 1. Klart
NEJ: Svaret är 0. Klart.

b

load "Int";

(* longestRun'(c,s)
   TYPE: char*string list -> int
   PRE: (ingen)
   POST: Antal tecken i början av s som är lika med c.
   EXAMPLES: longestRun'(#"a","aabcccaaaadd") = 2 *)
(* VARIANT: size s *)
fun longestRun'(c,"") = 0
  | longestRun'(c,s) =
      if String.sub(s,0) = c then
        1+longestRun'(c,String.substring(s,1,size s-1))
      else
        0;

(* longestRun s
   TYPE: string list -> int
   PRE: (ingen)
   POST: Längden på den längsta sammanhängande följden av något 
         tecken.
   EXAMPLES: longestRun "aabcccaaaadd" = 4 *)
(* VARIANT: size s *)
fun longestRun "" = 0
  | longestRun s =
      let
        val l = longestRun'(String.sub(s,0),s)
      in
        Int.max(l, longestRun(String.substring(s,l,size s-l)))
      end;

Uppgift 3

a

datatype cart =
           Cart of (string*int*int) list
(* REPRESENTATION CONVENTION:
     Listan innehåller varorna i kundvagnen.
     Första komponenten i varje listelement är varans namn.
     Andra komponenten i varje listelement är varans styckepris i öre.
     Tredje komponenten i varje listelement är antalet av varan.
   REPRESENTATION INVARIANT:
     Styckepris och antal får inte vara negativa. *)

b

datatype cart =
           Cart of int*(string*int*int) list
(* REPRESENTATION CONVENTION:
     Första komponenten är totala priset för varorna i öre.
     Andra komponenten är en listan med varorna i kundvagnen.
     Första komponenten i varje listelement är varans namn.
     Andra komponenten i varje listelement är styckepris varan i öre.
     Tredje komponenten i varje listelement är antal av varan.
   REPRESENTATION INVARIANT:
     Styckepris och antal får inte vara negativa.
     Totalpriset måste vara lika med summan av produkten av antal och 
      styckepris för varje vara i listan. *)

Uppgift 4

a

GTO(fn x=>size x<4,["ett","i","taget"])
if (fn x=>size x<4)"ett" then "ett"::GTO(fn x=>size x<4,["i","taget"]) else GTO(fn x=>size x<4,["i","taget"])
if size "ett" < 4 then "ett"::GTO(fn x=>size x<4,["i","taget"]) else GTO(fn x=>size x<4,["i","taget"])
if 3 < 4 then "ett"::GTO(fn x=>size x<4,["i","taget"]) else GTO(fn x=>size x<4,["i","taget"])
if true then "ett"::GTO(fn x=>size x<4,["i","taget"]) else GTO(fn x=>size x<4,["i","taget"])
"ett"::GTO(fn x=>size x<4,["i","taget"])
"ett":: if (fn x=>size x<4)"i" then "i"::GTO(fn x=>size x<4,["taget"]) lse GTO(fn x=>size x<4,["taget"])
"ett":: if size "i" <4 then "i"::GTO(fn x=>size x<4,["taget"]) else GTO(fn x=>size x<4,["taget"])
"ett":: if 1 <4 then "i"::GTO(fn x=>size x<4,["taget"]) else GTO(fn x=>size x<4,["taget"])
"ett":: if true then "i"::GTO(fn x=>size x<4,["taget"]) else GTO(fn x=>size x<4,["taget"])
"ett"::"i"::GTO(fn x=>size x<4,["taget"])
"ett"::"i"::if(fn x=>size x<4)"taget" then "taget"::GTO(fn x=>size x<4,[]) else GTO(fn x=>size x<4,[])
"ett"::"i"::if size "taget" <4 then "taget"::GTO(fn x=>size x<4,[]) else GTO(fn x=>size x<4,[])
"ett"::"i"::if 5 <4 then "taget"::GTO(fn x=>size x<4,[]) else GTO(fn x=>size x<4,[])
"ett"::"i"::if false then "taget"::GTO(fn x=>size x<4,[]) else GTO(fn x=>size x<4,[])
"ett"::"i"::GTO(fn x=>size x<4,[])
"ett"::"i"::[]
"ett"::["i"]
["ett","i"]

b

(* GTO(p,l)
   TYPE: ('a->bool)*'a list -> 'a list
   PRE: (inget)
   POST: En lista med de element från l som gör p sann
         (i samma ordning som i l)
   EXAMPLES:
     GTO(fn x=>size x<4,["ett","i","taget"]) = ["ett,"i"] *)
(* VARIANT: length l *)

c

Mangan "Great Teacher Onizuka".

Uppgift 5

• Abstraktion innebär att man döljer eller bortser någon konkret egenskap eller detalj för slippa ta hänsyn till den eller för att vara mera generell.
• Abstraktion kan användas för att göra program mer lätta att förstå eller ändra, eller för att lättare återanvända kod.
• En nackdel med abstraktion är att det kan göra programmet större eller mindre effektivt.
• Definitionsabstraktion (använda ett namn i stället för ett konkret värde), funktionsabstraktion (göra ett uttryck oberoende av specifika data), dataabstraktion (göra programmet oberoende av hur data är representerat).

Uppgift 6

fun addPositives l = 
  foldr (fn(x,y) => if x < 0 then y else x+y) 0 l

Uppgift 7

a

b binds först till 4.
foo 4 anropas. När let-uttrycket i foo beräknas binds b till 8. Detta skuggar den tidigare bindningen. (Notera att a nu är bunden till 4 eftersom a är argumentnamn i foo och foo anropades med argument 4.) När funktionen avslutas försvinner den nya bindningen.
foo b = 12, b=4.

b

Referensen skapas med innehållet 4.
foo(ref 4) anropas. I foo ändras innehållet i b till 8. (Notera att a och b nu är namn på samma referens eftersom a är argumentnamn i foo och bands om till värdet av b vid anropet.)
foo b = 16, !b=8.

Uppgift 8

(* countMatchingLines(f,s)
   TYPE: string*string -> int
   PRE: En fil med namn f skall finnas och vara läsbar.
   POST: Antal rader i filen med namn f som är lika med s.
   SIDE-EFFECTS: Läser från filen f.
   EXAMPLES: countMatchingLines("foo","kalle") = 2
             om foo innehåller raden "kalle" två gånger.
*)
fun countMatchingLines(f,s) =
  let
    (* cml' is
       TYPE: instream -> unit
       PRE: is är en öppen inström.
       POST: Antal återstående rader i strömmen is som är lika med s.
       SIDE-EFECTS: Läser från strömmen is. Stänger sedan is.
    *)
    (* VARIANT: Antal rader kvar att läsas från strömmen is. *)
    fun cml' is =
      if TextIO.endOfStream is then
        (TextIO.closeIn is; 0)
      else
        if TextIO.inputLine is = s^"\n" then
            1+cml' is
          else
            cml' is
  in
    cml'(TextIO.openIn f)
  end;