Programacao Funcional - Haskell

Embed Size (px)

Text of Programacao Funcional - Haskell

IntroduoProgramaoumaAbordagemFuncional

CredinSilvadeMenezes,MariaCludiaSilvaBoeres, MariaChristinaValleRauber,ThaisHelenaCastro, AlbertoNogueiradeCastroJnior,CludiaGalarda Varassin

DepartamentodeInformticaUFES DepartamentodeCinciadaComputaoUFAM 2005

2 1.CONCEITOSBSICOS ................................................................................ 5 1.1Introduo .................................................................................................... 5 2.ALinguagemdeProgramaoHaskelleoambienteHUGS ..................... 14 3.AArtedeResolverProblemas .................................................................... 23 3.4.Umpequenoexemplo: ......................................................................... 25 4.ABSTRAO,GENERALIZAO,INSTANCIAOEMODULARIZAO ................................................................................................................................. 30 5.TiposdeDadosNumricos ......................................................................... 38 Descrio ............................................................................................ 40 Programerror:dividebyzero ........................................................... 41 > ....................................................................................................................... 47 Exerccios ........................................................................................................ 47 6.EXPRESSESLGICASEOTIPOBOOLEAN ....................................... 49 P||Q&&R ..................................................................................... 57 7.DefiniesCondicionais .............................................................................. 59 8.OTESTEDEPROGRAMAS ...................................................................... 67 9.RESOLVENDOPROBLEMASOSMOVIMENTOSDOCAVALO ........... 74 10.TUPLAS ..................................................................................................... 84 11.VALIDAODEDADOS .......................................................................... 89 1.Expliqueporquenoexisteovalorkqueapieadefiniodafunofx; 94 2.Jpojpoj .......................................................................................................... 94 3.Pojpoj ............................................................................................................ 94 4.Pojpoij ........................................................................................................... 94 12.LISTAS ...................................................................................................... 95 Exerccios: .................................................................................................... 110 Kjoj ................................................................................................................. 110 Ionopi ............................................................................................................. 110 Oijoip ............................................................................................................. 110 Joij ................................................................................................................. 110 Oioi ................................................................................................................ 110 Iojo ................................................................................................................. 110 13.ResolvendoProblemascomListas ......................................................... 111 14.ParadigmaAplicativo ............................................................................... 115 15.ProcessamentodeCadeiasdeCaracteresprimeirospassos ............. 126 Exerccios ...................................................................................................... 134 Kjbkj ............................................................................................................... 134 Kjn ................................................................................................................. 134 Ono ................................................................................................................ 134 Onoi ............................................................................................................... 134 16.OPARADIGMARECURSIVO ................................................................ 135 19.APLICAES ......................................................................................... 177 20.ENTRADAESAIDADEDADOS ............................................................ 196 20.1Introduo: ....................................................................................... 196

3 1.CONCEITOSBSICOS 1.1INTRODUO Nestecursooleitorestarseenvolvendocomaaprendizagemdeconceitose mtodosbsicosparaaconstruodeprogramasdecomputador.Aabordagem que daremos est voltada para o envolvimento do aprendizcoma soluo de problemas ao invs da atitude passiva de ver o que os outros fizeram. Uma questocentralquepermeiaocursoadequeconstruirprogramasumatarefa deengenharia,eque,portantoproduzirartefatoscomosquaisoserhumano terdeconviver.Artefatosestesquedevemsatisfazerrequisitosdequalidadee serem,portanto,passveisdeconstatao. Optamos desenvolver o curso orientado descrio de funes, um formalismo bastante conhecido por todos os que chegam a este curso. Esperamos,comisso,atenuaralgumasdificuldadestpicasdoensinointrodutrio deprogramao.Nasseesseguintesapresentamosalgunsconceitosbsicos que nos parecem importantes ter em mente antes de iniciarmos um curso de programao. 1.2.COMPUTADORES Denominamosdecomputadorumamquinadeprocessardados,numricosou simblicos, que funciona atravs da execuo de programas. Ao contrrio das inmeras mquinas que conhecemos, tais como: mquina de lavar roupa, liquidificador, enceradeira, aspirador de p, e tantas outras, que realizam uma nicafuno,ocomputadorumamquinamultiuso.Podemosuslocomouma mquinadeescreversofisticada,comoumamquinadefax,comoumaprancheta de desenho sofisticada, como um fichrio eletrnico, como uma planilha de clculos e de tantas outras formas. exatamente como o nosso conhecido videogame:paramudardejogobastatrocarocartucho.Novideogame,cadanovo jogodeterminadoporumnovoprograma. Emlinhasgeraispodemosentenderumcomputadorcomoumamquina capazde: a) b) interpretardadosquelhesofornecidos,produzindoresultados emformadenovosdadosoucomportamentos,usandoparaisso conceitosquelheforamantecipadamenteinformadose, aceitar a descrio de novos conceitos e considerlos na interpretaodenovassituaes.

