Vestavěné predikáty

Vestavěné predikáty

Funkcionln programovn Haskell Jan Hric, KTIML MFF UK,1997-2005 http://ktiml.ms.mff.cuni.cz/~hric/ [email protected] Funkcionln programovn Historicky: lambda-kalkul, cca. 1940 LISP, 1959-1960 ...Scheme, ML, Haskell Literatura: - Richard Bird, Philip Wadler, Introduction to Functional Programming

Prentice Hall, New York, 1988 jazyk Miranda - Simon Thompson: Haskell: The Craft of Functional Programming, Addison-Wesley, 1997 - http://www.haskell.org -> impl. Hugs (,GHC) - elektronicky: tutorial.ps,.dvi Jazyk Haskell funkcionln jazyk siln typovan polymorfizmus, parametrick (vs. podtypov v C++) implicitn typovn (systm si typy odvod) ln vyhodnocovn

nekonen d.s. referenn transparentnost ... dal rysy porovnvn se vzorem - pattern matching (msto selektor) funkce vych d lexikln rozsahy platnosti, dvourozmrn syntax (indentace) typov tdy (uivatelsky definovan), peten funkce ist jazyk (bez sideefekt), spec. podpora V/V moduly (N/I) Zklady interpretan cyklus: ti - vyhodno - vytla (read - eval -print)

vyhodnocen vrazu kad vraz m hodnotu (a typ) zdrojov text v souboru -- komente {- vnoen komente -} prelude.hs (standard.pre) -- peddefinovan funkce ... prompt ? (dve, nyn > ) ? :quit ? :? help, seznam pkaz ? :load myfile.hs Skripty a interakce

? 3*4 12 delka = 12 kvadrat x = x*x plocha = kvadrat delka ? kvadrat (kvadrat 3) 81 Kontext, prosted - obsahuje dvojice: promnn a hodnota Vrazy a hodnoty redukce vrazu podle pravidla-definice fce kvadrat(3+4) =>(3+4)*(3+4) -=> 7*(3+4)

-=> 7*7 -=> 49 -- kvadrat + + * ln vyhodnocovn: voln funkce se nahrazuje tlem, za formln argumenty se dosad (nevyhodnocen) aktuln arg., arg. se vyhodnocuje pouze pokud je poteba pi uvaovn o programech spec. hodnota: nedefinovno chyba, nekonen vpoet

Hodnoty a typy 5 :: Int pklady zpisu hodnot a jejich typ 10000000000 :: Integer dlouh sla 3.0 :: Float a :: Char \t,\n,\\,\,\ True :: Bool ; False :: Bool v prelude [1,2,3] :: [Int], 1:2:3:[]::[Int] abc :: [Char] retzce, String (2, b) :: (Int, Char) dvojice, n-tice succ :: Int -> Int typ funkce

succ n = n+1 definice funkce *patn [2,b] hodnoty mus mt stejn typ Typy zkladn: Int, Integer (nekonen pesnost), Bool, Char, Float sloen n-tice (1,a):: (Int,Char), (a,b,c) ... speciln ( ) :: ( ) seznamy: [a] = [] | a : [a] typy funkc: Int -> Int (uivatelsky definovan) (typov) promnn: a, b, ... v popisu typu ! uvdt typ nen nutn, ale odvozuje se (a kontroluje se ->

typov chyba) suma::[Int]->Int, length::[a]->Int length [] = 0 length (a:xs) = 1 + length xs (typov tdy def. petench fc, stejn jmno pro rzn typy) Pevody typ explicitn voln pevodnch funkc toEnum :: Int -> Char -- peddefinovno, zjednodu. (peten) fromEnum :: Char -> Int -- lze def. pro vt. typy ord = fromEnum -chr = toEnum offset = ord A ord a

capitalize :: Char -> Char capitalize ch = chr (ord ch + offset) isDigit :: Char -> Bool isDigit ch = (0 <= ch) && (ch <= 9) Funkce Definice v souboru - skriptu funkce se aplikuje na argumenty a vrac vsledek curried forma (podle Haskell B. Curry) argumenty chod po jednom f :: Int -> (Int -> Int) msto: f :: (Int, Int) -> Int f (3,4) = ... f 3 4, (f 3) 4 => ...

