A Linguagem Funcional Haskell

Márcio M. Piffer , Rafael A. Kroth

Ciências da Computação 3ª fase, 2002

Departamento de Informática e Estatística
Universidade Federal de Santa Catarina (UFSC), Brasil, 88040-900
Fone (0XX48)333-9999, Fax (0XX48)333-9999
m_piffer@[Link], coca@[Link]

RESUMO

Este estudo tem como principal objetivo fazer uma breve introdução a linguagem de
programação Haskell, sendo abordado em primeira instância alguns dos princípios básico da
linguagem, ou seja, onde esta foi fundamentada. Programar em uma linguagem funcional significa
basicamente definir funções e utilizar o computador para avaliar expressões. Falando desta maneira
não imaginamos como a mais ascendente das linguagens funcionais do momento o Haskell pode ser
utilizado. Após a leitura deste artigo espera-se que o leitor no mínimo compreenda conceitos
básicos, vantagens, e como a linguagem é utilizada.

Palavras-chave: Haskell, Funcional, Lambda.

ABSTRACT

This study has as main objective to do a brief introduction the programming language
Haskell, being approached in first instance some of the basic of the language beginnings, that is to
say, where this was based. To program in a functional language means basically to define functions
and to use the computer to evaluate expressions. Speaking this way didn't imagine as the more
ascendancy of the functional languages of the moment Haskell can be used. After the reading of this
article it is waited that the reader at least understands basic concepts, advantages, and as the
language it is used.

Key-words: Haskell, Funcional, Lambda.

Introdução foi desenvolvida por um grupo internacional até

março de 1997, e está sendo administrada, ou
Existem diversos paradigmas de aperfeiçoada na universidade de Yale.
programação e diversas linguagens associadas a
estes paradigmas, e este trabalho irá enfatizar o Princípios Básicos
paradigma de programação funcional e a linguagem
a ser abordada será o Haskell. O GHC (Glasgow A linguagem a ser estudada é baseada quase
Haskell Compiler) foi desenvolvido na universidade que totalmente no cálculo lambda ( λ ), sendo assim
de Glasgow na Escócia, ou seja, seu nascimento por fica claro e evidente que aqueles que já possuírem
assim dizer foi dado lá. Sua última versão é a 1.4 e
um conhecimento prévio desta área terão uma maior
facilidade no entendimento do artigo do que aqueles Sessões e Scripts
que são leigos no assunto citado.
Outra questão interessante e que não pode Ao passarmos uma expressão para esta ser
deixar de ser dita é a de que quase todos os avaliada pelo computador o processo de avaliação e
problemas que são implementados em Haskell já evolução é chamado sessão, sendo assim tendo
tiveram uma resolução indutiva construída como prompt o ponto de interrogação (?). Alguns
anteriormente. exemplos de sessão são apresentados abaixo.
Conforme visto em [SCH 92] a indução é
uma ferramenta muito poderosa no Exemplo 1:
desenvolvimento de algoritmos e esta geralmente ? 64 expressão apresentada
traz uma resolução elegante aos problemas 64 valor de retorno apresentado ao usuário
apresentados. A Tese de Church, que não será
abordada aqui, comprova que todo e qualquer Exemplo 2:
problema resolvido imperativamente possui um ? 8*8 expressão apresentada
resolução indutiva, ficando claro então que todos 64 valor de retorno apresentado ao usuário
aqueles que quiserem se aventurar e conhecer o
Haskell mais a fundo deveriam primeiramente Note que nos dois exemplos acima são
possuir um conhecimento prévio destas duas áreas, passados expressões, a primeira já esta em sua
cálculo lambda e indução. forma normal, logo o computador não pode fazer
Tendo consciência também de que esta é mais avaliações, então ele somente retorna o valor a
uma linguagem extremamente tipada, torna-se apresentado, no entanto a segunda expressão poder
sabido que para aqueles que já tiveram algum ser avaliada e evoluída então ele, o computador, faz
contato como linguagens não tipadas como Perl, a avaliação e evolução da expressão, até chegar a
Tcl, ou Scheme, infelizmente terão uma dificuldade uma forma normal e daí então retorna o valor
ainda maior para com o entendimento da encontrado. Concluímos então que uma sessão é
linguagem. iniciada com a passagem de uma expressão para o
Já aqueles que possuem algum tipo de computador e só será terminada quando este
experiência com linguagens tipadas como Java, C, retornar algum valor.
Modula, ou até mesmo ML, irão ter maior O nome Script é dado a área de declaração
facilidade no entendimento quanto ao sistema de de funções e tipos, e alguns exemplos de declaração
tipos da linguagem apresentada neste trabalho. de tipos e funções serão dados logo a seguir, por
Haskell também é conhecido como esta razão não serão dados exemplos por enquanto.
calculadora funcional e a forma de avaliação de
expressões é de extrema importância, pois esta é
que não deixará que certas expressões resultem em Valores e Tipos
não-determinismo. Todas as expressões são
reduzidas tendo como base o cálculo lambda e
Segundo [HUD 97] expressões denotam
maiores aprofundamentos sobre este podem ser
valores e tipos de expressões são apenas termos
encontrados em [THO 87].
sintáticos que denotam tipos de valores ou só tipos.
Toda e qualquer expressão em Haskell é
Todo valor possui um tipo associado, e
avaliada como sendo uma equação matemática, ou
intuitivamente podemos pensar que tipos são
seja, está pode ser construída, avaliada e resolvida
definições de valores.
utilizando-se sempre de leis algébricas.
Valores em Haskell são considerados tipos
Qualquer expressão apresentada ao
primários e podem ser passados para funções como
computador será entendida como sendo um valor,
argumentos, e estes irão retornar como respostas
sendo assim o papel do computador torna-se obter a
colocadas em estruturas de dados.
forma normal ou mais reduzida possível deste valor
Tipos por outro lado não são considerados
e isto é feito através de b - reduções. Deduz-se então
primários e trazem como sentido principal a
que o significado de uma expressão é seu valor e a
descrição de um valor. A associação de um tipo a
tarefa do computador é encontra - lo.
um valor é chamada "typing".
 Usando tipos e valores no exemplo abaixo o símbolo do quantificação universal (∀). Em outras
