Kalábovic wikina

pitel:flp:start

# Funkcionální a logické programování

## Lambda kalkul

• α-konverze – λx.xyα λz.zy, substituce1)
• β-konverze – (λxz.xz)(xy) →β λz.xyz, aplikace funkce
• η-konverze – λx.(uv)xη uv
T λxy.x λxy.xy λxy.x λxy.x
F λxy.y λxy.y λxy.yx λxy.xy
NOT λx.xFT λx.xz.F)T λp.pFr.T) λx.xFT
AND λxy.xyF λxy.yz.x)F λab.abr.F) λxy.xyF
OR λxy.xTy λxy.yz.T)x λab.aTr.b) λxy.xTy
XOR λxy.x(NOT y)y λxy.xz.(NOT y))y λxy.x(NOT y)(λz.y) λxy.x(NOT y)y
EQ λxy.xy(NOT y) λxy.xz.y)(NOT y) λxy.xyz.(NOT y)) λxy.xy(NOT y)
<Presci> Pitel: no ne vsechny, ale kdyz ti true nebo false budou vracet dve hodnodty (LET TRUE = \a b.b a, tak tu jednu musis nejak zabit (treba v notu)
<Presci> a zabijes ji tam, ze ji nahradis \a.False treba, takze "a" se zahodi a zbyte False
 0, 1, 2, 3, … λfx.x λfx.fx λfx.f(fx) λfx.f(f(fx)) λfx.fⁿx λnfx.f(nfx) λmnfx.mf(nfx) λmnf.m(nf) λmn.nm λm.m(λv.FALSE)TRUE λctf.ctf λfse.efs λp.p(λab.a)2) λp.p(λab.b)3)

## Strukturální indukce

foldr            :: (a -> b -> b) -> b -> [a] -> b
foldr f z []     =  z
foldr f z (x:xs) =  f x (foldr f z xs)
foldl            :: (a -> b -> a) -> a -> [b] -> a
foldl f z []     =  z
foldl f z (x:xs) =  foldl f (f z x) xs
map :: (a -> b) -> [a] -> [b]
map f []     = []
map f (x:xs) = f x : map f xs
(++) :: [a] -> [a] -> [a]
[]     ++ ys = ys
(x:xs) ++ ys = x : (xs ++ ys)
take                   :: Int -> [a] -> [a]
take n _      | n <= 0 =  []
take _ []              =  []
take n (x:xs)          =  x : take (n-1) xs
drop                   :: Int -> [a] -> [a]
drop n xs     | n <= 0 =  xs
drop _ []              =  []
drop n (_:xs)          =  drop (n-1) xs
head             :: [a] -> a
head []          =  error "Prelude.head: empty list"
tail             :: [a] -> [a]
tail (_:xs)      =  xs
tail []          =  error "Prelude.tail: empty list"
last             :: [a] -> a
last [x]         =  x
last (_:xs)      =  last xs
last []          =  error "Prelude.last: empty list"
init             :: [a] -> [a]
init [x]         =  []
init (x:xs)      =  x : init xs
init []          =  error "Prelude.init: empty list"
length           :: [a] -> Int
length []        =  0
length (_:l)     =  1 + length l
filter :: (a -> Bool) -> [a] -> [a]
-- filter p xs = [x | x <- xs, p x]
filter p []                 = []
filter p (x:xs) | p x       = x : filter p xs
| otherwise = filter p xs
takeWhile               :: (a -> Bool) -> [a] -> [a]
takeWhile p []          =  []
takeWhile p (x:xs)
| p x       =  x : takeWhile p xs
| otherwise =  []
dropWhile               :: (a -> Bool) -> [a] -> [a]
dropWhile p []          =  []
dropWhile p xs@(x:xs')
| p x       =  dropWhile p xs'
| otherwise =  xs
zipWith          :: (a->b->c) -> [a]->[b]->[c]
zipWith z (a:as) (b:bs)
=  z a b : zipWith z as bs
zipWith _ _ _    =  []

## Prolog

1)
Bacha na volné a vázané proměnné!
2)
TRUE
3)
FALSE
/var/www/wiki/data/pages/pitel/flp/start.txt · Poslední úprava: 12. 09. 2023, 08.45:48 autor: pitel