Download ALPII Práctica 5

ALPII
Práctica 5
Bernardo Garcı́a Fuentes
1
[Ej. 1] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
data TipTree a = Tip a | Join (TipTree a) (TipTree a)
deriving Show
-- Ver pag. 157 del Bird
foldTip :: (a -> b) -> (b -> b -> b) -> TipTree a -> b
foldTip f g (Tip x) = f x
foldTip f g (Join xt yt) = g (foldTip f g xt) (foldTip f g yt)
{Ej. de un arbol
.
/ \
1
.
/ \
2
3
Join (Tip 1) (Join (Tip 2) (Tip 3))
-}
enlistar :: a -> [a]
enlistar x = [x]
aplanar = foldTip enlistar (++)
heighTip :: TipTree a -> Int
heighTip (Tip x) = 0
heighTip (Join xt yt) = 1 + (heighTip xt ‘max‘ heighTip yt)
heightTipf :: TipTree a -> Int
heightTipf = foldTip (const 0) fun where fun m n = 1 + (max m n)
leaves :: TipTree a -> Int
leaves (Tip x) = 1
leaves (Join xt yt) = leaves xt + leaves yt
nodes :: TipTree a -> Int
nodes (Tip x) = 0
nodes (Join xt yt) = 1 + nodes xt + nodes yt
mirrorTip :: TipTree a -> TipTree a
mirrorTip (Tip x) = Tip x
mirrorTip (Join xt yt) = Join (mirrorTip yt) (mirrorTip xt)
mapTip :: (a -> b) -> TipTree a -> TipTree b
mapTip f (Tip x) = Tip (f x)
mapTip f (Join xt yt) = Join (mapTip f xt) (mapTip f yt)
[Ej. 2] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
data BinTree a = Empty | Bin a (BinTree a) (BinTree a)
deriving Show
1
{ej.
1
/
\
3
/
\
4
5
/ \
/ \
E
E E
E
2
/ \
E
E
Bin 1 ((Bin 2 (Empty Empty)) (Bin 3 (Bin 4 (Empty Empty)) (Bin 5 (Empty Empty)))
-}
foldBin :: (a -> b -> b -> b) -> b -> BinTree a -> b
foldBin f e Empty = e
foldBin f e (Bin x xt yt) = f x (foldBin f e xt) (foldBin f e yt)
mapBin :: (a -> b) -> BinTree a -> BinTree b
-- mapBin f (Bin x xt yt) = foldBin fun (Empty) (Bin x xt yt) where fun w wt zt = (Bin (f w) wt zt)
mapBin f = foldBin fun (Empty) where fun w wt zt = (Bin (f w) wt zt)
heighBin :: BinTree a -> Int
heighBin = foldBin fun 0 where fun x m n = 1 + (max m n)
mirrorBin :: BinTree a -> BinTree a
mirrorBin = foldBin fun Empty where fun w m n = Bin w n m
[Ej. 3] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
data Nat = Zero | Succ Nat
deriving Show;
-----
ej:
0 -> Zero
1 -> Succ Zero
2 -> Succ (Succ Zero)
data Zeta = Base | Izq Nat | Der Nat
deriving Show;
-----
ej:
0 -> Zero
1 -> Der Succ Zero
-1 -> Izq Succ Zero
foldZ
foldZ
foldZ
foldZ
foldZ
foldZ
:: a -> (a
e f g Base
e f g (Izq
e f g (Der
e f g (Izq
e f g (Der
-> a)
= e
Zero)
Zero)
(Succ
(Succ
-> (a -> a) -> Zeta -> a
= foldZ e f
= foldZ e f
x)) = foldZ
x)) = foldZ
g
g
e
e
Base
Base
f g (Izq x)
f g (Der x)
previo :: Zeta -> Zeta
previo (Izq x) = Izq (Succ x)
2
previo (Der (Succ x)) = Der x
previo Base = Izq Zero
siguiente
siguiente
siguiente
siguiente
:: Zeta -> Zeta
(Izq (Succ x)) = Izq x
(Der x) = Der (Succ x)
Base = Der Zero
[Ej. 4] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
data GenTree a = Gen a [GenTree a]
deriving Show;
-- Ej
-- Gen 1 [Gen 1 [], Gen 2 []]
foldGen :: (a -> b -> c) -> ([c] -> b) -> GenTree a -> c
foldGen f g (Gen label hijos) = f label (g (map (foldGen f g) hijos))
sumGen :: GenTree Int -> Int
sumGen = foldGen (+) fun where fun x = if x == [] then 0 else foldr (+) 0 x
doble :: GenTree Int -> GenTree Int
doble = foldGen fun id where fun x y = Gen (x*2) y
mapGen :: (a -> b) -> GenTree a -> GenTree b
mapGen f = foldGen fun id where fun x y = Gen (f x) y
mirrorGen :: GenTree a -> GenTree a
mirrorGen = foldGen fun id where fun x y = Gen x (reverse y)
[Ej. 5] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
data Seq a = Nil | Unit a | Cat (Seq a) (Seq a)
deriving (Show, Eq);
-- ej:
-- Cat Nil (Cat (Unit 1) (Unit 2))
appSeq :: Seq a -> Seq a -> Seq a
appSeq x y = Cat x y
conSeq :: a -> Seq a -> Seq a
conSeq x y = Cat (Unit x) y
lenSeq
lenSeq
lenSeq
lenSeq
:: Seq a -> Int
Nil = 0
(Unit x) = 1
(Cat x y) = lenSeq x + lenSeq y
revSeq
revSeq
revSeq
revSeq
:: Seq a -> Seq a
Nil = Nil
(Unit x) = Unit x
(Cat x y) = Cat (revSeq y) (revSeq x)
headSeq :: Seq a -> a
3
headSeq Nil = error "No hay primer elemento"
headSeq (Unit a) = a
headSeq (Cat x y) = case (x,y) of
(Nil,x) -> headSeq y
(_,_)
-> headSeq x
tailSeq
tailSeq
tailSeq
tailSeq
:: Seq a -> Seq a
Nil = Nil
(Unit x) = Nil
(Cat x y) = case (x,y) of
(Nil,_)
-> Cat x (tailSeq y)
(Unit x,_) -> y
(_,_)
-> Cat (tailSeq x) y
normSeq
normSeq
normSeq
normSeq
:: Seq a -> Seq a
Nil = error "No se puede reducir"
(Unit x) = Unit x
(Cat x y) = case (x,y) of
(Nil, Nil)
->
(Nil, x)
->
(x, Nil)
->
(x, Cat Nil Nil) ->
(x, y)
->
Nil
normSeq x
normSeq x
normSeq x
Cat (normSeq x) (normSeq y)
eqSeq :: Eq a => Seq a -> Seq a -> Bool
eqSeq x y = case (x,y) of
(Nil, Nil)
-> True
(Nil, _ )
-> False
(_ , Nil)
-> False
(Unit a, Unit b)
-> if (a == b) then True else False
(Unit a, Nil )
-> False
(Cat a b, Cat c d) -> (eqSeq a c) && (eqSeq b d)
(Cat a b, _ )
-> False
(_, Cat a b )
-> False
[Ej. 6] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f e [] = e
foldr f e (x:xs) = f x (foldr f e xs)
foldl :: (b -> a -> b) -> b -> [a] -> b
foldl f e [] = e
foldl f e (x:xs) = foldl f (f e x) xs
-*- 1er Teorema de dualidad
Sea f una funcion
- Asociativa
- Elemento Neutro e
==> f a (f b c) = f (f a b) c
(1) = (2)
==> f e a = a
Entonces para toda lista finita xs
4
foldr f e xs = foldl f e xs
-*- Antes vamos a demostrar que
f x (foldl f y xs) = foldl f (f x y) xs
(*)
Lo demostramos con una lista finita
foldl f x [x0. x1, x2]
= foldl f (f x x0) [x1, x2]
= foldl f (f (f x x0) x1) [x2]
= foldl f (f (f (f x x0) x1) x2)
= f (f (f x x0) x1) x2
-- x asociatividad (2) -> (1), a
= f (f x x0) (f x1 x2)
-- x asociatividad (2) -> (1), a
= f x (f x0 (f x1 x2))
-- x asociativadad (1) -> (2), a
= f x (f (f x0 x1) x2)
= f x (foldl f x0 [x1, x2])
[]
= (f e x0), b = x1, c = x2
= e, b = x0, c = (f x1 x2)
= x0, b = x1, c = x2
.: foldl f (f x y) xs = f x (foldl f y xs)
-*- Demostramos para el caso base []
foldr f e []
= e
= foldl f e []
-*- Suponemos que vale
foldr f e xs = foldl f e xs
(1)
-*- Probamos para (x:xs)
foldr f e (x:xs)
= f x (foldr f e xs)
-- x h.i.
= f x (foldl f e xs)
-- x (*)
= foldl (f x e) xs
-- x elemento neutro
= foldl (f e x) xs
= foldl e (x:xs)
-*- 2do Teorema
Sea f y g dos funciones que se asocian entre si
y operar con e a la derecha de f es equivalente
a operar con e a la izquierda de g
- f a (g b c) = g (f a b) c
- f c e = g e c
(1)
(2)
5
Entonces para toda lista finita xs
foldr f e xs = foldl g e xs
-*- Demostramos para el caso base []
foldr f e []
= e
= foldl g e []
-*- Probamos para (x:xs)
foldr f e (x:xs)
= f x (foldr f e xs)
-- x h.i.
= f x (foldl g e xs)
foldl g e (x:xs)
= foldl g (g e x) xs
-- x (2)
= foldl g (f x e) xs
-*- Antes de demostrar la igualdad vamos a mostrar que
f x (foldl g y xs) = foldl g (f x y) xs
(3)
Lo probamos con una lista finita xs
f x (foldl g
= f x (foldl g
= f x (foldl g
= f x (foldl g
= f x (g (g (g
-- x (1)
= ??????
y [x0. x1, x2])
(g y x0) [x1, x2])
(g (g y x0) x1) [x2])
(g (g (g y x0) x1) x2) [])
y x0) x1) x2))
-- x (3)
= f x (foldl g e xs)
-*- 3er Teorema
Para todas las listas finitas xs
foldr f e xs = foldl (flip f) e (reverse xs)
donde flip f x y = f y x
-*- Demostramos para el caso base []
foldr f e []
= e
foldl (flip f) e (reverse [])
= foldl (flip f) e []
6
= e
-*- Probamos para (x:xs)
foldr f e (x:xs)
= f x (foldr f e xs)
-- x h.i.
= f x (foldl (flip f) e (reverse xs))
= ?????
[Ej. 7] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
-*- foldl f a (xs ++ ys) = foldl f (foldl f a xs) ys
-*- Caso base []
foldl f a ([] ++ ys)
= foldl f a ys
foldl f (foldl f a []) ys
= foldl f a ys
-*- Probamos para (x:xs)
foldl f a ((x:xs) ++ ys)
= foldl f a (x:(xs ++ ys))
= foldl f (f a x) (xs ++ ys)
-*- Sabemos que
f x (foldl f y xs) = foldl f (f x y) xs
(*)
-- x (*)
= f x (foldl f a (xs ++ ys))
-- x h.i.
= f x (foldl f (foldl f a xs) ys)
-- x (*)
= foldl f (f x (foldl f a xs)) ys)
-- x (*)
= foldl f (foldl f (f a x) xs) ys
= foldl f (foldl f a (x:xs)) ys
= foldl f a ((x:xs) ++ ys)
.: foldl f a ((x:xs) ++ ys) = foldl f (foldl f a (x:xs)) ys
.: foldl f a (xs ++ ys) = foldl f (foldl f a xs) ys
[Ej. 8] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
g :: Int -> Int -> Int
g x y = x + 10 * y
{Sea xs una lista finita
7
=
=
=
=
=
=
=
=
=
foldl g 0 [x0, x1, x2, ... , xn]
foldl g (g 0 x0) [x1, x2, ... , xn]
foldl g (g (g 0 x0) x1) [x2, ... , xn]
foldl g ( ... (g (g (g (g 0 x0) x1) x2) ... ) xn) []
g ( ... (g (g (g 0 x0) x1) x2) ... ) xn
g ( ... (g (g (0 + 10*x0) x1) x2) ...) xn
g ( ... (g ((0 + 10*x0) + 10*x1) x2) ...) xn
g ( ... (g ((0 + 10*x0) + 10*x1) + 10*x2) ...) xn
(0 + 10*x0) + 10*x1 + 10*x2 + ... + 10*xn
10*(x0 + x1 + x2 + ... + xn)
=
=
=
=
=
=
=
=
=
=
foldr g 0 [x0, x1, ... , xn]
g x0 (foldr g 0 [x1, ... , xn])
g x0 (g x1 ( ... (foldr g 0 [xn]) ... )
g x0 (g x1 ( ... (g xn (foldr g 0 [])) ... )
g x0 (g x1 ( ... (g xn 0) ... )
g x0 (g x1 ( ... (xn + 10*0) ... )
g x0 (g x1 ( ... (xn) ... )
g x0 (g x1 (x2 + 10*(... + 10*(x(n-1)+ 10*xn)))
g x0 (x1 + 10*(x2 + 10*(... + 10*(x(n-1) + 10*xn) ... )
x0 + 10*(x1 + 10*(x2 + 10*(... + 10*(x(n-1) + 10*xn) ... )
(10^0)*x0 + (10^1)*x1 + (10^2)*x2 + ... + (10^n)*xn
-*- 1er Teorema
foldr g e xs = foldl g e xs
foldr g 0 [1,2,3] = 321
foldl g 0 [1,2,3] = 60
.: No se cumple
-*- 2do Teorema
No se aplica xq tenemos una sola funcion f
-*- 3er Teorema
foldr f e xs = foldl (flip f) e (reverse xs)
foldr g 0 [1,2,3] = 321
foldl (flip g) 0 (reverse [1,2,3]) = 321
Justificacion: ???
-}
[Ej. 10] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
{foldl :: (b -> a -> b) -> b -> [a] -> b
foldl f e [] = e
foldl f e (x:xs) = foldl f (f e x) xs
8
=
=
=
=
foldl f
foldl f
foldl f
foldl f
f (f (f
e [x0, x1, x2]
(f e x0) [x1, x2]
(f (f e x0) x1) [x2]
(f (f (f e x0) x1) x2) []
e x0) x1) x2
-}
foldl’ :: (b -> a -> b) -> b -> [a] -> b
foldl’ f e xs = foldr fun e xs where ?
{foldl’ f e xs = foldr (\a k b -> k (f b a)) id xs e
foldr’ f e xs = foldl (\k a b -> k (f a b)) id xs e
-}
9