Int, Bool a vest. fce :: Int -- typ celch sel bn aritmetick opertory +,*,^,-,div,mod :: Int -> Int -> Int nepesn, je peten abs, negate:: Int -> Int :: Bool , vsledky podmnek, str > >= == /= <= < :: a->a->Bool nepesn (1) && || :: Bool -> Bool -> Bool not :: Bool->Bool (1) nkter typy nelze porovnvat, nap. funkce a typy funkce obsahujc

Pklady maxi :: Int -> Int -> Int maxi n m | n>=m = n -- stre/guards | otherwise = m allEq :: Int->Int->Int->Bool allEq n m p = (n==m)&&(m==p) const :: a -> b -> a const c x = c Voln const c :: b->a je pro c::a konstantn funkce ? const 7 (1.0/0.0) -- bez chyby kvli lnmu vyhodnocen 7

Pklad fact3 :: Int -> Int fact3 n = if n==0 then 1 else n*fact3 (n-1) ? fact3 4 24 iSort :: [Int] -> [Int] iSort [] = [] iSort (a:x) = ins a (iSort x) ins :: Int -> [Int] -> [Int] ins a [] = [a] -- ins cmp a [] = [a] ins a (b:x) -- ins cmp a (b:x) | a<=b

= a:b:x -- zobecnn | cmp a b = | otherwise = b : ins a x s porovnvac fc cmp: (i obecnj typ) - parametrizace kdem ins :: (a->a->Bool)->a->[a]->[a] , iSort :: :: (a->a->Bool)->[a]->[a] Lexikln konvence identifiktory post. psmen, slice, (apostrof), _(podtrtko) funkce a promnn - za. malm psm. velk za. psm - konstruktory vyhrazeno: case of where let in if then else data type infix infixl infixr primitive class instance module default ...

opertory jeden nebo vc znak : ! # $ * + - . / \ < = > ? @ ^ | spec. : ~ symbolov konstruktory zanaj znakem : identifiktor v `(zptn apostrof): 5 `mod` 2 zvorky pro neopertorov uit opertor: (+), (+) 3 4 Syntax - layout 2D layout, offside pravidlo: definice, stre (|), case, let, where ... - umouje vynechn separtor - zapamatuje se sloupec za. definice fce, cokoli je napravo,

pat do definice nsd n m | n==m = n | n>=m = nsd m (n `mod` m) | otherwise = nsd m n explicitn skupina v {}, jako separtor znak ; -vce definic na jednom dku Podmnky fact3 :: Int -> Int -- neoetuje zporn vstupy

fact3 n = if n==0 then 1 else n*fact3 (n-1) fact2 n | n==0 = 1 | n>0 = n*fact2 (n-1) | otherwise = error in: fact2 Porovnvn se vzorem pattern matching (nen to unifikace, pouze jednostrann) implicitn podmnka na mst formlnho parametru i pro uivatelsky def. typy length1 :: [a] -> Int length1 [] = 0 length1 (x:xs) = 1 + length1 xs --zv. nutn -- vzor n+k

fact1 0 = 1 fact1 (n+1) = (n+1)*fact1 n -- vzor _ and :: (Bool,Bool) -> Bool -- necurryovan and (True,True) = True -- and nen ln and (_ ,_) = False and2 (False, _) = False -- ln verze and2 (_ , x) = x

Lokln definice: where, let lokln def. k fci uvd kl. slovo where (na nejv. rovni) norma :: Complex->Float norma cnum = sqrt(re^2+im^2) where re = rpart cnum -- def. vzj. rekurzvn im = ipart cnum c = (3.0,4.0) -- testovac data ? let re=rpart c; im=ipart c in sqrt(re^2+im^2) 5.0 -- c = (3.0,4.0) rpart rpart ipart

ipart :: Complex -> Float (re,_) = re :: Complex -> Float (_,im) = im -- definice selektor Opertory zvorky pro deklaraci opertoru (&&&)::Int->Int->Int -- maximum a&&&b = maxi a b pevod : op na fci, bin. fce na op.