escrevemos alguns typings. palavras todos os tipos de variáveis estão
5 :: int implicitamente quantificados.
‘a’ :: char Listas são muito utilizados em linguagens
O símbolo "::" deve ser lido como "tem funcionais e são um ótimo veículo para que
tipo". possamos demonstrar os princípios do
Funções em Haskell geralmente são polimorfismo.
definidos por uma série de equações, mas existe um A lista [1, 2, 3 ] é um resumo da lista 1: (2:
tipo especial chamado "type signature declaration", (3: [])), onde [] é lista vazia e : é o operador de
que declara um tipo explicito para a função. infixação, é ele que adiciona o primeiro argumento
Um exemplo segue abaixo. para a frente do segundo e assim por diante, e desta
inc :: int → int "type signature declaration". maneira conseguimos definir um lista.
As "type signature declaration" não são de Ao definirmos uma função que conta o
uso obrigatório, mas regras geralmente são número de elementos de uma lista, notamos as
utilizadas pelo programador para que este saiba que facilidades oferecidas por este sistema de tipos.
tipo possui cada função. Veja o exemplo abaixo:
Quando queremos demonstrar que uma length :: [a] → int
expressão e1 é avaliada ou "reduzida" para uma length [] = 0
outra expressão e2 , nós indicamos desta maneira length (x : xs ) = 1 + length (xs)
que se segue: Se prestarmos atenção a definição é quase
e1 ⇒ e2 que auto - explicativa. Nós podemos ler a função
Por exemplo note que: como sendo "O tamanho da lista vazia é zero, e o
inc (inc 3) ⇒ 5 tamanho da lista cujo primeiro elemento é x e o
restante e da lista é xs é 1 mais o tamanho de xs,
Tipos Polimórficos passado novamente a esta função.
A função length é um exemplo de função
Tipos monomórficos são encontramos com polimórfica e sua "type signature declaration"
muita frequência em diversas linguagens de demonstra isto. Sua grande vantagem vem quando
programação, mas estes restrigem de certa forma a depois de definida esta pode ser aplicada a qualquer
capacidade do programador. tipo de lista e é isto que notamos no exemplo
Haskell também incorpora tipos abaixo, pois são passados para a mesma função
polimórficos - tipos que são universalmente diversos tipos de listas entre elas listas de tipo [Int],
quantificados em algum lugar e referem-se a todos Char], e até mesmo, [[Int]] lista de lista de inteiros.
os outros tipos. length [1, 2, 3] ⇒ 3
Expressões de tipos polimórficos length [‘a’, ‘b’] ⇒ 2
essencialmente descrevem famílias de tipos. Por length [[1], [2], [3], [4]] ⇒ 4
exemplo, (∀ a) [a] é a família de tipos consistindo Com tipos polimórficos, achamos que
de, para todo tipo a, o tipo de listas de a. alguns tipos estão em um senso extremamente mais
Listas de inteiros [1, 2, 3], listas de geral que outros. Por exemplo o tipo [a] é mais geral
caracteres [‘h’, ‘e’, ‘l’ , ‘l’, ‘o’], e até mesmo listas do que o tipo [Char].
de listas de inteiros[[2], [4], [6]]. Todos são O Sistema de tipos Haskell possui duas
membros desta família, ou seja, no momento que importantes propriedades: Primeira, toda expressão
usarmos a variável a está pode ser de qualquer tipo bem tipada é garantida para ter um único tipo
sendo desde que todos sejam do mesmo tipo. principal (explicado abaixo), e a Segunda, é que o
Haskell não irá admitir algo como [‘b’ , 2 ]. Nota-se tipo principal pode ser inferido automaticamente.
então que através da definição de uma função que Uma expressão ou função tipo principal é o
utiliza tipos polimórficos construímos, ou temos a tipo menos geral, que, intuitivamente, "Contém
oportunidade, de construir uma função genérica, todas as instâncias da expressão". Por exemplo, o
onde esta poderá ser utilizada para qualquer família tipo principal da função length é expressado como
de tipos. [a] → a; os tipos [b] → a, a → a , ou até mesmo de
Para fazermos a declaração de um tipo a são muito gerais, considerando que algum tipo
polimórfico não necessitamos explicitar por escrito como [Int] → Int é mais especifico. A existência de
tipos principais únicos é a característica mínima do Pt ‘a’ ‘b’ :: Point Char
sistema de tipos Hindley-Milner, sendo que este Pt True False :: Point Bool
forma a base do sistema de tipos Haskell, ML, Não podemos esquecer de ressaltar que algo
Miranda e a maioria das linguagens funcionais hoje como Pt ‘a’ 1 é sem tipo pois ‘a’ e 1 possuem tipos
conhecidas. diferentes sendo assim o próprio sistema de tipos
Em comparação com linguagens de tipos Haskell durante a compilação irá acusar erro.
monomórficos como C, o leitor irá notar que o É de extrema importância saber distinguir a
polimorfismo desenvolve expressões, e a inferência aplicação entre construtor de dados para construir
diminui a carga de tipos sobre os programadores. um valor e a aplicação de um tipo construtor para
construir um tipo. O primeiro formador acontece em
User-Defined Types tempo de execução e é como nós computamos
coisas em Haskell, já o segundo acontece em tempo
Para definirmos nossos próprios tipos em de compilação e é parte do processo do sistema de
Haskell usa-se a declaração data, ao qual este tipos para assegurar tipos seguros.
trabalho tenta exemplificar de forma a tornar maior Existe também a possibilidade de
a compreensão do leitor. construirmos tipos utilizando o mesmo nome para o
Um importante tipo que já esta predefinido tipo construtor e para o construtor de dados, como
em Haskell, é a definição de tipos boleanos, mas só vemos a seguir.
para exemplificar iremos fazer a sua criação data Point a = Point a a
tomando como se este não existisse: E já que estamos falando do sistema de
data Bool = False | True tipos Haskell não podemos deixar de abranger tipos
O tipo demonstrado acima é Bool e possui sinônimos, sendo que estes são utilizados para
exatamente dois valores: Verdadeiro e Falso. O tipo definir um mesmo tipo com outro nome, mas não
Bool em Haskell possui a denominação de tipo novos tipos. Portanto tipos sinônimos criam um
construtor, e True e False são chamados novo tipo a partir de um antigo só que com outro
construtores de dado, ou só construtores. nome. Para que possamos criar tipos desta maneira
Podemos assim definir diversos tipos. utilizamos a declaração type, como no exemplo
Similarmente podemos definir o tipo Cor: abaixo.
data Cor = Vermelho | Verde | Azul | Violeta type String = [Char]
Mas se pararmos e prestarmos atenção estas type Name = String
duas definições de tipos são limitadas, ou seja, são
tipos enumerados, pois possuem um número finito Funções
de construtores de dado.
Abaixo temos um exemplo com um único Como toda e qualquer linguagem Haskell
construtor de dados. oferece funções pré-definidas, mas seu maior
data Point = Pt a a potencial está destinado ao programador, ou seja, a
Definindo o tipo de dado Point não linguagem oferece muitos recursos a este, quanto a
limitamos o usuário, pois este poderá definir criação de novas funções. Alguns deste recursos já
qualquer tipo de ponto. foram demonstrados no sistema de tipos, agora
Um tipo como Point é freqüentemente iremos abordar a parte funcional da linguagem.
chamado de tuple type, sendo que neste caso este é Não iremos abordar funções oferecidas pela
só um produto cartesiano (neste caso binário) de linguagem, pois nossa intenção não é ensinar a
outros tipos. Tipos multi-construtor, como Bool e programar em Haskell e tão pouco ensinar a utilizar
Cor, são chamados (disjunto) união ou tipos soma, funções pré-definidas ou oferecidas pela linguagem.
em contraste a tipos mono construtor. Geralmente quando definimos uma função
Mais importante, no entanto, é lembrar que em Haskell utilizamos um "type signature" em
Point também é um exemplo de tipo polimórfico: primeiro lugar e na próxima linha iniciamos a
para qualquer tipo t, haverá a definição de pontos declaração da função, como no exemplo que segue:
cartesianos que usam t como o tipo coordenada.
Note que o tipo de binário Pt é a → a → add :: Int → Int → Int -- type signature
Point a, ou seja os tipos abaixo são válidos: add x y = x + y -- Corpo da função
Pt 2.0 3.0 :: Point Float
 Através deste exemplo temos conhecimento Haskore (music)
