Funkcionális programozás gyakorlat

9. feladatsor

Beadandó

Definiáld a bináris számokat mint bitek listáját (type kulcsszóval), ahol a bit egy algebrai adatszerkezet Zero és One konstruktorokkal (data kulcsszóval).

A listában az alacsonyabb helyi értékű bitek legyenek elöl.

[]                  :: Binary -- értéke 0
[One]               :: Binary -- értéke 1
[Zero, One]         :: Binary -- értéke 2
[One,  One]         :: Binary -- értéke 3
[Zero, Zero,  One]  :: Binary -- értéke 4

(folyt.)

Beadandó

Definiáld a rákövetkező és az összeadás függvényt is a típusra.

succ :: Binary -> Binary
add  :: Binary -> Binary -> Binary

succ [One, One]               ↦   [Zero, Zero, One]
[Zero, One] `add` [One, One]  ↦   [One, Zero, One]

Eszköz

A type kulcsszóval típusszinonímát lehet bevezetni. A szinoníma bárhol helyettesítheti a típust.

import Prelude hiding (String)

type String = [Char]

['a','b'] :: String

Feladat

Definiáld a Year típust mint egész számot.

1998 :: Year

Definiáld a sakktábla mezőit mint karakter/egész párokat.

('A', 8) :: Square

Eszköz

A típusszinonímákban típusparaméterek is szerepelhetnek.

type ListList a = [[a]]

[[1,2],[3],[],[4,5]] :: ListList Int

Feladat

Definiáld a predikátumok típusát (logikai értékű függvényeket).

isAlpha :: PredicateOn Char
even    :: Integral a => PredicateOn a

Eszköz

Új adattípust a data kulcsszóval lehet létrehozni. Ez algebrai adattípus: a lehetséges értékeket konstruktorokkal lehet leírni.

import Prelude hiding (Left, Right)

data Direction = Left | Right

Left  :: Direction
Right :: Direction

Eszköz

Algebrai adattípus készítésekor hasznos lehet, ha automatikusan létrejön néhány művelet. Műveletek csoportjait típusosztályok írják le, ezekből származtathatjuk az adattípust.

data Direction = Left | Right
                    deriving (Eq, Show)

Eszköz

Gyakori típusosztályok műveletekkel:

• Show: megjelenítés (ez kell pl. a ghci-ben való megjelenítéshez)
• Eq: egyenlőségvizsgálat (==, !=)
• Ord: rendezés (<, <=, >, >=, min, max)
• Enum: a konstruktorok között sorrend értelmezett (pred, succ, toEnum, fromEnum)
• Num: számok (+, -, *)

A típusosztályok kapcsolatban vannak egymással, pl. az Ord magában foglalja az Eq-t.

Eszköz

A Bool is algebrai adattípus.

data Bool
    = False
    | True
        deriving (Eq, Ord, Show)

Feladat

Tükrözz egy megadott irányt.

mirror :: Direction -> Direction

mirror Left   ↦   Right

Számold meg egy irányokat tartalmazó listában a balra irányokat.

numOfLefts :: [Direction] -> Int

numOfLefts [Left,Right,Left,Left]  ↦  3

Feladat

Definiáld az Answer típust az alábbi három elemmel.

No    :: Answer
Maybe :: Answer
Yes   :: Answer

Feladat

Definiáld a logikai "ÉS" és "VAGY" függvényeket az Answer típusra. (Több megoldás is lehetséges.)

infixr 3 &&&
infixr 2 |||
(&&&) :: Answer -> Answer -> Answer
(|||) :: Answer -> Answer -> Answer

Az infixr jelölés azt adja meg, hogy az operátorok jobbra kötnek, és a precedenciaszintjük 3 illetve 2 (az előbbi erősebb).

Eszköz

Az algebrai adattípusban a konstruktoroknak lehetnek típusparamétereik.

data MaybeInt = NoInt | JustInt Int

NoInt      :: MaybeInt
JustInt 13 :: MaybeInt

Algebrai adattípus és egy konstruktorának a neve egybeeshet.

data Harom = Harom Int Int Int

Eszköz

A Peano-számok a természetes számok egyfajta leírása.

data Nat
    = Zero          -- nulla
    | Succ Nat      -- rákövetkező
        deriving (Eq, Show)

Feladat

Definiáld az alábbi Peano-konstansokat és műveleteket.

one :: Nat
two :: Nat

add :: Nat -> Nat -> Nat
mul :: Nat -> Nat -> Nat

one `add` one  ==  two
two `mul` two  ==  two `add` two

Feladat

Definiáld a biztonságos div függvényt.

safeDiv :: Int -> Int -> MaybeInt

10 `safeDiv` 0    ↦    NoInt
10 `safeDiv` 4    ↦    JustInt 2

Eszköz

A konstruktorok paramétereiben nem csak konkrét típusok lehetnek, hanem típusváltozók is. Ezeket a típus leírásában is fel kell tüntetni.

import Prelude hiding (Maybe, Nothing, Just)

data Maybe a
    = Nothing
    | Just a

Nothing  :: Maybe a
Just 'x' :: Maybe Char

Feladat

Definiáld a biztonságos fejelem függvényt.

safeHead :: [a] -> Maybe a

safeHead []         ↦    Nothing
safeHead [1..10]    ↦    Just 1

Feladat

Definiáld a diszjunkt unió adatszerkezetet.

import Prelude hiding (Either, Left, Right)

Left  'x'  ::  Either Char a
Right 'x'  ::  Either a    Char
Right True ::  Either a    Bool

[Left 'x', Left 'z', Right True, Left '?']
    :: [Either Char Bool]

Feladat

Definiáld a kétdimenziós, pontokat.

1. Mindkét koordinátájuk legyen egész szám.
2. Mindkét koordinátájuk legyen tetszőleges szám.

Definiáld az alábbi műveleteket (a típusaik az első esetre vonatkoznak).

mirrorX :: Point -> Point     -- x tengelyre tükrözés
mirrorO :: Point -> Point    -- origóra tükrözés
mirrorP :: Point -> Point -> Point -- pontra tükrözés
translate :: (Int, Int) -> Point -> Point -- eltolás

Feladat

Definiálj saját pár típust. A pár két komponense tetszőleges típusú lehessen.

Tuple2 'a' True  ::  Tuple2 Char Bool

Definiálj saját hármas típust.

Tuple3 'a' True "xx"  ::  Tuple3 Char Bool String

Megjegyzés: beépített tetszőleges n-es:

('a', True, "xx", 2.4, 5)
    ::  (Char, Bool, String, Double, Int)

Feladat

Definiálj saját lista típust.

infixr 5 Cons

Nil                          ::  List a
'x' `Cons` Nil               ::  List Char
True `Cons` False `Cons` Nil ::  List Bool

Feladat

Definiáld az égtájakat.

East  :: CardinalPoint
West  :: CardinalPoint
North :: CardinalPoint
South :: CardinalPoint

Definiáld a 90 fokos elfordulást jobbra és balra, és a megfordulást.

turnRight :: CardinalPoint -> CardinalPoint
turnLeft  :: CardinalPoint -> CardinalPoint
turnBack  :: CardinalPoint -> CardinalPoint