ekvivalentn: (+) 3 4 , 3+4 5 `div` 2 , div 5 2 (deklarace opertor) aplikace fce ve nejvc: fact 3 + 4 vs. fact (3+4) ** abs -12 ; abs (-12) Sekce: (+), (1+) (+1)::Int->Int -- pro vechny opertory Opertory 9-0 ; 9 nejvy priorita , 0 nejni funkn voln .. ve tsnji ne 9 9,doleva asoc. !! -- n-t prvek

9,doprava . -- skldn fc 8,doprava ^ ^^ ** 7,doleva * / `div` `mod` `rem` `quot` 6,doleva + i unrn 5,doprava : ++ neasoc \\ 4,neasoc == /= < <= > >= `elem` `notElem` 3,doprava &&

-- and 2,doprava || -- or Definice opertor vy priorita jako v matematice pouze binrn opertory infixl 6 + -- stn, doleva asoc. infixr 5 ++ -- append, doprava asoc. infix 4 == -- porovnvn, neasoc. infix 4 `elem` -- prvek seznamu, neasoc.

Odlinosti aplikanho programovn bezstavov, nem (klasick) promnn neobsahuje pkazy, nap. piazen neobsahuje sekvenci pkaz vraz je definovan svm vskytem (jako aktuln parametr) pouije se jen 1x Program pracuje s celmi d.s. (seznamy , stromy ) Program vznik (obvykle) skldnm z jednoduch funkc (ne jako posloupnost zmn poloek d.s.) Syntax

case, if - porovnvn se vzorem stre let, where - vloen definice \ x -> f(x) - definice funkc (lambda) dvourozmrn syntax (layout) strun seznamy data - definice novch uivatelskch datovch typ type - typov synonyma type Complex = (Float,Float) (roziujc st) Seznamy data List a = []

| a : (List a) - ve skutenosti vestavn typ [a] length [] = 0 length (x:xs) = 1+length xs map :: (a->b)->[a]->[b] map f [] = [] map f (x:xs) = f x : map f xs ? map (+1) [2,3,4] -- [3,4,5] :: Int ? map (+) [2,3,4] -- [(2+),(3+), (4+)] :: [Int -> Int] ? map (const 1) abc -- [1,1,1] :: Int DC: zip :: [a]->[b]->[(a,b)]

Konstruktory seznamu - konstruktory jsou automaticky vytvoeny z definice typu [] :: [a] -- polymorfn konstanta (:) :: a -> [a] -> [a] -- data [a] = [] | a : [a] pseudokod, lexikln nesprvn symbolov konstruktory mus zanat :, jinak to jsou funkce konvence: [1,2,3] je vraz 1:2:3:[] Dlen dku na slova type Word = String

splitWords :: String -> [Word] splitWords st = split (dropSpace st) split :: String -> [Word] split [] = [] split st = (getWord st):split(dropSpace(dropWord st)) dropSpace st = dropWhile (\x->elem x whitespace) st dropWord st = dropWhile (\x->not(elem x whitespace)) st dropWhile :: (t -> Bool) -> [t] -> [t] dropWhile p [] = [] dropWhile p (a:x) | p a = dropWhile p x | otherwise = (a:x) getWord st = takeWhile (\x-> not(elem x whitespace)) st DC: takeWhile p x =

whitespace = [ , \t, \n] Uivatelsk typy nerekurzivn data data data data data Bool = False | True -- peddef. Color = Red | Green | Blue Point a = Pt a a -- polymorfn Maybe a = Nothing | Just a Union a b = Left a | Right b

Bool, Color, Point, jsou jmna typ False, Red, Pt ... jsou jmna konstruktor Pt m dva argumenty, False, Red, Nothing ... jsou konstanty a maj nula arg., ... porovnvat se vzorem lze i uiv. typy Pt 1 2 :: Point Int -- hodnoty jsou konkrtnho typu Pt a b :: Point Char vestavn typy nejsou speciln; li se lexikln, ne smanticky Rekurzivn uiv. typy data Tree a = Leaf a | Branch (Tree a) (Tree a)