de como são feitos comentários de linha. Utilizamos CGI programming in Haskell
dois sinais de menos (- -) consecutivos e tudo que Happy (Parser generator)
for escrito após não será reconhecido pelo Derive (Automatic derivation of classes from data
compilador. declarations)
Após este breve comentário continuamos Tk Gofer (the Tk GUI library ported to Gofer, a
falando sobre funções e por intermédio do mesmo language very similar to Haskell).
exemplo, que é chamado de função de curried. Uma
aplicação de add tem a forma add e1 e2, e isso Conclusão
eqüivale a (add e1) e2, desde que a associação da
aplicação da função seja para a esquerda. Em outras Concluímos após um ano de estudo que
palavras, aplicando add a um argumento, isto Haskell além dos inúmeros recursos que traz
produzirá uma nova função ao qual é então aplicado embutido consigo e dos demais que oferece,
o segundo argumento. Isto é consistente com o tipo consegue hoje um crescimento extraordinário no
de add; Int → Int → Int. mundo científico, sendo esta hoje a linguagem
Sendo assim nós podemos redefinir a funcional mais ascendente do momento, apesar de
função inc de um modo diferente da que não ser a mais utilizada ainda.
demonstramos anteriormente, agora podemos Foi descoberto também através deste estudo
utilizar a função add. Esta maneira que que um dos grandes anseios da população da área de
apresentamos agora o é uma aplicação parcial de informática atualmente a portabilidade, é muito bem
uma função curried. proporcionada pela linguagem pois esta trabalha em
Inc = add 1 diversos tipos de arquiteturas e sistemas
Sendo a linguagem Haskell baseada quase operacionais. Interpretadores ou compiladores
que totalmente no Cálculo Lambda, podemos Haskell "rodam" em quase todo hardware ou
definir as mesmas funções de maneira muito mais sistema operacional existente hoje.
reduzida e simplificada, mas não iremos demonstrar Deduz-se também que o estudo de outras
e ou entrar em detalhes pois exigiria, como já áreas, afins é claro, torna-se necessário para uma
falamos antes, um conhecimento prévio do leitor maior compreensão de alguns problemas, e dentre
sobre o cálculo lambda para que este conseguisse estas áreas podemos citar a indução matemática,
entender. sendo que esta é de extrema importância não só para
Podemos acompanhar o comportamento da o aprendizado do Haskell mas em diversas outras
função entendo o próximo exemplo. áreas. Esta afirmação é feita após a descoberta de
Add (add 2 3) 5 ⇒ 10 que existem estruturas na informática que possuem
O exemplo apresentado acima é uma resolução extremamente elegante através da
praticamente auto-explicável, pois ao lermos ele indução, entre eles estão árvores, listas, strings, e o
entendemos que "A função add recebe dois mais clássico deles o das Torres de Hannoi.
argumentos um é uma função e o outro um valor Mais uma dica para quem quiser aprender
sendo que este já se encontra na sua forma normal, esta nova linguagem é utilizar o Hugs um
então basta ser feita a resolução do primeiro interpretador pequeno e de grande portabilidade.
argumento sendo que este dever retornar um valor e Este interpretador é um excelente veículo para
é isto que irá acontecer, sendo assim o próximo aprender se aprender Haskell.
passo é a resolução da expressão". Repare que se o
primeiro argumento retorna-se um caracter ‘a’ por Nota Bibliográfica
exemplo este erro seria encontrado, mas somente
em tempo de execução não de compilação. [HUD 97] HUDAK, Paul e PETERSON, John. A
Gentle Intoduction to Haskell. Los Alamos
Aplicações National Laboratory, 1997.
[SCH 92] SCHINEIDER, Gerardo. Uso de la
Segue ainda uma listagem das áreas onde Inducción para el Diseño de Algoritmos. UTN.,
tem-se sido desenvolvido software utilizando a Facultad Regional Concepión del Uruguay,
linguagem já referida. Argentina. 1992.
Fran (animation)
[THO 87] THOMPSON, Simon. An Introduction
to Type Theory and Constructive Mathematics.
Canterbury, Kent, U.K. 1987.
[Link]