Algunsexemplosdeusodeumcomputador:

4 Ex1:Descreverparaumamquinaarelaomtricaqueexisteentreos lados de um tringulo retngulo. De posse desse conhecimento, a mquina poderia,porexemplo,determinarovalordeumdosladosquandoconhecidoo valordosoutrosdois. Ex2:Informaraumamquinaasregrasdeconjugaodeverbos.Comeste conhecimentoamquinapodedeterminaraformacorretaparaumdeterminado tempoepessoadeumverboespecfico. Ex3:Traduodetextos; Ex 4: Classificao de textos quanto sua natureza: romance, poesia, documentrio,entrevista,artigocientfico; Ex 5: Manipulao de expresses algbricas, resoluo de integral indefinida,etc; Ex 6: Programao automtica: dada uma certa especificao, gerar um programaeficiente; Ex7:MonitoramentodepacientesemumCentrodeTratamentoIntensivo; Ex8:Identificaodetumoresnocrebroapartirdacomparaodeimagens compadresconhecidosdeanormalidade; Ex9:Roteamentointeligentedemensagens. 1.3.PROGRAMAO tarefa de identificar o conhecimento necessrio para a descrio de um conceito,organizloecodificlodemodoaserentendidopelamquinadamoso nome de programao de computadores. Ao conhecimento codificado, produto finaldatarefadeprogramaodseonomedeprograma. Aprogramaodecomputadoresumaatividadequecompreendevrias outras atividades, tais como: entendimento do problema a ser resolvido, planejamentodeumasoluo,formalizaodasoluousandoumalinguagemde programao, verificao da conformidade da soluo obtida com o problema proposto. 1.4.LINGUAGEMDEPROGRAMAO A descrio de conhecimento para um agente racional qualquer (seja uma mquinaouumhumano)subentendeaexistnciadepadressegundoosquaiso agente possa interpretar o conhecimento informado. A esses padres, quando

5 rigorosamente elaborados, damos o nome de formalismo. Um formalismo compostodedoisaspectos:asintaxeeasemntica.Asintaxepermiteaoagente reconhecer quando uma "seqncia de smbolos" que lhe fornecida est de acordocomasregrasdeescritae,portantorepresentaumprograma.Asemntica permite que o agente atribua um significado ao conhecimento descrito pela "seqncia de smbolos".Por exemplo, quando um agente humano (com determinadograudeescolaridade)encontraaseguinteseqnciadesmbolos{3, 4}U{5,9,15},eleporcertoreconhecercomoumaexpressoalgbricaescrita corretamentee,selembrardosfundamentosdateoriadosconjuntos,associar estacadeiacomoadescriodeumconjuntocompostopelauniodoselementos dedoisconjuntosmenores. Eis aqui algumas observaes importantes sobre a necessidade de linguagensdeprogramao: Ainda no possvel usar linguagem natural para ensinar o computadorarealizarumadeterminadatarefa.Alinguagemnatural, tosimplesparaoshumanos,possuiambigidadeseredundncias que a inviabilizam como veculo de comunicao com os computadores. A linguagem nativa doscomputadores muito difcil de ser usada, pois requer do programador a preocupao com muitos detalhes especficosdamquina,tirandopoisatenodoproblema. Parafacilitaratarefadeprogramaoforaminventadasaslinguagens de programao. Estas linguagens tm por obje