data Tree2 a = Void | Node (Tree2 a) a (Tree2 a) konstruktory jako funkce pstup na sloky: porovnvn se vzorem, case, sel. funkce leftSub,.. Leaf :: a -> Tree a Branch :: Tree a -> Tree a -> Tree a leftSub :: Tree a -> Tree a leftSub (Branch l _)= l leftSub _ = error leftSub: unexpected Leaf p.: seznam list stromu, ++ je spojen seznam listy :: Tree a -> [a]

listy (Leaf a) = [a] listy (Branch l r) = listy l ++ listy r -- listy (Branch l r) = append (listy l) (listy r) Regulrn typy - n-arn stromy data NTree a = Tr a [NTree a] - regulrn typy: typov konstruktory (NTree) pouit na prav stran definice maj stejn argumenty (typov promnn) jako na lev stran definice - nejde: - data Twist a b = T a (Twist b a) | Notwist - data Vtree a = In ( Vtree (a,a)) | -- vyven stromy Typov synonyma

Klov slovo type na prav stran od = jsou jmna jinch typ data Barva = Trefy | Kara | Srdce | Piky data Hodnota = ... type Karta = (Barva,Hodnota) type RGB = (Int, Int, Int) Komplexn aritmetika komplexn slo jako dvojice realnch . type Complex = (Float,Float) cadd :: Complex -> Complex -> Complex cadd (rx,ix) (ry,iy) = (rx+ry,ix+iy) -- implicitn typ fce cadd je obecnej

... ? cadd (1.0,0.0) (0.1,2.0) (1.1,2.0) Case obecn porovnvn se vzorem case (promnn, ...) of (vzor, ...) -> vraz ... take n xs vybere ze seznamu xs prvnch n prvk, pokud existuj take2 :: Int take2 n xs = (0,_)

-> (_,[]) -> (n+1,x:xs) -> [a] -> [a] case (n,xs) of [] [] -> x : take2 n xs P.:Take take, ekvivalentn (a obvykl) zpis take n xs vybere ze seznamu xs n prvk, pokud existuj take1 0 _

= [] take1 _ [] = [] take1 (n+1) (x:xs) = x : take1 n xs Podmnn vraz if vraz je syntaktick cukr if e1 then e2 else e3 ekvivalentn case e1 of True -> e2 False -> e3 Funkce

funkce se konstruuj tzv. lambda-abstrakc succ x = x+1 -- obvykl zpis succ = \ x -> x+1 -- ekv. lambda vraz add = \ x y -> x+y -- vc parametr formln parametry maj rozsah platnosti tlo definice succ a add se vyhodnot na (intern) repr. danch fc funkci lze aplikovat na argument (!mezerou) typy: kdy x::a, e::b, pak \x->e :: a->b anomymn funkce - jako parametry fc vych d referenn transparentnost: voln fce na stejnch parametrech vrt stejnou hodnotu protoe nemme globln promnn, piazen a sideefekty Funkce 2

na funkcch nen definovna rovnost funkci mu aplikovat na argumenty aplikace je (jedin) selektor => lze zjistit jej hodnotu v jednotlivch bodech skldn fc (.) :: (b->c) -> (a->b) -> (a->c) f . g = \ x -> f (g x) -- (f . g) x = f (g x) -- ekviv. odd :: Int -> Bool odd = not . even -- odd x = (not.even) x -- ekv. zpis Funkce 3 currying / curryfikace: argumenty chod po jednom

typ a->b->c msto (a,b)->c vhoda: lze sten aplikovat sekce: p: (+1), (1+), (+) (x op) ekv. \y ->x op y, (op y) ekv. \x ->x op y (op) ekv. \x y-> x op y harmonicky_prumer :: [Float] -> Float harmonicky_prumer xs = (fromInt(length xs)/) (sum (map (1/) xs)) Aritmetika s testovnm chyb lift2M :: (a->b->c)->Maybe a -> Maybe b -> Maybe c lift2M op Nothing _ = Nothing

