Kodumaro :: Palíndromo em Standard ML

Publicado em 14 de Setembro, 2018
As sombras da programação.

Estive pensando em uma forma de explicar functor de ML, cheguei ao algoritmo de determinação de palíndromo.

Para programar em Standard ML, eu sugiro MLton para a compilação e Standard ML of New Jersey como console interativo.

É possível fazer um paralelo entre classes da orientação a objetos e functor de ML. O construtor de um functor recebe uma estrutura (structure), que é seu parâmetro, e retorna outra estrutura, que pode ser entendida como sua instância.

Vamos ao palíndromo então.

Assinaturas

O parâmetro de nosso functor é algo reversível, ou seja, que pode ser “dito” de trás pra frente.

No arquivo de assinaturas (palindrome.sig) vamos criar a seguinte assinatura:

signature REVERSIBLE =
sig
  eqtype t
  val reverse : t -> t
end

Isso define uma assinatura REVERSIBLE que referencia um tipo t e contém uma função reverse (para reverter o objeto).

Agora precisamos de uma assinatura para definir a interface da estrutura instanciada a partir do functor. Essa estrutura precisa referenciar o mesmo tipo t de REVERSIBLE e conter uma função para verificar se o objeto reversível é um palíndromo.

Ainda em palindrome.sig:

signature PALINDROME =
sig
  eqtype t
  val check : t -> bool
end

Então check verificará se o objeto do tipo t é um palíndromo, retornando verdadeiro ou falso (bool).

Implementação

No arquivo de implementação (palindrome.sml) vamos começar criando o functor, que recebe um REVERSIBLE e retorna um PALINDROME.

No corpo do functor (pense em classe), o tipo t será definido como o mesmo t do parâmetro, e a função check verificará se o resultado de reverse do objeto é igual a ele próprio:

functor Palindrome (R : REVERSIBLE) : PALINDROME =
struct
  type t = R.t
  fun check pal = (pal = R.reverse pal)
end

Agora vamos definir o que são os tipos reversíveis (Reversible). Vamos lidar com dois: inteiro (Int 0, por exemplo) e string (String "", por exemplo):

datatype Reversible = Int of int
                    | String of string

Finalmente vamos definir a função palindrome, que recebe um reversível, que acabamos de definir acima, e retorna verdadeiro ou falso de acordo se o reversível recebido for ou não um palíndromo.

Para isso instanciaremos duas estruturas de Palindrome: StringPalindrome e IntPalindrome.

local
  structure StringPalindrome = Palindrome (struct
    type t = string
    val reverse = implode o rev o explode
  end)

  structure IntPalindrome = Palindrome (struct
    type t = int

    val reverse =
      let
        fun reverse' (acc:t) 0     : t = acc
          | reverse' (act:t) (n:t) : t =
              reverse' ((acc * 10) + (n mod 10)) (n div 10)
      in
        reverse' 0
      end
  end)

in
  fun palindrome (Int d)    = IntPalindrome.check d
    | palindrome (String s) = StringPalindrome.check s
end

Assim a função palindrome escolherá IntPalindrome.check ou StringPalindrome.check de acordo com o tipo interno do parâmetro.

IntPalidrome.check tem a especialização para inverter inteiros, enquanto StringPalindrome.check para inverter strings.

Experimentando

Vamos testar:

Standard ML of New Jersey v110.78 [built: Thu Jul 23 11:21:58 2015]
- use "palindrome.sig";
[opening palindrome.sig]
signature PALINDROME =
sig
eqtype t
val check : t -> bool
end
signature REVERSIBLE =
sig
eqtype t
val reverse : t -> t
end
val it = () : unit
- use "palindrome.sml";
[opening palindrome.sml]
palindrome.sml:4.24 Warning: calling polyEqual
functor Palindrome(R: sig
eqtype t
val reverse : t -> t
end) :
sig
eqtype t
val check : t -> bool
end
datatype Reversible = Int of int | String of string
val palindrome = fn : Reversible -> bool
val it = () : unit
- palindrome (Int 12);
val it = false : bool
- palindrome (Int 121);
val it = true : bool
- palindrome (String "test");
val it = false : bool
- palindrome (String "rotor");
val it = true : bool

E é isso aí! Espero que tenha ficado claro, quaisquer dúvidas ou se achar que alguma coisa ficou obscura, deixe um comentário.

Conceitual | Funcional | ML