FMFP
FormalMethodsAndFunctionalProgramming
FormalMethodsAndFunctionalProgramming
Haskel command for absolutvalue of x
(abs x)
REPLACE the following Haskel command with the let syntax:
gcdInt:: Int->int->Int
gcdInt x y = gcdiv (abs x) (abs y)
gcdInt :: Int->Int->Int
gcdInt x y
let (x',y') = (if x>= 0 then x else -x, if y >= 0 then y else -y)
in gcdiv x' y'
absolut value of a complex number (a +ib)
conj value of a complex number (a+ib)
multiplication of complex numbers (a+ib)(c+ib)
sqrt(a^2 + b^2)
a-ib
(ac+bd)+i(ad+cb)
Evaluation Rules for Haskel
from outside to inside
from left to right
Order the symboles according to strongness
(strong to week)
-> , /\ , V, ¬
¬,/\,V,->
Is -> right or left associaltive?
right
Is /\ and V right or left-associative?
left
We define A <-> B as (A->B)/\(B->A). Provide suitable introduction and elimination rules for <->.
see image
Truth table of an implication a->b
true true
true false
false true
false false
true,false,true,true
command for float division in haskel?
/
Command for integer division in haskel
div x y
Write the following set comprehesnsion into haskel
S = {2*x | x \in N, x <=10 ,x*2 >= 12]
[2*x|x<-[1..10],x*2>=12]
Definition of foldr
foldr :: (a->b->b) -> b -> [a] -> b
foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)
Defintion of foldl?
foldl :: (b->a->b) -> b -> [a] -> b
foldl f e [] = e
foldl f e (x:xs) = foldl f (f e x) xs
Definition of zipWith
zipWith :: (a->b->c)->[a]->[b]->[c]
zipWith f (x:xs) (y:ys) = f x y : zipWith f xs ys
zipWith f _ _ = [ ]
Definition of uncurry
uncurry :: (a->b-> c) -> (a,b) -> c
uncurry g = f
where f (x,y) = g x y
definition of map
map :: (a->b) -> [a] -> [b]
map f [] = []
map f (x:xs) = f x : map f xs
definition of filter
filter :: (a-> Boll) -> [a] -> [a]
filter p [] = []
filter p (x:xs)
| p x = x :filter p xs
| otherwise = filter p xs
definition of iterate
iterate :: (a->a) -> a -> [a]
iterate f x = x : iterate f (f x)
definition of sum
sum :: (Num a) => [a] -> a
sum = foldl (+) 0
or
sum l = sum' l 0
where
sum' [] a = a
sum' (x:xs) a = sum' xs (a+x)
define maximum
maximum :: (Ord a) => [a] ->
maximum [] = errorEmptyList "maximum"
maximum xs = foldl1 max xs
define replicate
replicate :: Int-> a ->[a]
replicate n x = take n (repeat x)
rewrite the function
filterMap :: (b->Bool) ->(a->b) -> [a] -> [b]
filterMap p f = filter p . map f
starting with
filterMap' p f = foldr aux e
filterMap' p f = foldr aux e
where aux = \x xs -> if p (f x) then f x:xs else xs
e = []
typ of (\x y z -> x (y z))
(b->a)->(c->b)->c->a
:t (\f -> (\h -> (f,h))
a->b->(a,b)
:t map (elem 0)
Num a => [[a]] ->[Bool]
:t (\x -> x (<))
(b->a)->(c->b)->c->a
Implement a breadth-first traversal on trees with the data type Tree t. Your function should traverse a given tree in a breadth first manner and return a list with the elements that are stored in the tree.
data Tree t = Leaf | Node t (Tree t) (Tree t)
bfs :: Tree a -> [a]
bfs x = traverse [x]
traverse :: [Tree a] -> [a]
traverse [] = []
traverse ts = rootlables ++ traverse childern
where rootlables = [x| Node x _ _ <- ts]
childern = [x | Node _ l r <- ts, t <- [l,r]]
lazy and eager ev. of
(\x -> x (\y -> x y)) (\x -> (\y -> y) x)
(i) lazy evaluation of f g:
(\x -> x (\y -> x y)) (\x -> (\y -> y) x)
t2 is substituted without evaluation
= (\x -> (\y -> y) x) (\y -> (\x -> (\y -> y) x) y)
t2 is substituted without evaluation
= (\y -> y) (\y -> (\x -> (\y -> y) x) y)
t2 is substituted without evaluation
= (\y -> (\x -> (\y -> y) x) y)
evaluation stops since no evaluation under an abstraction
(ii) eager evaluation of f g:
(\x -> x (\y -> x y)) (\x -> (\y -> y) x)
since t1 is evaluated, t2 is evaluated (prior to substitution)
= (\x -> x (\y -> x y)) (\x -> x)
substitution of t2
= (\x -> x) (\y -> (\x -> x) y)
since evaluation is carried out under an abstraction and since t2
is evaluated prior to substitution, we obtain
= (\x -> x) (\y -> y)
substitution of t2
= \y -> y
The type of multivariate polynomials over variables of type 'a' with
'Integer' coefficients is defined as follows.
> type Poly a = [(Integer, [a])]
write a function evalPoly, such taht evalPoly f p computes the value of the polynominal p where every variabel x is replace by the value f x
> evalPoly :: (a -> Integer) -> Poly a -> Integer
> evalPoly f p = sum [ a * product (map f xs) | (a, xs) <- p ]
-
- 1 / 31
-
Flashcards
Haskel command for absolutvalue of x
(abs x)
REPLACE the following Haskel command with the let syntax:
gcdInt:: Int->int->Int
gcdInt x y = gcdiv (abs x) (abs y)
gcdInt :: Int->Int->Int
gcdInt x y
let (x',y') = (if x>= 0 then x else -x, if y >= 0 then y else -y)
in gcdiv x' y'
absolut value of a complex number (a +ib)
conj value of a complex number (a+ib)
multiplication of complex numbers (a+ib)(c+ib)
sqrt(a^2 + b^2)
a-ib
(ac+bd)+i(ad+cb)
Evaluation Rules for Haskel
from outside to inside
from left to right
Order the symboles according to strongness
(strong to week)
-> , /\ , V, ¬
¬,/\,V,->
Is -> right or left associaltive?
right
Is /\ and V right or left-associative?
left
We define A <-> B as (A->B)/\(B->A). Provide suitable introduction and elimination rules for <->.
see image
Truth table of an implication a->b
true true
true false
false true
false false
true,false,true,true
command for float division in haskel?
/
Command for integer division in haskel
div x y
Write the following set comprehesnsion into haskel
S = {2*x | x \in N, x <=10 ,x*2 >= 12]
[2*x|x<-[1..10],x*2>=12]
Definition of foldr
foldr :: (a->b->b) -> b -> [a] -> b
foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)
Defintion of foldl?
foldl :: (b->a->b) -> b -> [a] -> b
foldl f e [] = e
foldl f e (x:xs) = foldl f (f e x) xs
Definition of zipWith
zipWith :: (a->b->c)->[a]->[b]->[c]
zipWith f (x:xs) (y:ys) = f x y : zipWith f xs ys
zipWith f _ _ = [ ]
Definition of uncurry
uncurry :: (a->b-> c) -> (a,b) -> c
uncurry g = f
where f (x,y) = g x y
definition of map
map :: (a->b) -> [a] -> [b]
map f [] = []
map f (x:xs) = f x : map f xs
definition of filter
filter :: (a-> Boll) -> [a] -> [a]
filter p [] = []
filter p (x:xs)
| p x = x :filter p xs
| otherwise = filter p xs
definition of iterate
iterate :: (a->a) -> a -> [a]
iterate f x = x : iterate f (f x)
definition of sum
sum :: (Num a) => [a] -> a
sum = foldl (+) 0
or
sum l = sum' l 0
where
sum' [] a = a
sum' (x:xs) a = sum' xs (a+x)
define maximum
maximum :: (Ord a) => [a] ->
maximum [] = errorEmptyList "maximum"
maximum xs = foldl1 max xs
define replicate
replicate :: Int-> a ->[a]
replicate n x = take n (repeat x)
rewrite the function
filterMap :: (b->Bool) ->(a->b) -> [a] -> [b]
filterMap p f = filter p . map f
starting with
filterMap' p f = foldr aux e
filterMap' p f = foldr aux e
where aux = \x xs -> if p (f x) then f x:xs else xs
e = []
typ of (\x y z -> x (y z))
(b->a)->(c->b)->c->a
:t (\f -> (\h -> (f,h))
a->b->(a,b)
:t map (elem 0)
Num a => [[a]] ->[Bool]
:t (\x -> x (<))
(b->a)->(c->b)->c->a
Implement a breadth-first traversal on trees with the data type Tree t. Your function should traverse a given tree in a breadth first manner and return a list with the elements that are stored in the tree.
data Tree t = Leaf | Node t (Tree t) (Tree t)
bfs :: Tree a -> [a]
bfs x = traverse [x]
traverse :: [Tree a] -> [a]
traverse [] = []
traverse ts = rootlables ++ traverse childern
where rootlables = [x| Node x _ _ <- ts]
childern = [x | Node _ l r <- ts, t <- [l,r]]
lazy and eager ev. of
(\x -> x (\y -> x y)) (\x -> (\y -> y) x)
(i) lazy evaluation of f g:
(\x -> x (\y -> x y)) (\x -> (\y -> y) x)
t2 is substituted without evaluation
= (\x -> (\y -> y) x) (\y -> (\x -> (\y -> y) x) y)
t2 is substituted without evaluation
= (\y -> y) (\y -> (\x -> (\y -> y) x) y)
t2 is substituted without evaluation
= (\y -> (\x -> (\y -> y) x) y)
evaluation stops since no evaluation under an abstraction
(ii) eager evaluation of f g:
(\x -> x (\y -> x y)) (\x -> (\y -> y) x)
since t1 is evaluated, t2 is evaluated (prior to substitution)
= (\x -> x (\y -> x y)) (\x -> x)
substitution of t2
= (\x -> x) (\y -> (\x -> x) y)
since evaluation is carried out under an abstraction and since t2
is evaluated prior to substitution, we obtain
= (\x -> x) (\y -> y)
substitution of t2
= \y -> y
The type of multivariate polynomials over variables of type 'a' with
'Integer' coefficients is defined as follows.
> type Poly a = [(Integer, [a])]
write a function evalPoly, such taht evalPoly f p computes the value of the polynominal p where every variabel x is replace by the value f x
> evalPoly :: (a -> Integer) -> Poly a -> Integer
> evalPoly f p = sum [ a * product (map f xs) | (a, xs) <- p ]
