LP 14/09/2011

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

// Falando mais de SML

  fun addp(x,y) = x + y
    int * int -> int

  fun add2 x y  = x + y
    int -> int -> int

// Veja que a primeira função recebe uma tupla, e a segunda recebe apenas um inteiro como parâmetro.
// Mas retorna uma segunda função que recebe um segundo inteiro como parâmetro.

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

  Agora suponha que existe um operador + em cálculo lambida.

  Como escrever a função add?
    (<l>x <l>y x + y)

  Repare que se eu der apenas um parametro eu gero outra função. Se esse parametro for 1 eu gerarei:

    (<l>y 1 + y)

  // Com isso aqui eu entendi muito melhor o que significam as funções de SML, porque de fato elas se parecem muito com as de cálculo lambida.

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

  Agora veja como escrever uma função associando seu nome a uma variável:

  val inc = fn x => x+1

  Porém eu não posso dentro dessa função usar o nome inc novamente, ou seja com esse tipo de declaração não haverá recursividade.

  E portanto o "fun" é uma definição mais poderosa de função.
  // Ou ao menos mais prática né, pois acho q recursão não é pre-requesito para ser turing completo.

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

  Vamos descrever os números em SML da mesma forma que descrevemos para o cálculo lambida e ver o que acontece?

  val UM = fn s => fn z => s z
  val DOIS = fn s => fn z => s ( s z )
  val TRES = fn s => fn z => s ( s ( s z ) )
  e assim por diante.

  Agora criemos uma função que tranforme estes números em números decimais já existentes em SML.

  É facil fazer essa função, já que esses números são o número de vezes que se chama a função parametro,
  então vamos contar esse número de chamadas, usando uma função que retorne +1 para cada chamada dela, ou seja a função de incremento:

  val TRANS = fn s => s inc 0

  E pronto.
    TRANS 2  ->  2 inc 0  ->  (fn s => fn z => s (s z)) inc 0

    ->  (fn z => inc (inc z)) 0   ->   inc (inc 0)   -> inc 1 -> 2 em notação decimal!

    Legal?

  O professor gerou uma função NOT em SML assim como a função que criamos para calc. lambda na ultima aula,
  uma função multiplicação, adição, definiu True e False também da mesma forma, e e criou também um IF.

  Notem bem, sendo-se capaz de somar, realizar desvios, e contabilizar números, temos uma linguagem que é turing completa.

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

CONCEITO:
  Funções de Alta Ordem são funções que recebem outra função como parâmetro ou retornam uma como retorno.

  Uma funçào de ordem 0 não recebe nem retorna nem uma funçào.
  ex:
    fun add (x,y) = x + y

  Uma função que recebe ou retorne uma função é de ordem 1.
  ex:
    fun add2 x y = x + y
    // Só relembrando: Essa função "add2" le x e retorna uma função que então lê y e por fim retorna a soma de x+y.

  Se uma função retorna uma função de ordem 0, sua ordem é 1, se retorna uma função de ordem 1 sua ordem é 2 e assim por diante.

  Estas são então as funções de alta ordem.

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

  Seja agora a função map: Ela recebe uma função e uma lista, e aplica a função a cada posição da lista, ou seja:

    fun map f l = f hd l map tl l

  Ex de uso:

    A função ord que recebe um caractere como parametro retorna o seu número em asc.

    fun asc str = map ord explode(str)

    assim é retornada uma lista contendo os números asc da string recebida como parametro.

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

    Outra função foldr:  (fold right)

      fun foldr func s nil = s
      fun foldr func s l   = foldr func (func s hd l) (tl l)
        ('a  * 'b -> 'b ) -> 'b -> 'a list  -> 'b

    Essa função aplica func sobre os elementos da lista 2 a 2.
    Ou seja, o parâmetro s deve ser originalmente chamado com um valor neutro em relação à função.
    Assim o que a foldr faz é aplicar s = (func s hd l) recursivamente até que l seja nula.

    Existe o fold right e o fold left, foldr e foldl respectivamente.
      foldr: (a4(a3(a2(a1))))
      foldl: ((((a1)a2)a3)a4)

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

Nota solta:
  Existe um operador que seja associativo mas não comutativo?
  Sim a concatenaçào
  E um que seja o contrário? isso pode cair na prova, existe sim mas ele nào disse qual.
// Bem eu não consegui pensar em nada, espero que o professor num invente de cobrar isso em prova =/.

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

  fun filter _ nil = nil
    | filter f (h::t) = if f h then h :: filter f t else filter f t

  // leq é lesser or equal
  fun leq a b = a <= b

  // grt é maior que.
  fun grt a b = a >  b

  fun qsort nil = nil
    | qsort (h::t) = qsort (filter (leq h) t) @ [h] @ qsort (filter (grt h) t)

// Bem e é essa aula =]
// Acho que esse quick sort nao funciona e esqueci de anotar a correçào que faria ela funcionar.
// Bem eu q num vou corrigir isso xP