Negyedik előadás

Egysoros függvénydefiníciók

divides :: Integral a => a -> a -> Bool
divides a b  =  b `mod` a == 0

even :: Integral a => a -> Bool
even n = 2 `divides` n

odd :: Integral a => a -> Bool
odd = not . even

dividers :: Integral a => a -> [a]
dividers a = [n | n<-[1..a], n `divides` a]

Egysoros függvénydefiníciók (2)

isPrime :: Integral a => a -> Bool
isPrime n =  length (dividers n) == 2

primes :: Integral a => [a]
primes = [n | n<-[2..], isPrime n]

isqrt :: Integral a => a -> a
isqrt = floor . sqrt . fromIntegral

isPrime' :: Integral a => a -> Bool
isPrime' p = not $ or [n `divides` p | n<-[2..isqrt p]]

Egysoros függvénydefiníciók (3)

primes' :: Integral a => [a]
primes' = [2,3] ++ [n | n<-[5,7..], isPrime'' n]

isPrime'' :: Integral a => a -> Bool
isPrime'' p = not $ or [n `divides` p | n <- takeWhile (<= isqrt p) primes']

Körrizés

A függvényeket lehet részlegesen is alkalmazni:

take            :: Int -> [a] -> [a]
take 3          ::        [a] -> [a]
take 3 "Hello"  ::               [Char]
take 3 []       ::               [a]

Gyakorlati példa:

reverseTake n = reverse . take n . reverse

Automatikus körrizés

 take 3  [1..10]

azonos a következővel:

(take 3) [1..10]

Ballaszt

areTriangleSides :: Real a => a -> a -> a -> Bool
areTriangleSides a b c =  a < b + c  &&  b < a + c  &&  c < a + b

Hajtogatások

Hajtogatás balról és jobbról:

foldl :: (b -> a -> b) -> b -> [a]{-véges-} -> b
foldl f x [1,2,3,4]  ==  f (f (f (f x 1) 2) 3) 4

foldr :: (a -> b -> b) -> b -> [a]{-véges-} -> b
foldr f x [1,2,3,4]  ==  f 1 (f 2 (f 3 (f 4 x)))

Variánsok:

foldl1 :: (a -> a -> a) -> [a]{-véges, nemüres-} -> a
foldl1 f [1,2,3,4]  ==  f (f (f 1 2) 3) 4

foldr1 :: (a -> a -> a) -> [a]{-véges, nemüres-} -> a
foldr1 f [1,2,3,4]  ==  f 1 (f 2 (f 3 4))

Névtelen argumentum

Ha egy (névelen) függvény argumentumát nem akarjuk felhasználni, változó helyett egy _ kerül a helyére.

sum     = foldr (+) 0
product = foldr (*) 1
minimum = foldr1 min
maximum = foldr1 max
and     = foldr (&&) True
or      = foldr (||) False
concat  = foldr (++) []
length  = foldl (\a _ -> a + 1) 0
a ++ b  = foldr (:) b a
reverse = foldl (\a b -> b:a) []

Dia

mean :: Fractional a => [a]{-véges-} -> a
mean l = sum l / fromIntegral (length l)

means :: Fractional a => [a] -> [a]
means = tail . scanl (\s (n,x)->s + (x-s)/fromIntegral n) 0 . zip [1..]

Lokális definíciók

A Haskell nyelvben számít, mennyire húzzuk be a sorokat.

infixr 9 .
(.) :: (b -> c) -> (a -> b) -> (a -> c)
(.) f g = h  where  h x = f (g x)

Esetszétválasztás

f par1 par2
    | feltétel1 =  eredmény1
    | feltétel2 =  eredmény2
    | ...       =  ...
    | feltételN =  eredményN
    | otherwise =  eredményUtolsóÁg

Gyakorlati példa:

min, max :: (Ord a) => a -> a -> a
min x y
    | x <= y    =  x
    | otherwise =  y

Mintaillesztés

Logikai tagadás

not True  = False
not False = True

Logikai "és"

and True  True  = True
and True  False = False
and False True  = False
and False False = False

Mintaillesztés (2)

Logikai "és" egyszerűbben:

and True True = True
and _ _ = False

Logikai "és" egyszerűbben és gyorsabban (lustán):

and True x = x
and _    _ = False

Mintaillesztés listákra

insertions :: a -> [a] -> [[a]]
insertions a [] = [[a]]
insertions a l@(h:t) = (a:l) : map (h:) (insertions a t)

permutations :: [a] -> [[a]]
permutations (h:t) = [l' | l<-permutations t, l'<-insertions h l]

Gyorsrendezés:

qsort :: [a] -> [a]
qsort [] = []
qsort (h:t) = qsort [x|x<-t, x<=h] ++ [h] ++ qsort [x|x<-t, x>h]