lift2M op _ Nothing = Nothing lift2M op (Just x) (Just y) = Just (x op y) minusM :: Maybe Float -> Maybe Float -> Maybe Float minusM x y = lift2M (-) x y delenoM x y= if y==Just 0 then Nothing --vyvoln chyby else lift2M (/) x y ? deleno(Just 3)(lift2M (-)(Just 2)(Just 2)) -- 3/(2-2) Nothing data AV a = AV a :-: AV a | AV a :/: AV a | Con a | eval :: AV Integer -> Maybe Integer eval (av1 :/: av2) = delenoM (eval av1) (eval av2) eval (av1 :-: av2) = lift2M (-) (eval av1) (eval av2) eval (Con x)

= Just x ? catch (eval (Con 3 :/: (Con 2 :-: Con 2)) ) catch Nothing opr_data = opravna_fce opr_data catch (Just x) _ = x Strun seznamy 1 analogick mnoinm {x | x in Xs & p(x)} p. pouit: seznam een - simulace nedeterminizmu p.: [ x | x <- xs, p x ] -- filter p xs p.: [ f x | x <- xs] -- map f xs vlevo od |: vraz pro kadou hodnotu genertor se pid v. vpravo od |: genertor (x<-xs) nebo podm. (str) (nebo let) poad genertor: zleva doprava

? [(x,y)| x<-[1,2], y<-[3,4]] ~~> [(1,3),(1,4),(2,3),(2,4)] delitele n = [d| d<-[1..n], n `mod` d ==0] spaces n=[ | i<-[1..n]] -- i se nepouije(C) (list comprehensions) Strun seznamy 2 testy (stre) jsou boolovsk vrazy quicksort [] = [] quicksort (x:xs) = quicksort [y|y<-xs, y=x] - mrn neefektivn, xs se prochz 2x

