Deklaratív programozás

2. SML kis házi feladat

V1.0, 2006. november 1.
Kisebb javítások: 2007. febr. 22., ápr. 2. HP

A feladat

Adott egy n sorból és m oszlopból álló, téglalap alakú tábla, amelynek a mezőire az (x,y) koordinátájukkal hivatkozunk (1≤x≤n, 1≤y≤m). E tábla altáblájának nevezzük azt az i sorból és j oszlopból álló részét (0≤i≤n, 0≤j≤m), amelyet a bal felső mezőjének - ún. referenciapontjának - a koordinátája azonosít. A tábla és az altáblák bal felső mezőjének (relatív) koordinátája (1,1).

Ha egy i*j méretű altábla referenciapontjának a koordinátája (r,s), akkor teljesülniük kell a következő egyenlőtlenségeknek: 1≤r≤n, 1≤s≤m, 1≤r+i-1≤n, 1≤s+j-1≤m.

Az 1. ábra egy 5*6-os táblát mutat, a 2. ábra pedig ennek egy olyan 3*2 méretű altábláját, amelynek referenciapontja a tábla (2,3) koordinátájú mezője.

  +---+---+---+---+---+---+
  |"a"|"b"|"c"|"d"|"e"|"f"|
  +---+---+---+---+---+---+
  |"0"|"1"|"2"|"3"|"4"|"5"|
  +---+---+---+---+---+---+
  |"N"|"M"|"O"|"P"|"Q"|"R"|
  +---+---+---+---+---+---+
  |"."|","|";"|":"|"<"|">"|
  +---+---+---+---+---+---+
  |"q"|"w"|"e"|"r"|"t"|"y"|
  +---+---+---+---+---+---+

  +---+---+
  |"2"|"3"|
  +---+---+
  |"O"|"P"|
  +---+---+
  |";"|":"|
  +---+---+

1. ábra. Egy tábla (n=5, m=6) 2. ábra. Egy (2,3) referenciapontú 3*2 méretű altábla (i=3, j=2)

Mind a táblát, mind az altáblákat sorfolytonosan, listák listájaként ábrázoljuk.

Írjon olyan SML-függvényt altabla néven, amely kielégíti az alábbi specifikációt:

(* altabla : 'a list list -> (int * int) -> (int * int) -> 'a list list
   altabla tss (r,s) (i,j) = a 'tss' táblának az az 'i'*'j' méretű altáblája,
          amelynek referenciapontja a 'tss' tábla '(r,s)' koordinátájú mezője;
          ha a táblának nincs '(r,s)' mezője vagy '(r,s)' referenciapontú, 'i'*'j'
          méretű altáblája, ezt a függvény az 'Altabla' kivétellel jelezze 
*)

Megoldásában feltételezheti, hogy a függvényt csak helyes táblára alkalmazzuk, azaz olyan táblára, amelynek minden sora egyforma hosszú.

Segédfüggvényeket definiálhat.

A jobbrekurzív függvényekből generált számítási folyamatok kevesebb tárterületet használnak, mint a nemjobbrekurzív függvényekből generáltak, ezért ajánljuk, hogy lehetőleg jobbrekurzív függvényt definiáljon, ám ez nem kötelező, a pontozásba nem számít bele.

Példák

Legyen

val tss = [["a","b","c","d","e","f"],
           ["0","1","2","3","4","5"],
           ["N","M","O","P","Q","R"],
           [".",",",";",":","<",">"],
           ["q","w","e","r","t","y"]];

Az 1. ábrán látható tábla 2. ábra szerinti altábláját adja eredményül a következő függvényalkalmazás:

  altabla tss (2,3) (3,2);
> val it = [["2","3"],["O","P"],[";",":"]] : string list list

A tss tábla (2,3) referenciapontú, 5*2 méretű altáblája nem állítható elő, ezért

  altabla tss (2,3) (5,2);
! Uncaught exception: 
! Altabla

A tss táblának nincs (6,3) mezője, ezért ilyen referenciapontú altáblája sem állítható elő:

  altabla tss (6,3) (3,2);
! Uncaught exception: 
! Altabla

Tudnivalók a beadásról

A kis házi feladat beadását, jóllehet nem kötelező, a tárgy minden hallgatójának nagyon ajánljuk.

A programot az Elektronikus Tanársegéd segítségével Weben keresztül lehet beadni, a HF beadás menüpont alatt.
A beadási határidő 2006. november 16., csütörtök, 24:00.

A vizsgaosztályzat megállapításakor a határidőre beadott, helyesen megoldott kis házi feladatért plusz 1 pont jár.