--Segunda Prova de LP2 - 1/2000 - 26/05/2000
--===========================================

{-
1) Prove a seguinte propriedade:
   b) (2.0) filter c (filter c xs) = filter c xs

2) (3.0) Em uma aplicacao que envolve controle de distancias, eŽ possivel
   que os dados sejam representados utilizando o sistema metrico (Km)
   ou o sistema americano (Milhas). Dadas as tres representacoes 
   em Haskell propostas abaixo, discuta suas diferencas,
   vantagens e desvantagens de cada uma delas.
   opcao A) type Km = Float
            type Milha = Float
   opcao B) data Km = Km Float
            data Milha = Milha Float
   opcao C) data Distancia = Km Float
                           | Milha Float
-}
data Distancia = Km Float | Milha Float
		deriving (Eq, Ord)
{-
3) (2.0) assumindo o uso da opcao C acima, e o fato de que uma Milha e' 
   igual a 1.609 Km, mostre como podemos implementar adequadamente
   instancias da classe Eq e da Classe Ord (e' suficiente definir apenas
   as funcoes (==) e (<=) dessas classes).
-}
{-
instance Eq Distancia Km Float where
Km f1 == Km f2 = f1 == f2

instance Eq Distancia Milha Float where
Milha f1 == Milha f2 = f1 == f2
  -}
   
{- Dado que o tipo Tree t pode implementar uma 'arvore de
   busca (com informacoes apenas nos nos)  
   defina uma funcao que permita a insercao de um novo 
   elemento em uma arvore de busca, mantendo suas propriedades de ordenacao
   (i.e. os dados armazenados na sub-arvore da esquerda sao 
   sempre menores ou iguais ao dado no proprio no', 
   e os da sub-arvore da direita sao sempre maiores ou iguais ao
   dado do proprio noŽ).
-}
data Tree t = Empty | Node t (Tree t) (Tree t)
		deriving (Show, Eq)
   
insTree :: Ord t => t -> Tree t -> Tree t
insTree t Empty = Node t (Empty) (Empty)
insTree t (Node a x y)  | t <=  a = Node a (insTree t x) y
			| otherwise = Node a x (insTree t y)
{-   (2.0) insTree :: Ord t => t -> Tree t -> Tree t

   Faca uma funcao que verifique se uma arvore qualquer e' uma 'arvore de
   busca (i.e. verifique a propriedade descrita acima).

   (2.0) isOrdered :: Ord t => Tree t -> Bool

-}

isOrdered :: Ord t => Tree t -> Bool
isOrdered Empty = True
isOrdered (Node a Empty (Node y d e)) = (a<y) && (isOrdered (Node y d e))
isOrdered (Node a (Node x b c) Empty) = (a>=x) && (isOrdered (Node x b c))
isOrdered (Node a Empty Empty) = True
isOrdered (Node a (Node x b c) (Node y d e)) = (a>=x) && (a<y) && (isOrdered (Node x b c)) && (isOrdered (Node y d e))