---------- 1. Kérdés ---------- Valaki el tudná mondani, hogy az alábbi kifejezésben mi x típusa? val x = let val xs = List.filter Char.isAlpha [#"1", #"3"] in xs end ---------- Válasz egy hallgatótól ---------- A filter ('a ->bool) ->'a list ->'b list, azaz, ha adsz neki egy függvényt, ami bool típusú (ld. Char.isAlpha a példában), ő ezt alkalmazza a megadott 'a listára (jelen esetben [#"1",#"3"]), tehát kiválogatja a lista azon elemeit, amire a megadott bool függvény igaz. Egy 'b list-tel tér vissza. Mivel itt egy 2 elemű karakterekből álló lista van megadva, ezért xs char list, és x is ezzel egyenlő. ---------- Válasz, kiegészítés az oktatótól ---------- A List.filter típusa helyesen (ellenőrizhető pl. az mosml-lel): List.filter: ('a ->bool) ->'a list ->'a list Vagyis az eredménylistának ugyanaz a típusa, mint az argumentumként átadott listának. A Char.isAlpha függveny akkor ad igazat eredményül, ha az argumentuma betű (az angol abécé kis- vagy nagybetűje). Most List.filter Char.isAlpha-t a kételemű [#"1", #"3"] lista elemeire alkalmazza. A két elem közül egyik sem betű, ezért a függvényalkalmazás eredménye az üres lista, a típusa pedig azonos a [#"1", #"3"] lista típusával, azaz char list. Vagyis a lokális kifejezésen belül xs = [] : char list. A "let val xs = ... xs end" kifejezés xs ertékét adja eremenyül, es ezt az értéket veszi fel x is. x értéke tehát [], a típusa pedig char list. ---------- 2. Kérdés ---------- Az alábbi feladattal kapcsolatban kérnék segítséget: Írj az alábbi fejkommentet kielégítő SML-függvényt! Segítségül példát is mutatunk az alkalmazására. (* nthFmBehind(i, xs) = xs hátulról számított i-edik eleme, ahol egy lista utolsó elemének a sorszáma 1 PRE: i > 0 nthFmBehind : (int * 'a list) -> 'a *) Példa: nthFmBehind (3, ["w","x","y","z"]) = "x" A probléma az, hogy ha nem kezelem le az xs = [] esetet, akkor nem enged tovább, ha lekezelem, akkor viszont a visszaadott érték nem megfelelő, hiszen nem tudom visszaadni a listabeli elem típusát. Mi a megoldás? ---------- Válasz az oktatótól ---------- A korrekt megoldásnak kivételt (exception) kell jeleznie. Ez lehet a hasonló esetekben jelzett Empty (vö. List.hd, List.tl) vagy a Subscript (vö. List.nth, List.take, List.drop), vagy egy erre a célra deklarált saját kivételnév (ezzel azonban eddig még nem foglalkoztunk). (1) Az egyik gyorsan megírható változat az alábbi, amely az i = 0 és az i > length xs speciális eseteket is automatikusan kezeli, a List.nth : 'a list * int -> 'a és a length : 'a list -> int függvényt alkalmazza. List.nth alkalmazásához tudni kell, hogy a lista fejének (bal szélső elemének) 0 az indexe. fun nthFmBehind (i, xs) = List.nth(xs, length xs - i) Példák: - nthFmBehind (3, ["w","x","y","z"]); > val it = "x" : string - nthFmBehind (5, ["w","x","y","z"]); ! Uncaught exception: ! Subscript - nthFmBehind (1, []); ! Uncaught exception: ! Subscript (2) Egy másik gyorsan megírható változat a List.nth mellett a rev-et alkalmazza. fun nthFmBehind (i, xs) = List.nth(rev xs, i-1) Az mosml válaszai az előző példákban bemutatottakkal azonosak. (3) Végül következzen egy, a List.nth függvényt nem alkalmazó változat. fun nthFmBehind (_, []) = raise Empty | nthFmBehind (i, xs) = let fun nFmB (0, z::zs) = z | nFmB (i, _::zs) = nFmB(i-1, zs) | nFmB (_, []) = raise Subscript in nFmB(i-1, rev xs) end Példák: - nthFmBehind (3, ["w","x","y","z"]); > val it = "x" : string - nthFmBehind (5, ["w","x","y","z"]); ! Uncaught exception: ! Subscript - nthFmBehind (0, ["w","x","y","z"]); ! Uncaught exception: ! Subscript - nthFmBehind (0, []); ! Uncaught exception: ! Empty ---------- 3. Kérdés ---------- Meg tudná valaki mondani, hogy az alábbi kifejezésben mi az x típusa? Mert nekem nem sikerült megoldani. val x = let val xs = List.find not [false, true] in xs end Nekem úgy tűnik, hogy az xs bevezetése csak megtévesztés, hiszen a végén x-nek xs lesz az értéke. A "find" eljárás meg elvileg visszaadja a "false" értéket, mert arra ad igazat a "not" fuggvény, tehát az xs értéke (és ezáltal x is) false. Nem? Akkor most ez bool típusú? ---------- Válasz egy hallgatótól ---------- Az sml-könyv szerint (ld. a függelékben) az van, hogy ilyenkor a find (amikor talált olyan listaelemet, amire az alkalmazott - itt not - függvény igaz), akkor SOME ... (ahol ... a talált elem) a visszaadott eredmény. Ha nem talált volna ilyet, akkor NONE-t ad vissza. Na most, SOME típusa 'a option, tehát a válasz a feladatra: bool option. ---------- Válasz, kiegészítés az oktatótól ---------- Az xs bevezetése valóban felesleges (nevezhetjük megtévesztésnek is), mivel let val xs = List.find not [false, true] in xs end = List.find not [false, true] A fenti válasz helyes: x értéke false, a típusa pedig bool option. A magyarázat nem elég pontos. Az előadáson a datatype deklarációt és az Option könyvtárat tárgyalni fogjuk, az alábbi válasz akkor válik világossá. (E két témakört nem kell tudni a zárthelyire.) List.find típusa és alkalmazásának eredménye, továbbá SOME és NONE típusa helyesen a következő. List.find : ('a -> bool) -> 'a list -> 'a option Ha a List.find-ot egy 'a -> bool típusú p predikátumra alkalmazzuk, akkor olyan függvényt ad eredményül, amelyet egy 'a típusú elemekből álló xs listára alkalmazhatunk. Ha az xs-nek nincs a p-t kielégítő eleme (azaz olyan eleme, amelyre p-t alkalmazva true eredményt kapnánk), akkor a függvényalkalmazás eredménye NONE lesz. Ha az xs-nek van egy vagy több p-t kielégítő eleme, akkor - az xs balról számított első ilyen elemét x-szel jelölve - az eredmény SOME x lesz. SOME ún. adatkonstruktorfüggvény, a típusa: 'a -> 'a option NONE ún. adatkonstruktorállandó, a típusa: 'a option ---------- 4. Kérdés ---------- Mi az f típusa? 1. fun f x y z = x z y megoldás: ('a -> 'b -> 'c) -> 'b -> 'a -> 'c 2. fun f (x,y) = y (x+1, 2.0) megoldás: int * (int* real->'a) -> 'a 3. fun f x y = y (x y) megoldás: (('a->'b)->'a)->('a->'b)->'b Szóval miért ezek a megoldások? Meg egyébként is. hogy kell az ilyet általánosságban megoldani? ---------- Válasz egy hallgatótól ---------- A második példa: Mivel az y-t alkalmazzuk (x+1,2.0)-ra, ezért mivel x int (mert hozzá tudunk adni 1-et, ami pedig int), és a 2.0 pedig real, így y olyan, hogy int*real az argumentuma. És ebből egy ismeretlen típust csinál, amit hívhatunk 'a-nak. Tehát: f típusa: int*(int*real->'a). És mivel mi y-t alkalmazzuk a megfelelő parametérekkel, ezért az eredmény 'a lesz (hiszen y ilyet ad vissza). ---------- Válasz, kiegészítés az oktatótól ---------- Egy értékdeklarációban az értékeket jelölő nevek (függvényjelek, változók, argumentumok) típusának meghatározását a definiáló kifejezés (azaz a deklarációban az egyenlőségjel jobb oldalán álló) kifejezés elemzésével kezdjük. 1. fun f x y z = x z y megoldás: ('a -> 'b -> 'c) -> 'b -> 'a -> 'c A definiáló kifejezés itt: x z y. x függvényalkalmazási pozícióban áll, mivel egy (rész)kifejezés első eleme és szóköz választja el egy másik névtől, z-től, amely ily módon az x argumentuma. Az SML-ben általában mohó kiértékelést alkalmaz. Ez most azt jelenti, hogy az x függvényt mohón alkalmazza az argumentumára, z-re. Az (x z) függvényalkalmazás eredménye is függvényérték, mert az (x z) részkifejezést ugyancsak szóköz választja el egy újabb névtől, y-tól, amely tehát az (x y) argumentuma. A kifejezés kiértékelésének precedenciaszabályai szerint x z y = (x z) y <> x (z y). (A szóköz mellett a többi formázó karakternek és a zárójeleknek is hasonló szeparátor-szerepe van. Így x z y helyett (x z)y is írható.) Amikor egy kifejezés típusát az SML-értelmező levezeti, akkor a lehető legtöbb információt hámozza ki a kifejezés elemeiből. Nekünk is arra kell törekednünk, hogy a lehető legtöbbet tudjuk meg egy kifejezésről. x-ről tudjuk már, hogy függvény, méghozzá részlegesen alkalmazható függvény. Azt is látjuk, hogy politípusú, hiszen egyetlen típusállandó vagy többszörösen terhelhető függvénynév sem fordul elő a függvénydefinícióban. z-ről és y-ról csak annyit tudunk, hogy argumentumok, többet nem, így a típusukat egy-egy típusváltozóval jelöljük ('a-val, ill. 'b-val). Az x z y függvényalkalmazás eredményéről sem tudunk semmi közelebbit, a típusát tehát egy újabb típusváltozóval, 'c-val jelöljük. A részkifejezések: z y -- -- z : 'a, y: 'b, x: 'a -> 'b -> 'c Most már könnyű felírni az f típusát, hiszen mindhárom argumentumának típusát ismerjük. Az x-hez hasonlóan az f is részlegesen alkalmazható és politípusú. A fun szócska után álló f x y z = x z y kifejezés egyúttal egyenlőséget is kifejez, az f x y z függvényalkalmazásnak és az x z y függvényalkalmazásnak ugyanaz az érték az eredménye (és így természetesen a típusa is, amit most 'c-val jelöltünk). Most már mindent tudunk f-ről. Precedenciaokok miatt a típuskifejezés egyes részkifejezéseit zárójelbe kell tenni. x y z ---------------- -- -- f : ('a -> 'b -> 'c) -> 'b -> 'a -> 'c 2. fun f (x,y) = y (x+1, 2.0) megoldás: int * (int* real->'a) -> 'a A hallgatói válasz jó. Kicsit másképpen, pontosabban megfogalmazva: Az y-t az (x+1, 2.0) párra alkalmazzuk a definíció jobb oldalán. x int típusú, mert az int típusú 1-hez adjuk hozzá, a 2.0 típusa pedig real. Az y-nak tehát az int * real típusú pár az argumentuma. Az y(x+1, 2.0) függvényalkalmazás eredményéről több nem tudható meg, a típusát jelöljük hát 'a-val. És ebből egy ismeretlen típust csinál, amit hívhatunk 'a-nak. Ezzel y : int * real -> 'a x y --- ---------=------ f : int * (int * real->'a) -> 'a 3. fun f x y = y (x y) megoldás: (('a->'b)->'a)->('a->'b)->'b A levezetés a fentiekhez hasonló. A részeredmények és a végeredmény, rövid magyarázattal: y-t az (x y) függvényalkalmazás eredményére alkalmazzuk, az eredmény típusát jelöljük 'a-val. Ezzel y : 'a ->'b A zárójelezés miatt az x is függvényalkalmazási pozícióban van, y-ra alkalmazzuk. Eredményének, mint az előbb láttuk, 'a típusúnak kell lennie, hiszen az y-t alkalmazzuk rá. x : ('a -> 'b) -> 'a Most már könnyű felírni f típusát: f : (('a -> 'b) -> 'a) -> ('a ->'b) -> -'b