podobn: aritmetick posloupnosti [1..5] ~~> [1,2,3,4,5] [1,3..8] ~~> [1,3,5,7] --rozdl uruje krok [1,3..] ~~> [1,3,5,7,.. --nekonen seznam Strategie vyhodnocovn redukn krok: nahrazen nkterho voln fce jej definic, piem se formln parametry nahrad aktulnmi (v dosud vyhodnocenm stavu) redukn strategie: vybr prvn redukn krok strategie: eager (ML, Scheme); normln (-kalkul); ln (Haskell); Vta: vechny redukn strategie, pokud skon, vydaj stejn

vsledek Vta: pokud njak strategie skon, pak skon i normln (a ln) sq x = x*x p: sq( sq 3) Strategie vyhodnocovn 2 eager (dychtiv), striktn red. strategie, voln hodnotou (zleva zevnit): sq(sq 3) ~> sq (3*3) ~> sq 9 ~> 9*9 ~> 81 - kad argument se vyhodnocuje prv jednou normln red. strategie, voln jmnem (zleva zvnjku): sq(sq 3)~> sq 3*sq 3 ~> (3*3)*sq 3~>9*sq 3 ~>

9*(3*3)~>9*9~>81 - nepouit argumenty se nevyhodnocuj - nevhoda: opakovan vyhodnocovn spol. podvraz (1) Ln redukn strategie ln: jako normln, ale neopakuje vyhodnocovn argument (spol. podvraz) sq(sq 3) ~> (x:=)sq 3*x(=sq 3)~> (3*3)*x(=3*3)->9*x(=9)~>81 - vyhodnocuje potebn vrazy (argumenty) prv jednou ? my_if True (0/7) (7/0{- BUM-}) --ln: bezchybn my_if p x y = if p then x else y -- dychtiv: - grafov redukce (cca 1986) vs. termov redukce - vyuv referenn transparentnost nezle, kdy se vyhodnocuje - umouje nekonen datov struktury - vyhodnocovn v case a pattern matching: vyhodnot tolik z vsledku

na konstruktory, aby se dala urit jednoznan sprvn vtev pro dal vpoet - (mn efektivn implementace ne striktn strategie: nejprve zapisuje neredukovan tvar, pak redukovan; pi pstupu nutno zjiovat, zda je term u redukovan) Obrzky Nekonen d.s. ln vyhodnocovn umouje potenciln nekonen d.s. pouijeme jen konenou st (anebo petee pam) numsFrom n = n : numsFrom (n+1) fib = 1 : 1 : [a+b | (a,b) <- zip fib (tail fib)]

factFrom = map fact (numFrom 0) Autotest: efektivnj faktoril idea: prvky seznamu budou dvojice (n,f(n)) Nekonen dat. struktury nkolik uitench procedur repeat x = x : repeat x cycle xs = xs ++ cycle xs iterate f x = x : iterate f (f x) [ f 0 (x), f 1 (x), f 2 (x), f 3 (x), ] p.: jednotkov matice jedn_mat = iterate (0:) -- dal dky, 0: se pid na zatek

(1:repeat 0) -- prvn dek 1:0:0:0: jedn_mat = [ 1:0:0:0: , 0:1:0:0: , 0:0:1:0: , Nekonen dat. struktury a fce - funkce pst kompatibiln s lnm vyhodnocovnm: and1 True True = True -- nen ln ve 2. arg. and1 _ _ = False and2 True x = x -- je ln and2 False _ = False

- zpracovn nekonench struktur: - mt fce, kter odeberou pouze potebnou st d.s. (take, takeWhile, ... getWord) - mt fce, kter zpracuj nekon. d.s. na nekon. d.s. (map, zip, filter, drop, dropWhile ...) past: [ x | x<-[0..], x<4 ] ~~> [0,1,2,3, - striktn funkce: vyhodnot vdy svj argument (pln) - Pro striktn funkce plat : f ~> Polymorfn typy - odvozovn typ unifikac f :: (t,Char) -> (t,[Char]) f (x,c) = (x,[a..c]) g:: (Int,[u])->Int

g (m,l) = m+length l h = g.f -- (.):: (b->c)->(a->b)->(a->c) -- (t,[Char]) unifikuj s (Int,[u]) h::(Int,Char)->Int Polymorfn typy polymorfn konstanty, funkce: kad vskyt se typuje zvl length([]++[1])+length([]++[True]) OK :: Int -> Int :: Bool -> Int --obecn :: a -> Int promnn: m pouze jeden (polymorfn) typ * length(x++[1])+length(x++[True]) -- NE x::?

Typov tdy - idey ne vechny operace jsou definovny na vech typech typov tda: abstrakce tch typ, kter maj definovny dan operace - tento mechanizmus odpovd ad hoc polymorfizmu, tj. peten klov slova: class - zaveden typov tdy instance - definovn typu jako prvku typov tdy, spolu s definovnm operac typov kontext: podmnky na typy eqpair :: (Eq a),(Eq b) => (a,b)->(a,b)->Bool eqpair (x1,x2) (y1,y2) = x1==y1 && x2 ==y2 Typov tdy

definice tdy typ, kter lze porovnvat class Eq a where (==),(/=) :: a -> a -> Bool x/=y = not (x==y) -- defauln definice typ rovnosti (==) :: (Eq a) => a -> a -> Bool instance Eq Int where x == y = intEq x y -- vest. fce instance (Eq a) => Eq (Tree a) where Leaf a == Leaf b = a == b (Branch l1 r1) == (Branch l2 r2) = (l1==l2) && (r1==r2)

_ == _ = False Funkce vych d map map f xs aplikuje funkci f na kad prvek seznamu xs a vrac seznam odpovdajcch vsledk map :: (a->b) -> [a] ->[b] map f [] = [] map f (x:xs) = (f x) : (map f xs) ? map succ [1,2,3] ~~> [2,3,4] ? map (add 2) [3,4] ~~> [5,6] ? map (+) [7,8] ~~> [(7+),(8+)]

filter (ze souboru standard.pre) filter p xs returns the sublist of xs -- containing those elements which satisfy the predicate p. filter filter _ [] filter p (x:xs) | p x | otherwise :: (a -> Bool) -> [a] -> [a] = [] = x : xs'

= xs' where xs' = filter p xs Pklad: zip -- zip2 z1 z2 -- ze dvou seznam prvk vyrob seznam dvojic -- seznamy mohou bt rzn dlouh, -- zip2 skon, kdy skon jeden z argument zip2 :: [a] -> [b] -> [(a,b)] zip2 (x:xs) (y:ys) = (x,y) : zip2 xs ys zip2 _ _ = [] map - varianty synchronn pechod pes dva seznamy

map2 :: (a->b->c) -> [a]->[b]->[c] map2 f x y = map (\(x,y)-> f x y) (zip x y) p: plus_vektor x y = map2 (+) x y operace s konstantou map_c :: (a->b->c)-> a->[b]->[c] map_c f c x = map (\x->f c x) x lokln x v definici map_c f c x = map2 f (map (\_->c) x) x generujeme pomocn vektor ze samch konstant pro matice map_m :: (a->b)-> [[a]] -> [[b]] map_m f x = map (map f) x

Typovn: map_m explicitn typy pro vraz map ( map f ) x aktuln typy jsou v hornch indexech map ([ a] [ b]) [[ a]] [[ b]] ( a b) [ a] [ b] a b [[ a]]

( map f ) x [ a] [ b] map pro jin d.s. pro binrn stromy rozbor podle konstruktoru mapTree :: (a->b) -> Tree a -> Tree b mapTree f (Leaf a) = Leaf (f a) mapTree f (Branch l r) = Branch (mapTree f l)

(mapTree f r) n-rn stromy data NTree a = Tr a [NTree a] mapNT :: (a->b) -> NTree a -> NTree b mapNT f (Tr x trees) = Tr (f a) (map (mapNT f) trees) Funkce jako vsledky typ aritm. vrazu a jeho peklad do funkce data Tvyraz a = Con a | Var String | Tvyraz a :+: Tvyraz a | Tvyraz a :*: Tvyraz a ? (Con 2 :*: Var "x") :+: Con 1 -- vstup zdarma cc :: (Tvyraz a) -> a -> a

cc (Con a) = \x -> a cc (Var _) = \x -> x cc (a :+: b) = \x -> (cc a x) + (cc b x) cc (a :*: b) = \x -> (cc a x) * (cc b x) ekv. cc (a:+:b) x = cc a x + cc b x Autotest Hornerovo schema je dan seznam koeficient, vyrobte k nmu funkci, kter pro dan vstup x spote hodnotu v bod x Obecn strukt. rekurze - seznamy pro seznamy, doprava rekurzivn

nahrazovn konstruktor funkcemi foldr :: (a -> b -> b) -> b -> [a] -> b foldr f z [] = z foldr f z (x:xs) = f x (foldr f z xs) length xs = foldr (\_ n->n+1) 0 xs varianty doleva rekurzivn na neprzdnch seznamech Obecn strukt. rekurze - stromy foldT :: (a->b)->(b->b->b)->Tree a->b

foldT fL fB (Leaf a) = fL a foldT fL fB (Branch l r) = fB (foldT fL fB l) (foldT fL fB r) hloubka t = (\_->1) (\x y -> 1+max x y) t Pklad: slvn merge merge [] ys merge xs [] merge (x:xs) (y:ys) | x <= y | otherwise

:: Ord a => [a]->[a]->[a] = ys = xs = x : merge xs (y:ys) = y : merge (x:xs) ys (Rozirujc st) (potenciln) nekonen d.., nap. seznamy (funkce pro) vbr konench st (typov) tdy a instance: nap.: Eq, Ord vzor @ (as) (I/O, show, read) (moduly)

Vzor @ (as) neodmtnuteln vzor @ podsti mohou bt odmtnuty potebujeme souasn strukturu po stech i vcelku p.: f [email protected](x:xs) = x:s mn efektivn: f (x:xs) = x:x:xs (Vstup) show pokraovn Blokov struktura - let Let - (vnoen) mnoina vazeb pro vraz vazby jsou vzjemn rekurzivn

konstrukce let je vraz f x y = let norma (x,y) = sqrt (x^2+y^2) prumer x y = (x+y)/2.0 in prumer (norma x) (norma y) let je pouiteln pro optimalizaci spolench podvraz Blokov struktura - where lokln vazby pes nkolik steench rovnost f x y | y >z | y==z | y

= ... where z = x*x Rekurze a iterace: Factorial fact 0 = 1 fact (n+1) = (n+1)*fact n ? fact 4 fact 4 ~~> (3+1)* fact 3 ~~> 4* fact 3 ~~> 4*(3*fact 2) ~~> 4*(3*(2*fact 1)) ~~> 4*(3*(2*(1* fact 0))) ~~> 4*(3*(2*(1* 1 )))

~~> 24 pracuje v linern pamti Faktorial - iterativne fact5 n = fact_iter n 0 1 where fact_iter n k f | n==k = f | True = fact_iter n (k+1) ((k+1)*f) ? fact5 4 fact5 4 ~~> fact_iter 4 0 1 ~~> fact_iter 4 1 1 ~~> fact_iter 4 2 2 ~~> fact_iter 4 3 6 ~~> fact_iter 4 4 24

~~> 24 pracuje v konstantn pamti DC: Fibonacciho sla, stav: seznam nebo dvojice Rozloen, layout Dvourozmrn syntax - pedpoklad: definice jsou zarovnny do sloupc za klovmi slovy: where, let, of prvn znak uruje sloupec (indentaci) jakkoli znak nalevo kon vnoen explicitn skupiny definic let {a=1 ; b=2} in a+b

Recently Viewed Presentations

  • KPA presentation - lossfreerx.com

    KPA presentation - lossfreerx.com

    Account Management is also available through KPA and includes the following: RMC Onboarding Configuration . Your Account Specialist will help you tailor an implementation strategy for two applications of the RMC to fit your organization's needs.
  • FORENSIC SCIENCE - Ironwood Wilson

    FORENSIC SCIENCE - Ironwood Wilson

    CORPUS DELICTI "Body of the Crime" You must prove that a crime occurred that the person charged with the crime was responsible for the crime Top Reasons for Committing a Crime Money Revenge Emotion—love, hate, anger Source of Evidence Body...
  • Welcome to E-Medix 4.80

    Welcome to E-Medix 4.80

    Welcome to E-Mobile 3.20 Purchase Voucher Servicing of Mobiles & Accessories Servicing Bill Bank-Cash Transfer (Contra) Day Book Details Thanks for your Patience Only main options are given in the presentation.
  • Latin II FCA Review - All Things Latin at Milton HS

    Latin II FCA Review - All Things Latin at Milton HS

    17. Caecilius, his factis, laborarecoepit. A. doing these things B. about to do these things . C. with these things having been done
  • Dentatorubral-pallodoluysian Atrophy (DRPLA)

    Dentatorubral-pallodoluysian Atrophy (DRPLA)

    Dentatorubral-pallodoluysian Atrophy (DRPLA) DRPLA Trinucleotide Repeat Disorder CAG repeat on Chromosome 12 6 to 35 normal, 48 to 93 mutation DRPLA disease named after DRPLA gene Family inherited and anticipation illness The age of onset is from one to 62...
  • Analysis of Contract-type and Acquisition Performance

    Analysis of Contract-type and Acquisition Performance

    The data for development contracts. There were 433 contracts in the sample. Break-down by contract-type: 74 CPIF. 108 CPAF. 100 CPFF. 78 fixed-price. 73 hybrid (mixture of CLIN contract types)
  • Les filières de soins - WordPress.com

    Les filières de soins - WordPress.com

    Réseaux de santé en Martinique Réseau Président (e) Sigle GIP RAM Auguste ARMET ERMANCIA Pr Didier SMADJA Réseau Autonomie Martinique Denise DESORMEAUX Gérontologique Dr Lidvine GODAERT Oncologique Dr Pierre HELENON Soins palliatifs Anne-Marie Magdeleine Respi-R Alex BIRON Périnatalité Chemin clinique...
  • Instrumental Chemistry - Pace University

    Instrumental Chemistry - Pace University

    Atomic Mass Spectrometry Atomic mass The mass of a single atom, usually expressed in atomic mass units (amu) Most of the mass of an atom is concentrated in the protons and neutrons contained in the nucleus Each proton or neutron...