FP Cvičení 2

Typy

• V interpretu GHCi lze použít příkaz :info k zjištění typu funkce nebo operátoru, zjistěte typ následujících elementů: +, sqrt, succ, max
• Zjistěte informace o typech následujících výrazů a vyhodnoťte je. K tomuto slouží příkaz :type. Je možné zapnout, aby interpret standardně vypsal typ výrazu. Toto jde příkazem :set +t (tuto funkci lze vypnout :unset +t).

5 + 8 
3 * 5 + 8
2 + 4
sqrt 16 
succ 6
succ 7
pred 9
pred 8
sin (pi / 2)
truncate pi
round 3.5
round 3.4 
floor 3.7 
ceiling 3.3
mod 10 3
odd 3

• Na přednáškách byly diskutovány některé základní datové typy: Int, Double, Bool, Char. Přiřaďte předcházejícím výrazům nejvhodnější z těchto základních datových typů. Váš tip je možné ověřit využitím operátoru ::. Například pro první výraz předpokládejme, že jeho výsledný typ je Int. Můžeme manuálně přetypovat výsledek na celé číslo a toto ověřit.

Prelude> :type (5 + 8) :: Int
(5 + 8) :: Int :: Int

Pokud provedeme nekorektní konverzi na Char, dostaneme následující výsledek.

Prelude> :type (5 + 8) :: Char

