Funkcionális programozás gyakorlat

10. feladatsor

Beadandó feladat

Implementáld a Nat típusra a hatványozást. Ehhez ne alakítsd át a számot belső ábrázolású egésszé.

power :: Nat -> Nat -> Nat

power (toNat 2) (toNat 2)
          ↦  (Succ (Succ (Succ (Succ Zero))))
power (toNat 8) Zero       ↦  Succ Zero

Feladat

Definiáld egy nagyon egyszerű telefonkönyv megvalósításához szükséges típusokat.

1. PhoneBook: a telefonkönyv neveket és telefonszámokat összepárosító bejegyzések sorozata.
   1. Entry: egy bejegyzés
   2. Name: szöveg, a bejegyzés első komponense
   3. Number: egész szám, a bejegyzés második komponense

[("Frici", "8396"), ("Jozsi", "2345"), ("Feco", "4852")]
          :: PhoneBook

Feladat (folyt.)

2. emptyBook: az üres telefonkönyv

emptyBook :: PhoneBook

Feladat (folyt.)

3. findEntry: keresőfüggvény

A findEntry megkeres egy névhez tartozó telefonszámot. Ha nem talál ilyet, akkor Nothing eredményt adjon.

findEntry :: PhoneBook -> Name -> Maybe Number

Példák:

myPhoneBook =
     [("Frici", "8396"), ("Jozsi", "2345"),
      ("Feco", "4852")]
findEntry myPhoneBook "Frici"   ↦   Just "8396"
findEntry emptyBook   "Frici"   ↦   Nothing

Feladat (folyt.)

4. addEntry: új bejegyzés

Az addEntry egy bejegyzést illeszt be egy meglevő telefonkönyvbe. Ha a megadott névhez már tartozik bejegyzés, a telefonkönyv nem változik.

addEntry :: PhoneBook -> Entry -> PhoneBook

Példák:

addEntry emptyBook ("Imi", "2356") ↦  [("Imi", "2356")]
addEntry [("Jancsi", "2356")] ("Imi", "8963")
        ↦  [("Imi", "8963"), ("Jancsi", "2356")]
addEntry [("X", "2")] ("X", "1") ↦  [("X", "2")]

Feladat (folyt.)

5. addEntryMod: új bejegyzés, módosít

Az addEntryMod az addEntry függvénytől annyiban tér el, hogy ha a megadott névhez már tartozik bejegyzés, a bejegyzéshez tartozó szám frissül.

addEntryMod :: PhoneBook -> Entry -> PhoneBook

Példa:

addEntryMod [("Jancsi", "2356")] ("Jancsi", "1111")
        ↦  [("Jancsi", "1111")]

Feladat

Készítsd el a fromNat függvényt, amely a Nat típusú értékekből egész számokat állít elő, és a fordított irányban működő toNat függvényt.

fromNat :: Nat -> Integer
toNat   :: Integer -> Nat

Példák:

fromNat Zero                ↦  0
fromNat (Succ (Succ Zero))  ↦  2
toNat 0   ↦   Zero
toNat 2   ↦   (Succ (Succ Zero))

Eszköz

A fromNat felhasználásával írassuk ki "normális" egész számként a Nat típusú értékeket.

Ehhez a Show típusosztályt kell példányosítani, ezúttal nem deriving származtatással, hanem egyedileg.

A Show típusosztály a show függvény megvalósítását írja elő.

instance Show Nat where
    show x = show (fromNat x)

Feladat

Definiáld újra az Ordering típust és annak compare függvényét.

compare :: (Ord a) => a -> a -> Ordering

Az Ordering lehetséges értékei:

LT :: Ordering -- less than
EQ :: Ordering -- equal
GT :: Ordering -- greater than

import Prelude hiding (Ordering, LT, EQ, GT, compare)

Feladat

Keresd meg egy listában, hogy melyik indexű elem volt a legnagyobb (az indexelés az 1 értéktől indul).

maxIndex :: Ord a => [a] -> Int

maxIndex [4, sqrt 14, 50 / 13, 3 ** 1.3]  ↦  4

Feladat

Készíts egy olyan minimumkeresést, amely az üres listákra nem ad eredményt.

maybeMinimum :: (Ord a) => [a] -> Maybe a

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

Feladat

Írj az előbbi függvényhez egy feldolgozó függvényt, amely szöveges üzenetben közli az eredményt (értelemszerűen azt is, ha a paraméterként adott lista nem rendelkezik minimummal).

showMinimum :: (Ord a, Show a) => [a] -> String

showMinimum [1..10]  ↦  "Minimum of the list: 1"
showMinimum []       ↦  "No minimum."

Feladat

Készíts statisztikát egy szövegben előforduló karakterek gyakoriságáról.

charFrequency :: String -> [(Int, Char)]

charFrequency "abrakadabra"  ==
      [(5,'a'),(2,'b'),(1,'d'),(1,'k'),(2,'r')]

Feladat

Rendezz egy listát, és add meg az elemek indexét az eredeti listában (az indexelés az 1 értéktől indul).

origIndices :: Ord a => [a] -> Int

origIndices [4, sqrt 14, 50 / 13, 3 ** 1.3]  ↦
      [2, 3, 1, 4]

Feladat

Keresd meg az 1 és n közötti egész számok közül a legtöbb osztóval rendelkezőt.

maxDivisorsUntil :: Int -> Int

maxDivisorsUntil 100  ↦   96
maxDivisorsUntil 200  ↦  180

Feladat

Kódold és dekódold a listában előforduló futamokat (egymás utáni ismétlődő elemeket).

compress   :: Eq a => [a] -> [(Int,a)]
decompress :: Eq a => [(Int,a)] -> [a]

compress "abbccccb"  ↦
      [(1,'a'),(2,'b'),(4,'c'),(1,'b')]
decompress [(1,'a'),(2,'b'),(4,'c'),(1,'b')]  ↦
      "abbccccb"