LP 21/09/2011

   # # # # # # # # # # # # # #
  # Linguagens de Programação #
  # Prof. Fernando Pereira    #
  # notasdogarcia.blog.com    #
   # # # # # # # # # # # # # #

		// A aula de hoje vai falar sobre tipos de dados

Declarando um tipo boolean:

datatype bool = true | false;

// Parece que true e false são palavras reservadas, mas bool não é e precisa ser definida.

Outro exemplo:

datatype day = dom | seg | ter | qua | qui | sex | sab;

Estes tipos são chamados de tipos algebricos dentro de linguagens funcionais e mais especificamente dentro do SML chamamos de uniões disjuntas rotuladas.

Porque disjuntas? porque cada membro dessa união é um conjunto sem intercessões com nenhum outro conjunto da mesma enumeração.
// ou seja eu não posso fazer nenhuma operação do tipo dom < seg, pois isso não faz sentido a principio já que as uniões nenhuma relação entre sí.

 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Ex interessante:
  Como poderiamos fazer para expressar +infinito e -infinito em SML?,
  já que apesar de termos o tipo inteiro, quando ocorre um overflow seu valor fica apenas confuso e chamar isso de +infinito ou -infinito seria uma solução prática.

  datatype exint = MinusInf | PlusInf | Value of int

Value no caso é tranformado num "construtor de dados", que recebe um inteiro e retorna um tipo exint
exint é um construtor de tipo.

CONCEITO:
  Construtor de Dados é diferente de construtor de tipos, mas também funciona de forma semelhante a uma função.
  Um Construtor de Dados é definido na declaração de um rotulo de um datatype e utiliza-se a palavra reservada "of" para associa-lo a um tipo.
  Assim ele recebe um tipo como parâmetro (como no exemplo acima) e retorna um datatype, no caso o exint.

  Assim se eu escrevo Value 10 em uma função eu estou na verdade me referindo ao tipo exint no conjunto de Values referente especificamente ao valor 10.

 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

  Como fazer uma função para calcular o quadrado de um inteiro retornando um exint e lidando com overflows?

// No caso vamos considerar que o parâmetro é um exint ao inves de um inteiro, para simplificar.

fun square PlusInf = PlusInf
  | square MinusInf = PlusInf
  | square (Value x) = Value (x*x)
    handle Overflow => PlusInf;
  // Parece que handle é o pegador de excessões do SML.

  Então repare que o rotulo Value, se parece muito com uma função, então qual a diferença??
  A diferença é que eu posso usar um rotulo para casamento de padrão, mas não posso usar uma função para isso.
  Voces viram como eu usei (Value x) para que x denotasse o inteiro contido no exint de parâmetro?
  Interessante não?

 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

  O casamento de padrão é um açucar sintatico sobre a ferramenta case veja:

  val s = case x of
          PlusInf => "inf"
          MinusInf => "-inf"
          value y => Int.toString y;

// então note que o case realiza exatamente o mesmo processo que um casamento de padrão.
// Porém pode ser usado em uma variável como no exemplo acima.
// A variável s conterá portanto uma string denotando o valor da variável x.

 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

  datatype 'a opt = NONE | SOME of 'a

  Pode-se usar isso por exemplo para gerar a função:

fun optdiv a 0 = NONE
  | optdiv a b = SOME(a div b)

  Assim posso retornar um sinal de "erro" ou de "invalidez" quando a divisão não puder ser realizada.
  sinal esse que no caso eu chamo de NONE.

 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

  datatype 'b bunch = One of 'x | Group of 'x list

  Que pode representar conjuntos unitários ou não de forma diferenciada.

 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

  Como criar uma função para descobrir o tamanho da um tipo bunch?

  fun size (One _) = 1
    | size (Group l) = lenght l

// Pense em lenght como uma função para descobrir o comprimento de uma lista.

  Ou seja em SML fica fácil trabalhar com estruturas de dados mais complexas, pois sempre consigo desconstrui-las
  em padrões mais simples e trabalhar apenas sobre eles usando o casamento de padrão.

 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

  Observem uma notação importante, que pode causar erro se voce não entender bem:

  datatype 'int opt = NONE | SOME of 'int

  Funciona bem

  mas:

  datatype int opt = NONE | SOME of 'int

  Da erro, pois um tipo deve sempre ter uma apostofre antes.

  // Repare que eu redefini o valor de opt que agora só aceita inteiros.

 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

  Vamos definir uma lista?

    datatype intlist = IntNill | IntCons of int * intlist (recursivamente)

  Legal né? e meio confuso.

 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

  Mas essa lista só aceita inteiros vamos fazer uma que aceita qualquer tipo:

    datatype 'a mylist = NIL | CONS of 'a * 'a intlist (recursivamente)

//  o professor fez infixr 5 CONS, e de algum modo cons ganhou os mesmos poderes que os "::" porem funcionando sobre "mylist"
//  o professor escreveu algo antes, que não entendi.
//  Bem pensando a respeito do :: parece então que ele é também um construtor de dados que recebe um 'a e um 'a list assim como o CONS,
//  faz sentido haver um modo de fazer o cons se comportar da forma que o :: faz já que são totalmente analogos.

 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

  Como se faz uma arvore?

  datatype 'a tree = Empty | Node of 'a tree * 'a * 'a tree

  Mole não?

 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

  Agora o professor quer tranformar uma lista em uma arvore binaria balanceada veja:
// não faço idéia da utilidade dessa função xP

  fun toTree nil = Empty
    | toTree (h::t) =
      let
        fun halve nil = (nil, nil)
          | halve [e] = ([e], nil)
          | halve (a::b::t) =
          let
            (x,y) = halve t
          in
            (a::x, b::y)
          end

      val (x,y) = halve t

      in
        Node(toTree x, h, toTree y)
      end

 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

// bem a aula acabou, o professor escreveu mais algumas coisas, mas não cheguei a copiar tudo não. =/