<interactive>:1:2: error:
    * No instance for (Num Char) arising from a use of `+'
    * In the expression: (5 + 8) :: Char

Pro tento výraz je platná konverze také na typ Double.

Prelude> :type (5 + 8) :: Double
(5 + 8) :: Double :: Double

Reasoning about types

Pro následující výrazy se pokuste určit:

• zda je výraz typově korektní;
• jaký bude typ výsledku;
• jaký bude výsledek;
• zadejte výraz do interpretu a ověřte vaše tvrzení.

5.9/7
(floor 5.9)/7
floor 5.9/7
fromIntegral floor 5.9/7
fromIntegral (floor 5.9)/7
div (floor 5.9) 7
(floor 5.9) div 7
(floor 5.9) `div` 7
mod 10/2 3
mod (floor (10/2)) 3

Jednoduché funkce

Implementujte následující funkce:

• Funkce která spočítá faktoriál zadaného čísla.
  

factorial :: Int -> Int

*Main> factorial 5
120

factorial  :: Int -> Int
factorial  0 = 1
factorial  n = n * factorial  (n-1)

factorial'  :: Int -> Int
factorial' n | n==0 = 1
             | otherwise = n * factorial'' (n-1)

factorial''  :: Int -> Int        
factorial'' n = if n==0 then 1 else n * factorial'' (n-1)

• Funkce která spočítá n-tý člen ve Fibonacciho sekvenci.
  

fib :: Int -> Int

*Main> fib 5      
8

fib :: Int->Int
fib 0 = 1
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

fib' :: Int -> Int
fib' n = tmp n 1 1 where
  tmp 0 a _ = a 
  tmp x a b = tmp (x-1) b (a+b)

• Funkce která ověří, že zadaný rok je přestupný (rok je přestupný když je dělitelný 4 a zároveň není dělitelný 100. Pokud je dělitelný 400, je to přestupný rok).

leapYear :: Int -> Bool

*Main> leapYear 2000
True
*Main> leapYear 2020
True
*Main> leapYear 2100
False
*Main> leapYear 2019
False

leapYear :: Int -> Bool
leapYear x = x `mod` 4 == 0 && x `mod` 100 /= 0 || x `mod` 400 == 0

leapYear' :: Int -> Bool
leapYear' x | x `mod` 400 == 0 = True
            | x `mod` 100 == 0 = False
            | otherwise = x `mod` 4 == 0

• Implementujte dvě funkce, které vrátí maximální hodnotu ze dvou respektive tří čísel. Ty budou zadány jako parametry.

max2 :: Int -> Int -> Int
max3 :: Int -> Int -> Int -> Int

*Main> max2 5 8
8
*Main> max3 5 8 4
8

max2 :: Int -> Int -> Int
max2 x y | x >= y = x
         |otherwise = y

max3 :: Int -> Int -> Int -> Int
max3 x y z = (x `max2` y) `max2` z

• Kombinace je výběr položek z kolekce, kde (narozdíl od permutace) pořadí prvku při výběru nehraje roli. Spočítejte počet možných kombinací, pokud vybíráme k prvků z kolekce n prvků.

combinations :: Int -> Int -> Int

*Main> combinations 8 5
56

factorial  :: Int -> Int
factorial  0 = 1
factorial  n = n * factorial  (n-1)

combinations :: Int -> Int -> Int
combinations n k = factorial n `div` (factorial k * factorial (n-k))

combinations' :: Int -> Int -> Int
combinations' n k = fromIntegral(factorial n) `div` fromIntegral(factorial k * factorial (n-k))

• Implementujte funkci, která spočítá počet řešení kvadratické rovnice. Tato kvadratická rovnice je zadaná standardními koeficienty: a,b,c.

numberOfRoots :: Int -> Int -> Int -> Int
-- To simplify the solution, let construct can be used
f x y = let a = x + y
        in a * a

*Main> numberOfRoots 1 4 2
2

numberOfRoots :: Int -> Int -> Int -> Int
numberOfRoots a b c = let d = b*b - 4 * a *c
                      in if d<0 then 0 else if d == 0 then 1 else 2

• Implementujte funkci, která spočítá nejvetší společný dělitel pro dvě zadaná čísla.
  

gcd' :: Int -> Int -> Int

*Main> gcd' 30 18
6

gcd' :: Int -> Int -> Int
gcd' a b | a > b = gcd' (a-b) b
         | a < b = gcd' a (b-a)
         | a==b = a

gcd2 :: Int -> Int -> Int         
gcd2 a 0 = a
gcd2 a b = gcd2 b (a `mod` b)

• Implementujte funkci, která určí, zda je zadané číslo prvočíslo.
  

isPrime :: Int -> Bool

*Main> isPrime 7
True

isPrime :: Int -> Bool
isPrime 1 = False
isPrime y = isPrimeTest y (y-1) where
  isPrimeTest _ 1 = True 
  isPrimeTest n x | n `mod` x ==0 = False
                  | otherwise = isPrimeTest n (x-1)

Další zadání

• Definujte funkci, která vrací true, pokud jsou všechny tři argumenty různé.

threeDifferent :: Int -> Int -> Int -> Bool

*Main> threeDifferent 4 5 6
True
*Main> threeDifferent 6 5 6
False

• Definujte funkci, která vrací true, pokud se všechny čtyři argumenty rovnají.

fourEqual :: Int -> Int -> Int -> Int-> Bool

*Main> fourEqual 4 5 6 7
False
*Main> fourEqual 4 4 4 4
True

• Definujte funkci, která vypočítá průměr tří celých čísel.

averageThree :: Int -> Int -> Int -> Float

*Main> averageThree 4 10 20
11.333333

• Definujte funkci, která vrací, kolik z jejích vstupů je větších než jejich průměrná hodnota.

howManyAboveAverage :: Int -> Int -> Int -> Int

*Main> howManyAboveAverage 5 5 5
0
*Main> howManyAboveAverage 10 50 50 
2

• Pomocí násobení přes celá čísla implementujte rekurzivní funkci, která realizuje n-tou mocninu celého čísla.

power :: Int -> Int -> Int

*Main> power 2 3                    
8
*Main> power 4 2
16
*Main> power 4 3
64

• Pomocí sčítání nad celými čísly implementujte rekurzivní funkci, která realizuje násobení celých čísel.

mult :: Int -> Int -> Int

*Main> mult 4 5
20
*Main> mult 4 9
36
*Main> mult 4 0
0

• Definujte rekurzivní funkci, která vypočítá zbytek po dělení celým číslem.

mod' :: Int -> Int -> Int

*Main> mod' 40 7
5
*Main> mod' 30 5
0
*Main> mod' 20 7
6