Programacao Funcional - Haskell

  • Published on
    01-Jul-2015

  • View
    966

  • Download
    9

Embed Size (px)

Transcript

<p>IntroduoProgramaoumaAbordagemFuncional</p> <p>CredinSilvadeMenezes,MariaCludiaSilvaBoeres, MariaChristinaValleRauber,ThaisHelenaCastro, AlbertoNogueiradeCastroJnior,CludiaGalarda Varassin</p> <p>DepartamentodeInformticaUFES DepartamentodeCinciadaComputaoUFAM 2005</p> <p>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 &gt; ....................................................................................................................... 47 Exerccios ........................................................................................................ 47 6.EXPRESSESLGICASEOTIPOBOOLEAN ....................................... 49 P||Q&amp;&amp;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 </p> <p>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.</p> <p>Algunsexemplosdeusodeumcomputador:</p> <p>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</p> <p>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 objetivo se colocarem maisprximodolinguajardosproblemasdoquedocomputadorem si.Paraqueoprogramaqueescrevemospossaserentendidopelo computador, existem programas especiais que os traduzem (compiladores) ou os que interpretam (interpretadores) para a linguagemdocomputador. Podemosfazerumparalelocomoqueocorrequandoqueremosnos comunicarcomumapessoadelnguaestrangeira.Podemosescrever umacartaemnossalnguaepediraalgumqueatraduzaparaa lngua de nosso destinatrio ou se quisermos conversar pessoalmente,podemosusarumintrprete.</p> <p>1.5.PROPRIEDADESDEUMPROGRAMA Fazemosprogramascomaintenodedotaruma mquina dacapacidade de resolverproblemas.Nestesentido,umprogramaumprodutobemdefinido,que paraserusadoprecisaquesejamgarantidasalgumaspropriedades.Aquifazemos referncias a duas delas: a correo e o desempenho. A correo pode ser entendida como a propriedade que assegura que o programa descreve corretamente o conhecimento que tnhamos inteno de descrever. O</p> <p>6 desempenhotratadapropriedadequeasseguraqueoprogramausardeforma apropriadaotempoeosrecursosdamquinaconsiderada.Cabeaquialertaraos principiantes que a tarefa de garantir que um programa foi desenvolvido corretamente to complexa quanto prpria construo do programa em si. Garantirqueumprogramafuncionacorretamentecondioimprescindvelpara oseuusoe,portantoestaremosdandomaiornfaseaestapropriedade. 1.6.PARADIGMASDELINGUAGENSDEPROGRAMAO Asregrasquepermitemaassociaodesignificadoss"seqnciasdesmbolos" obedecemacertosprincpios.Existemvriasmanifestaesdestesprincpiosea cadaumadelasdenominamosdeparadigma. Um paradigma pode ser entendido informalmente como uma forma especfica dese "pensar"sobre programao.Existemtrsgrandesgruposde paradigmasparaprogramao:oprocedimental,ofuncionaleolgico.Osdois ltimos so freqentemente referidos como sendo subparadigmas de um outro mais geral,oparadigma declarativo.Oparadigmaprocedimentalsubentendea organizaodoconhecimentocomoumaseqnciadetarefasparaumamquina especfica. O paradigma lgico requer o conhecimento de um formalismo matemticodenominadodelgicamatemtica.Oparadigmafuncionalbaseiase no uso dos princpios das funes matemticas. De uma forma geral, os paradigmas declarativos enfatizam o aspecto correo e o procedimental os aspectosdedesempenho.Vejamquefalamosem"enfatizam",oquequerdizer que apresentam facilidades para descrio e verificao da propriedade considerada. Entretanto, em qualquer caso, o programador dever sempre garantirqueosdoisaspectos(correoedesempenho)sejamatendidos. 1.7.PROGRAMAOFUNCIONAL Paraosfinsqueaquinosinteressamnesteprimeiromomento,podemosentender ocomputador,deumaformasimplificada,comoumamquinacapazde: a) avaliarexpressesescritassegundoregrassintticasbemdefinidas,como a das expresses aritmticas que to bem conhecemos (ex. 3 + 5 8) obedecendosemnticadasfunesprimitivasdasquaiseladotada(por exemplo:asfunesaritmticasbsicascomosomar,subtrair,multiplicare dividir); b) aceitar a definio de novas funes e posteriormente considerlas na avaliaodeexpressessubmetidassuaavaliao. Por enquanto, denominaremos o computador de mquina funcional. A seguir apresentamos um exemplo de interao de um usurio com a nossa Mquina Funcional.</p> <p>7usurio: 3+5/2 sistema: 5,5 usurio: fxy=(x+y)/2 sistema: definiodeffoiaceita usurio: (f35)+(f1040) sistema: 29</p> <p>Na primeira interao podemos observar que o usurio descreveu uma expressoaritmticaequeosistemaavalioueinformouoresultado.Nasegunda interaoousuriodescreve,atravsdeumaequao,umanovafuno,queele denominoudefequeosistemaacatouanovadefinio.Naterceirainteraoo usuriosolicitaaavaliaodeumanovaexpressoaritmticausandooconceito recentementedefinidoequeosistemafazaavaliaousandocorretamente o novoconceito. 1.8.EXPRESSESARITMTICAS A nossa mquina funcional hipottica entende a sintaxe das expresses aritmticas,comasquaistodoalunouniversitriojbemfamiliarizadoecapaz deavalilasusandoessasmesmasqueregrasquejconhecemos. SintaxeTodooperadoraritmticopodeserentendido,eaquioser,como uma funo que possui dois parmetros. A notao usual para as operaes aritmtica a infixada, ou seja, smbolo funcional colocado entre os dois operandos.Nadaimpededepensarmosneleescritosnaformaprefixada,quea notao usual para funes com nmero de parmetros diferente de 2. Por exemplo,podemosescrever"+32"paradescreverasomadonmero3como nmero2.Asfunesdefinidaspeloprogramadordevemserescritasdeforma prefixada,comonoexemplodeinteraoacimaapresentado.Combinandoessas duas formas, infixada e prefixada, podemos escrever expresses bastante sofisticadas. Avaliao As expressesaritmticas, como sabemos,so avaliadas de acordocomregrasdeavaliaobemdefinidas,efetuandoasoperaesdeacordo comsuasprioridades.Porexemplo,naexpresso"3+5/2"oprimeirooperadora seravaliadoserodediviso(/)eposteriormenteodeadio.Sedesejarmos mudaressaordem,podemosusarparntesesemqualquerquantidade,desdeque balanceadoseemposiesapropriadas.Porexemplo,naexpresso"(3+...</p>