Funkcionális programozás gyakorlat

7. feladatsor

Beadandó feladat (1. rész)

Definiáld a következő függvényeket:

parenthesisWeight  ::  Char  ->  Int
parenthesisWeights :: [Char] -> [Int]

A parenthesisWeight függvény rendelje hozzá a '(' karakterhez az 1 értéket, a ')' karakterhez a -1 értéket, minden más esetben adjon vissza nullát.

A parenthesisWeights függvény alkalmazza az előző függvényt egy sztring minden elemére.

Beadandó feladat (2. rész)

Definiáld a következő függvényt:

lastDepth :: String -> Int

A függvény adja meg, hogy a szövegben mennyivel több nyitó zárójel volt, mint záró zárójel.

Példa:

lastDepth "((("   ↦   3
lastDepth ")))"   ↦   -3
lastDepth "()()"  ↦   0

Beadandó feladat (3. rész)

Definiáld a következő függvényt:

depths :: String -> [Int]

A függvény tetszőleges karakterlistához hozzárendel egy annál eggyel hosszabb listát, amely a karakterek közti "mélységet" tartalmazza. Mélység alatt azt értjük, hogy előzőleg mennyivel több nyitó zárójel volt mint záró zárójel.

Példa:

depths "()"     ↦   [0,1,0]
depths "(ab)"   ↦   [0,1,1,1,0]
depths "(())"   ↦   [0,1,2,1,0]

Beadandó feladat (4. rész)

wellformed :: String -> Bool

A függvény megadja, hogy egy szöveg jól zárójelezett-e. Ez két feltétel együttes meglétét jelenti:

1. nem zárunk be ki nem nyitott zárójelet
2. nincsen olyan kinyitott zárójel, amelyet nem zárunk be

Példa:

wellformed "(()"       ↦  False
wellformed "()()"      ↦  True
wellformed "((x)y(z))" ↦  True
wellformed "alma"      ↦  True

Feladat

Állítsd elő a Pascal-háromszöget.

`[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1],`...`]`.

pascalTriangle :: [[Integer]]

Feladat

Számold ki a binomiális együtthatókat.

Az együtthatók a Pascal-háromszög megfelelő sorában és oszlopában találhatóak.

Azt adják meg, hogy n különböző elemből hányféleképpen lehet k darab elemet kiválasztani.

binomCoeff :: Int -> Int -> Integer

Ezek segítségével döntsd el, hogy az 5-ös vagy a 6-os lottón van-e nagyobb esélye a telitalálatnak.

Eszköz

Függvénykompozíció

(.) :: (b -> c) -> (a -> b) -> (a -> c)

Példák:

((+ 1) . (* 4)) 5                       ↦  21
(map (+ 2) . filter even) [1..5]        ↦  [4,6]
(length . filter even) [1..5]           ↦  2
(tail . map (+ 2) . filter even) [1..5] ↦  [4,6]

Eszköz

Fold

foldl :: (a -> b -> a) -> a -> [b]{-véges-} -> a
foldr :: (a -> b -> b) -> b -> [a]{-véges-} -> b

Példák:

foldl (-) 0 [1,2,3]     ↦  ((-) ((-) ((-) 0 1) 2) 3)
                           (((0 - 1) - 2) - 3)
foldr (-) 0 [1,2,3]     ↦  ((-) 1 ((-) 2 ((-) 3 0)))
                           (1 - (2 - (3 - 0)))

Feladat

Fold segítségével add meg az alábbi függvényeket.

1. A logikai vagy függvény listákra.
2. Két lista összefűzése.
3. Egy lista elemeinek szorzata.
4. Egy lista elemeinek összege.

or      :: [Bool]{-véges-} -> Bool
(++)    :: [a] -> [a] -> [a]
product :: Num a => [a]{-véges-} -> a
sum     :: Num a => [a]{-véges-} -> a

Feladat

Definiáld újra a könyvtári scanl függvényt.

scanl :: (a -> b -> a) -> a -> [b] -> [a]

Működése a foldl és a map függvények keveréke: a görgetett értékre cseréli ki a lista elemeit. Első értéke a kezdőérték.

Példa:

scanl (+) 3 [1,2..]  ↦  [3, 3 + 1, 3 + 1 + 2, ...]
                        [3,4,6,...]

Extra

Add meg az alábbi függvényeket.

1. Lista összegsorozata (az adott elemig tartó elemek összege). 2.

sums :: Num a => [a] -> [a]

Eszköz

Definiáld újra az until függvényt.

until :: (a -> Bool) -> (a -> a) -> a -> a

Ez addig alkalmaz egy elemre egy függvényt sorozatosan, amíg egy adott feltételt nem teljesít a kapott eredmény.

until (==10)  (+1) 1  ↦   10
until (>1000) (*2) 1  ↦   1024

Eszköz

Definiáld újra a zipWith függvényt.

zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]

Ez a zip-hez hasonlóan összecsomagol egy listát, de általánosabban, egy függvény segítségével.

zipWith (+) [1,2,3,4,5] [5,6,7,8] == [6,8,10,12]

Az eredeti zip is megkapható vele a párképző függvénnyel:

zipWith (,)

Feladat

Definiáld újra a Data.List modulbeli nub függvényt. Ez a töbször szereplő elemeket hagyja el egy listából.

nub :: Eq a => [a] -> [a]

Példa:

nub [4,4,2,4,1,2,2,3]   ↦   [4,1,2,3]

Feladat

Definiáld a gyorsrendezést. A gyorsrendezés a listát kettébontja a fejnél kisebb és nagyobb elemekre, ezeket rendezi, majd a kapott (már rendezett) kisebb és nagyobb részt fűzi újra össze.

qsort :: Ord a => [a] -> [a]