Nome TextoResumo
1 ALLEF KRISTIAN TAVARES ROCHA # Resumo semana 3 ## QuickCheck Utilizada para teste de código - Define-se uma invariante - É gerado automatica e aleatoriamente casos teste Exemplo: import Test.QuickCheck par x = x ``mod` 2 == 0 propAlternancia n = par n /= par (n+1) quickCheck propAlternancia propSeImparNaoPar n = par n ==> not (impar n) -- (==>) implicação quickCheck propSeImparNaoPar ## Funções como tipos Podemos pensar em funções como tipos de dados. Exemplo: soma :: Int -> (Int -> Int) soma x y = x + y soma3 :: Int -> Int soma3 = soma 3 -- > 3 + y soma3 2 -- > 5 Nesse exemplo ocorreu uma *aplicação parcial*. Isso pode ocorrer em qualquer função com mais de um argumento ## Funções de alta ordem - recebem uma ou mais funções como argumento, ou - devolem uma função map :: (a->b) -> [a] -> [b] map f xs -- f é aplicado a todos os elementos de xs, gerando uma nova lista do tipo b de mesmo tamamnho. filter :: (a -> Bool) -> [a] -> [a] filter p xs -- devole uma lista contendo cada x de xs, tal que p(x) é Verdadeiro all/any :: (a -> Bool) -> [a] -> Bool -- verifica se todos/algum elemento atende ao predicado takeWhile/dropWhile :: (a -> Bool) -> [a] -> [a] -- retorna os primeiros/ultimos elementos que atendem ao predicado ($) :: (a->b) -> a -> b f $ x = f x -- precedência ## Folding foldr :: (a -> b -> b) -> b -> [a] -> b foldr f v xs -- f recebe um elemento de xs e o acumulador v O foldr busca reduzir a lista, iterando por cada elemento x aplicando f, com o objetivo de gerar um unico valor de qualquer tipo. foldl :: (a -> b -> a) -> a -> [b] -> a foldl f v xs -- f recebe o acumulador v e um elemento de xs É a versão caudal do foldr ## Composição de funções f o g (matemática) = f . g (Haskell)
3 ANDRE BELTRAME KRUSS
4 ANDRE RICCA YOSHIDA Teste de propriedade do algoritmo: - Podemos provar a funcionalidade correta do algoritmo usando indução, o Haskell permite provar matematicamente a funcionalidade correta. - Outra maneira de provar a funcionalidade é realizar testes sobre as funções, apresentando dados "hardcoded" de entrada e saída esperados. - Uma maneira mais avançada de se implementar testes é utilizando o QuickCheck. - O QuickCheck, ao encontrar um erro, ele retorna a instância mais simples que deu errado. - Podemos também editar o "break" do QuickCheck, para podermos ignorar casos especificos. - tack new quickcheck simple - Comando para criar um arquivo novo de teste. - Podemos testar as propriedades da funções, tamanho de uma lista, etc... Funções de alta ordem: - Recebem uma ou mais funções como argumento. - Devolvem uma função. - Haskell, de maneira nativa possui diversas funções de alta ordem que auxiliam na construção do código, por exemplo: - Map, é uma função que recebe uma lista, executa uma função e retorna outra lista. - Filter, função que recebe uma lista, aplica um predicado e retorna outra lista.
5 ANDRESSA TEIXEIRA MENEZES
2 ANDRÉ ANDERSON DE JESUS OLIVEIRA
6 ANGELO MAEDA ROJAS QuickCheck O QuickCheck é uma ferramenta que avalia se uma função está correta para uma propriedade, que é definida pelo programador. Essa avaliação é realizada através de diversas entradas. Exemplo Existe uma função de ordenação, quicksort, com a seguinte assinatura: qsort :: Ord a => [a] -> [a]. Queremos testar a propriedade para verificar se a lista de entrada e a lista de saída são do mesmo tamanho. Para isso inicialmente importamos o quickCheck e criamos a função que testa a propriedade. Import Test.QuickCheck qsort :: Ord a => [a] -> [a] qsort [] = [] qsort (x:xs) = … prop_length :: Ord a => [a] -> Bool prop_length xs = length (qsort xs) == length xs Utilizando o stack GHCI Podemos digitar “quickCheck prop_length” e verificar se essa propriedade é válida. Funções de alta ordem Funções de alta ordem são funções que recebem uma ou mais funções ou que devolvem uma função. Map map :: (a -> b) -> [a] -> [b] map f xs = [f x | x <- xs] Recebe como argumento uma função f e uma lista e devolve uma lista. Existem muitas funções que utilizam recursão que se assemelham muito com a função sum, descrita abaixo sum :: Integral a => [a] -> a sum [] = 0 sum (x:xs) = x + sum xs Por conta disso existem duas funções que se equivalem a funções com essa cara. O foldr e o foldl. foldr :: (a -> b -> b) -> b -> [a] -> b foldr f v [] = v foldr f v (x:xs) = f x (foldr f v xs) foldl :: (a -> b -> a) -> a -> [b] -> a foldl f v [] = v foldl f v (x:xs) = foldl f (f v x) xs
7 ANTONIO DUARTE CANTANHEDE NETO Quickcheck é uma bilbioteca de testes baseada em testes de invariantes (os quais corretude capturam a corretude do algoritmo), complementar a testes unitários. Funções de alta ordem são funções que admitem outras funções como entradas ou devolvem outras funções. No Haskell, funções de alta ordem podem ser pensadas como tipos de dados, os quais podem servir como argumentos de entrada de outras funções ou como saída destas. Funções de alta ordem permitem realizar tarefas que seriam muito dificilmente executadas caso funções de alta ordem não existissem. As duas funções de alta ordem mais icônicas em Haskell são: Map – aplica uma mesma função a todas as entradas de uma lista; ex.: map (+3) [1, 5, 7, 9] retorna [4, 8, 10, 12] Filter – “filtra” de uma lista A uma outra lista B que contém apenas os elementos de A que respeitem uma certa condição. ex.: filter (<3) [1, 2, 5, 8, -1, 0] retorna [1, 2, -1, 0] Outras funções de alta ordem importantes: any – recebe um predicado p e uma lista; retorna True se existe algum elemento da lista para o qual o predicado p é verdadeiro; retorna False do contrário; takeWhile - recebe um predicado f e uma lista A; retira os elementos da lista A e colocando na lista B até quando encontra o primeiro elemento de A para o qual o predicado f não vale; retorna B; dropWhile - análogo a takeWhile, mas com a lógica da função “drop”. Folding: técnica que permite aplicar, sequencialmente, uma função f a cada elemento da lista e a um resultado parcial, o qual é obtido de forma incremental. foldr: começa a partir do fim da lista; foldl: começa a partir do início da lista Composição de funções em Haskell: utiliza-se o operador ‘.’ (ponto).
10 BRUNA ISHIDA Há a possibilidade de testar o código feito em Haskell, um bom exemplo de ferramenta é o QuickCheck. Com ele, pode-se definir uma invariante do algoritmo e o mesmo testa o código com valores aleatórios, gerando casos progressivos para os testes. Uma vez encontrado um erro, o mesmo notifica na mesma hora, parando o teste. No Haskell há a possibilidade de enviar funções como argumentos, assim, é possível chamar uma função dentro de outra. Esse tipo de ação leva o nome de "função de alta ordem". Ou seja, funções que recebem uma ou mais funções para serem utilizadas no desenvolvimento da questão ou que retornam funções. Existem diversas possibilidades, alguns exemplos mais utilizados são: map, filter e o pipe. O folding tem como objetivo generalizar o caso de recursão dentro de uma lista de valores. Existe uma diferença entre os comandos de folding (foldr e foldl). Normalmente utiliza-se do foldr quando a lista de dados enviados é infinita, ou o operador utilizado pode acarretar num curto circuito. Enquanto que o foldl é utilizado no caso antagônico (lista finita e não acarreta num curto circuito). Além de que o foldl auxilia a na utilização de listas reversas.
11 BRUNA MIRELLI XAVIER GONCALVES 5.1 Quickcheck: testes baseados em propriedades Trata-se de uma ferramenta de teste do código, por exemplo, para funções, para que se possa determinar se apesar da sua compilação correta, funciona como desejado. E ajuda a verificar também, se o seu comportamento está controlado quando há o uso de valores limites ou não convencionais. Complementa os testes de unidade. Funciona com a definição de uma invariante do algoritmo e com a geração automática e aleatória de casos de teste. Podemos verificar se uma lista de saída está ordenada, se o seu tamanho é igual a de entrada e se contém os mesmos elementos da lista de entrada. A ferramenta é utilizada por meio da edição do arquivo .cabal do projeto com "build-depends: base >= 4.7 && <5, QuickCheck", com o import da biblioteca e o comando stack ghci no terminal. 6.1 - Programação Funcional em Haskell: Funções de Alta Ordem ->Mapeamento de funções, Filtragem e Folding. Função como tipo de dado: pode servir como argumento ou retorno de outra função. Mapping: Função que recebe outra função e uma lista, e realiza sua aplicação. Funciona para listas de qualquer tipo, com quaisquer funções, e pode ser usada em listas de listas, ou seja, é aplicável sobre ela mesma de forma recursiva. Filter: Função de alta ordem que realiza filtragem de elementos de uma lista e retorna a lista modificada. Operador Pipe ($): Ajuda na organização do código. Permite a retirada de parênteses pois gera um padrão de precedência. Folding: Foldr e Foldl generalizam de forma recursiva funções que possuem um padrão simples, realizando as chamadas a partir da cabeça da lista ou de modo caudal respectivamente. Composição de Funções: uso do operador (.) para manter a composição matemática típica associativa e facilitar a escrita.
12 BRUNO STORER FRANCO MARTINS Nessa semana aprendemos sobre o quickCheck que se trata de uma ferramenta para teste de códigos. Com o quickCheck é possivel se estabelecer propriedades que averiguam o correto funcionamento do algoritmo e, em seguida, o quickCheck gera uma sequência de testes aleatórios que colocam em cheque se o código programado obedece as propriedades definidas. Funções podem ser consideradas tipos de dados em haskell. Veja que ela é uma função que recebe um inteiro e retorna uma função que recebe um inteiro e retorna um inteiro. Além disso, funções podem ser passadas como argumentos em outras funções. Funções que possuem esse tipo de aplicação são chamadas de função de alta ordem. Aprendemos na aula sobre aplicações parciais, também. Exemplo: triplica = (*3) Dado um argumento y a função retorna y*3 . Funções de alta ordem podem ser usadas para gerarem uma lista, é conhecido essa tática como função map, em que se passa uma função como argumento q será aplicada a cada posição de uma lista: map :: (a -> b) -> [a] -> [b] map f xs = [f x | x <- xs] Da mesma forma uma função pode ser passada de parâmetro pra ser usada no filtro de uma lista. As funções de alta ordem representadas até o momento podem ser generalizadas por uma função chamada foldr: foldr :: (a -> b -> b) -> b -> [a] -> b foldr f v [] = v foldr f v (x:xs) = f x (foldr f v xs) Onde f é uma função que queremos aplicar na lista, v é o valor padrão de retorno para listas vazias e (x:xs) será nossa lista (head e tail no caso). Por exemplo, se queremos a funcionalidade de somar uma lista fazemos : foldr (+) 0 [1..10] Também existe o foldl que inverte x e (foldr f v xs) em sua aplicação.
13 CAIO ARGENTINO DE OLIVEIRA - QuickCheck - framework para realizar testes unitários em Haskell - certas propriedades esperadas do algoritmo implementado são declaradas e o algoritmo é testado a partir de diversas entradas e saídas afim de se verificar se as propriedades são respeitadas pela implementacão do algoritmo codificada. - função de propriedade: válida se determinada propriedade do algoritmo é respeitada - ex: prop_idempotencia :: Ord a => [a] -> Bool prop_idempotencia xs = qsort (qsort xs) == qsort xs - casos de teste: válida se determinada propriedade é respeitada para uma determinada saída - ex: > quickCheck prop_idempotencia +++ OK, passed 100 tests. > quickCheck prop_length *** Failed! Falsifiable (after 4 tests): [(),()] - Funções de Alta Ordem - em Haskell, funções são consideradas um tipo de dado, e consequentemente podem ser passadas como argumento para outras funções ou serem o valor de retorno de uma função - funções que recebem como argumento outras funções ou que retornam uma função ao serem aplicadas, são ditas funções de alta ordem - em Haskell, caso o argumento de uma função apareça apenas no final de sua definição, ele pode ser omitido como argumento - ex: duplica x = (*2) x duplica = (*2) - algumas funções de alta ordem em Haskell são: - map: recebe uma função e uma lista e retorna uma lista mapeada da lista de entrada usando a função - filter: filtra uma lista a partir de uma função que retorna um booleano - all: retorna se todos os elementos de uma lista resultarem em True a partir da aplicação da função recebida - any: retorna se algum elemento de uma lista resultar em True a partir da aplicação da função recebida - takeWhile: retorna todos os elementos até o elemento que retornar False para função recebida aplicada sobre ele - dropWHile: retorna todos os elementos a partir do elemento que retornar True para função recebida aplicada sobre ele - foldr: recebe uma função, um valor inicial e uma lista, um valor que representa a aplicação dessa funcao a partir do final da lista usando inicialmente o valor inicial recebido - foldl: similar a foldr, porém percorre a lista na ordem oposta a foldr - Composição de funções - é possível compor funções em Haskell utilizando o operador . - fn x = max (min 50 x) => fn = max . min 50 - lê-se: max após min de 50 e x
14 CAIO CESAR RAMALHO FOLLADOR
9 CAIO HENRIQUE DOS SANTOS RIBEIRO
15 DANIEL ESPINDOLA DA SILVA QuickCheck: É uma biblioteca de teste de código que te permite utilizar propriedades definidas da sua função para testar se ela está tendo o resultado esperado, esse processo é feito utilizando funções de alta ordem. Além disso, ela te permite gerar dados de teste aleatórios automaticamente, permitindo testes mais amplos e mais rápidos do que inserir manualmente. Nos testes automáticos também é possível definir propriedades para que o teste em questão apenas seja executado em entradas que façam sentido com o algoritmo. Aplicação Parcial: Quando temos uma função que recebe N parâmetros e passamos menos que N parâmetros ao chama-la, o retorno da função será outra função que receberá a quantidade de parâmetros que ficou faltando. Esse é um exemplo de função de alta ordem. Funções de Alta Ordem: São funções que recebem funções como parâmetro e/ou retornam funções como resultado. Entre as mais famosas presente em diversas linguagens inclusive não funcionais estão: Map: Recebe uma função e uma lista e retorna a lista resultante da aplicação da função para todos os elementos da lista. Filter: Recebe uma função com retorno booleano e aplica essa função para eliminar da lista original todos os elementos que retornem Falso na aplicação da função. Foldr: Recebe uma função que tenha dois argumentos e um valor final e aplica essa função entre numa lista pegando sempre 2 elementos e ‘acumulando’ o resultado de modo que no final sobre apenas um tipo da lista.
17 DIEGO SOUSA SANTOS Parte 5: Apresentação e estudo da biblioteca quick check, utilizada para realização de testes automatizados das soluções em Haskell. Aspectos importantes: -É uma biblioteca externa, deve ser incorporada ao projeto. -A biblioteca tem funções para gerar valores / parâmetros aleatórios para realizar testes das nossas funcionalidades. -Podemos testar diversas propriedades das funções e de seus resultados através do quick check -Utilização no terminal: "quickCheck nomeFuncaoDeTeste" -A quantidade default de testes bem sucedidos é 100, porém isso pode ser alterado. Parte 6: Definição e aplicação de funções de alta ordem e de composição de funções Funções de alta ordem: -São funções que ou recebem outras funções como parâmetro e/ou retornam funções como resultado do processamento. -São úteis quando precisamos criar funções que dependem de funções externas. Exemplos: map, filter, foldr, foldl, etc.. Composição de funções: -Para compor funções podemos utilizar os operadores (.) ou ($) --Exemplo sem operador: sum(takeWhile(<10000) (filter odd (map (^2) [1..]))) --Exemplo com operador (.): sum . takeWhile(<10000) . filder odd . map (^2) $ [1..] --Exemplo com operador ($): sum $ takeWhile(<10000) $ filter odd $ map (^2) [1..]
72 DIOGO AKIO BALBONI MIYAKE QuickCheck: É uma ferramenta para testes baseados em propriedades, é um metodo complementar aos testes de unidade. seus principios são baseados em deifnir uma propriedade do algoritmo e em um mecanismo que automáticamente e aleatoramente os casos de teste. O interessante da bibliotece QuickCheck é que ela gera testes de forma progressiva, onde começa coms casos simples e vai até casos mais complexos em busca de erros, quando um erro é encontrado ele vai retornar qual a instância que retornou o erro. ---------- Funções de Alta Ordem Funções como tipos Em Haskell uma função pode ser tratada como um tipo de dado. Pode ser utilizado como argumento de entrada ou de saída. Aplicação Parcial Uma forma de usar a função com mais de um argumento, é bem parecido com a forma que as calculadoras HO operam.. Funções de alta ordem são aquelas que recebem uma ou mais funções como argumento Ou que seu retorno seja a devolução de uma função. Alguns dos Exemplos mais comuns são : - map: transforma uma lista do tipo a para o tipo b utilizando uma função f :: a -> b - filter: devolve uma lista de todos os valores cujo o predicado p de x devolve True Map e Filter podem ser utilizadas juntas e também com list compreensions Operador Pipe ($) é utilizado para separar as aplicações de funções e remover parenteses. Folding obra a lista aplicando a função f em cada elemento da lista e um resultado parcial. Quando usar o foldr e foldl? Uma regra do dedão para trabalharmos por enquanto é: - Se a lista passada como argumento é infinita, use foldr - Se o operador utilizado pode gerar curto-circuito, use foldr - Se a lista é finita e o operador não irá gerar curto-circuito, use foldl - Se faz sentido trabalhar com a lista invertida, use foldl - Bônus! E temos ainda uma outra função chamada foldl' que aprenderemos mais para frente. Composição de funções significa aplicar uma função a um argumento e, depois, aplicar outra função ao resultado da primeira função. Em haskell é utilizado a assinatura (.) Ela pode ser associativa, e ter um elemento neutro. Na matemática a composição de função f∘g define uma nova função z tal que z(x)=f(g(x)).
18 EDUARDO AKIRA UENO
45 EDUARDO ALVES FERREIRA JUNIOR Quick Check: -Ferramenta para teste de código baseado em suas propriedades; -Definimos as propriedades a serem testadas e o quickcheck gera os testes (aleatórios e bem estruturados); -É possível passar parâmetros para a função de chamada do Quick Check e/ou usar tipos especiais nas assinaturas das funções para modelar melhor os testes (restrição de valores, número de testes etc). Funções de Alta Ordem: -Funções que recebem outras funções como argumento e/ou retorna funções; -Útil para criar funções genéricas que dependem de funções externas; -Quando o argumento x de uma função aparece no final da linha da função, podemos omiti-lo (não só para as de alta ordem); -map: (a -> b) -> [a] -> [b], f xs = [f x | x <- xs], aplica uma função em todos os elementos de uma lista; -filter: (a -> Bool) -> [a] -> [a], p xs = [x | x <- xs, p x], insere valores em uma lista dada uma condição; -map e filter costumam ser utilizados em conjunto. Ex: sum (map (^2) (filter even ns)) -podemos utilizar o pipe ($) para organizar melhor as precedências; -all: verifica se todos os elementos da lista cumprem uma condição; -any: verifica se algum dos elementos da lista cumprem uma condição; -takeWhile: "Copia" os elemtentos da lista até que haja uma ocorrência que não cumpre a restrição; -dropWhile: "Remove" da mesma forma que takeWhile; -foldr: Aplica a função com o "valor padrão" (argumento) ao último elemento da lista, aplica a mesma função utilizando o resultado desta operação ao penúltimo elemento da lista e assim vai..; -foldl: Parecido com foldr, mas vai do primeiro ao último elemento da lista (idealmente utilizsr Data.List (foldl', evita estouro de pilha de recursão)); -flip: inverte os argumentos -Composição de Funções: (f . g) x = f (g x)
19 EDUARDO MACIEL DE SOUZA Essa semana estudamos QuickCheck, que é uma ferramenta capaz de gerar testes pseudo-aleatórios para nossas funções em Haskel. Vimos também o conteúdo de funções de alta ordem, que são funções que recebem ou retornam outras funções. O QuickCheck, quando executado, é capaz de olhar para a assinatura de uma função e gerar testes de diferentes complexidades executando-os de forma incremental. Se algum teste falha ele nos indica qual input causou a falha. Podemos também definir quais vão ser os tipos de dados dos inputs que queremos em nossos testes. Para usar essa ferramenta, vimos algumas propriedades dos algoritmos de ordenação, e testamos nosso algoritmo segundo essas propriedades. As funções map e filter são dois exemplos de funções de alta ordem que são muito importantes e continuamente usadas em programação funcional, eles são funções de alta ordem, pois ambos necessitam de uma função nos parâmetros, seja para alterar os valores de um vetor ou selecionar argumentos segundo uma função condicional. Os operadores pipe ($) e o operador de composição (.) são dois operadores que possibilitam a escrita de funções mais complexas sem a confusão o uso de diversos parênteses. Também estudamos sobre Folding, que acabam por simplificar um padrão que é muito comum, tratam-se de funções que "dobram" uma lista, aplicando operação consecutivas em seus termos, como uma soma entra os elementos ou um produtório.
20 EUGENIO VERAS MARIA Quickcheck Ferramenta para teste de codigo que gera automaticamente e aleatoriamente casos de teste Retorna a instancia mais simples ao encontrar erro Conjectura de Collatz se numero é natural div numero 2 se nao numero * 3 + 1 Essa conjectura afirma que com um numero finito de repeticoes chegamos ao numero 1 para qualquer numero inicial Funcoes com tipos (Aplicação Parcial) Podemos passar uma funcao com um tipo de dados como argumento, que pode ser de entrada ou saida Funcoes de alta ordem Sao funcoes que recebem uma ou mais funcoes como argumento ou devolvem uma funcao Isso permite aumentar a expressividade Filter e map sao exemplos dessas funcoes Composicao de funcao O operador . compoem funcoes
21 FABIO DOS SANTOS DE SOUZA Nessa terceira semana da disciplina de paradigmas de programação, iniciamos nossos estudos conhecendo uma poderosa ferramenta do ambiente Haskell que permite ao desenvolvedor testar propriedades de programas e até mesmo provar, segundo o princípio de indução finita, a corretude desses. Com disso, testamos algumas funções e propriedades conhecidas delas no QuickCheck; por exemplo testamos o QuickSort e sua propriedade de idempotência, e a função par e sua propriedade de que um número não pode ser par e ímpar simultaneamente; vale observar que os testes do QuickCheck são aleatórios, o que garante uma maior confiabilidade. Vale notar que essa biblioteca nos permite escolher a quantidade de testes que serão feitos e usar modificadores de tipos para auxiliar nos testes. Em seguida, aprendemos sobre funções de alta ordem, que são funções que recebem e/ou retornam funções, exatamente como é no cálculo lambda, a partir disso construímos funções genéricas bastante úteis, como : *map ( que recebe uma lista e uma função f, e aplica f sobre cada elemento da lista) *filter ( que recebe uma lista e uma função f, e retorna os elementos da lista que satisfazem f) Apreendemos também sobre a função pipe($), uma função que tem uma certa precedência sobre as outras, e por isso, auxilia a eliminar parênteses, deixando o código mais legível. Vimos também outras funções de alta ordem, sendo elas : All, any, takeWhile e dropWhile. Também construímos as funções FoldR e FoldL, que nos permitem aplicar um certo padrão a nossa lista de maneira a reduzir ela; essas funções são muito importantes, pois, esse problema de reduzir listas é bem comum, note as funções : sum, product etc. Por fim, aprendemos sobre o operador (.) do Haskell para composição de funções, a mesma da matemática, esse operador nos permite eliminar parênteses, obtendo um código mais claro e legível,
22 FELIPE ASSIS
61 FELIPE AUGUSTO FLOR DE SOUZA Quickcheck: Testar o programa final; Verificar se o programa realmente faz o esperado; A lista deve ser ordenada; A lista de entrada deve ter o mesmo tamanho da de saída; Não deve ter elementos distintos; Idempotencia: Independente da quantidade de operações , o resultado é sempre o mesmo; O primeiro valor da lista é igual ao mínimo; Funções de alta ordem: Recebem uma ou + funções e retorna uma função como resultado; Map: Tranforma um tipo de lista em outro; Filter: Filtra uma lista, devolvendo valores previstos; Foldr: Dobra uma lista, aplicando uma função;
24 FELIPE DE SOUZA TIOZO
60 FELIPE MOREIRA TEMOTEO DA SILVA
25 FELIPE OLIVEIRA SILVA Nessa semana, foram abordados conceitos de QuickCheck e Funções de Alta Ordem. Na Engenharia de Software, utilizamos testes automizados para garantir que a entrada e saída de funções estejam corretas, permitindo com que manuntenções de código não quebrem o produto final. O Haskell permite, em algumas situações, provar matematicamente que seu programa está correto (usando indução). Quando o QuickCheck diz que alguma função passou nos testes, ele apenas quer dizer que não encontrou nenhum contra-exemplo possível não que a propriedade tenha sido provada. Isso pode ser associado a testes unitários onde os testes passsam mesmo podendo haver bugs caso os testes não tenham sido bem escritos. Outros conceitos básicos como if, else, then, where, length foram abordados nessa semana. Para finalizar, foi abordado o conceito de Funções de alta ordem, que podem receber uma ou mais funções como argumento, ou devolvem uma função como resultado. Exemplos mais utilizados de funções de alta ordem são map, filter, operador pipe e folding.
23 FELIPE PONSANO FRANKE A semana se inicia com a apresentação da bibiloteca quick check. Para usa-la é necessário instalar a bibiloteca no arquivo cabal e compilar. O quick check testa o seu modulo com cem entradas diferentes, com um crescente nível de complexidade. Se houver falha a checagem para e o programa retorna qual foi o teste que deu erro. Voce pode especificar quais entradas você não quer e qual a quantidade de testes que o programa fará. Dessa forma é possível testar seu programa de forma muito mais rápida e eliminar as variáveis humanas. Depois vemos funções de alta ordem, isto é, funções que recebem funções como argumento ou em aprte de seu corpo. Já uso funções de alta ordem pois crio funçoes auxiliares e as chamo dentro das principais, configurando uma função de alta ordem. Algumas funções de alta ordem uteis são o map e o fold. O map aplica uma função à uma lista, isto é, para cada valor que entra na lista, a função é aplicada. A lista, portanto, é do tipo de saída da função de entrada, já que todas as variaveis são aplicadas à função. O fold faz algo semelhante, mas aplica a função de entrada varias vezes. Ele troca os cons (:) pela função e coloca os parenteses da forma correta, de forma que a entrada da proxima função é a saída dela aplicada à variavel da lista.
31 GABRIEL ALBANO SANTOS
32 GABRIEL BELLOMI MEALE Quickcheck -Biblioteca que auxilia na implementação de casos de teste e checagem de um programa, gerando validações de testes em um conjunto de regras e condições específicas. -O quickcheck gera casos de testes simples e complexos, para avaliar o comportamento do algoritmo e maximizar sua confiança e assertividade. Funções de Alta Ordem - São funções que recebem outra função como parâmetro. Ou seja, é possível utilizar funções como um "tipo de dado". - Possibilita a implementação de funções como map e filter. map assinatura: map :: (a -> b) -> [a] -> [b] -Recebe uma função que recebe um dado do tipo a e retorna um do tipo b -Recebe uma lista do tipo a -Retorna uma lista do tipo b Uma implementação possível é aquela cuja para cada elemento da lista a, a função transforma o elemento de a para b, retornando uma lista do tipo b. map implementação: map f xs = [f x | x <- xs] filter assinatura: filter :: (a -> Bool) -> [a] -> [a] -Recebe uma função que recebe um dado do tipo a e retorna um booleano. -Recebe uma lista do tipo a -Retorna uma lista do tipo a Dessa forma, uma implementação possível é aquela cuja para cada elemento da lista "a" e um predicado, avalia-se o resultado. Se verdadeiro, o valor é adicionado à lista de saída "a". filter implementação: filter f xs = [x | x <- xs, f x] foldr assinatura: foldr :: (a -> b -> b) -> b -> [a] -> b -Recebe uma função que recebe um dado do tipo a, um dado do tipo b e retorna outro do tipo b. -Recebe um dado do tipo b -Recebe uma lista do tipo a -Retorna um dado do tipo b Dessa forma, a função (a -> b -> b) é recursiva dentre os elementos da lista a, até b. foldr exemplo: sum l = foldr (+) 0 l
26 GABRIEL DE MELLO FIALI Apresentação da biblioteca QuickCheck para implementar testes sobre o programa, que permite gerar dados automaticamente conforme a tipagem especificada pela função e condições estipuladas. - quickCheck <função> : função básica. - quickCheckWith stdArgs {argmumentos} : função com argumentos. Algumas restrições de entrada para limitar os parâmetros inseridos, provenientes de Test.QuickCheck.Modifiers: - NonNegative : Números a partir de 0 - Positive : Números maiores que 0 Apresentação de Funções de Alta Ordem, que assumem uma função como parâmetro ou retorno. - Todas as funções em haskell recebem apenas um parâmetro, com funções com múltiplos parâmetros simplesmente sendo uma representação resumida desse processo. - A partir disso é possível implementar aplicações parciais. Um ou mais argumentos são aplicados, enquanto outro pode ser definido posteriormente na chamada da função. - Algumas funções de alta ordem já estão implementadas para listas: - Map : aplica uma função em todos os elementos de uma lista - Filter : aplica uma função sobre os elementos que satisfazem determinada condição - All : retorna verdadeiro/falso se todos os elementos da lista satisfazem determinada condição - Any : retorna verdadeiro/falso se pelo menos um dos elementos da lista satisfazem determinada condição - takeWhile : inclui elemento em uma lista se determinada condição é satisfeita. - dropWhile : remove elemento em uma lista se determinada condição é satisfeita. Funções foldr/foldl: - Funções já definidas para aplicar operações recursivas sobre uma lista, especificando um valor base. - Apresentam diferenças na forma de sua execução, pois diferem nos parâmetros recebidos. - foldr pode ser utilizada nos casos em que a lista fornecida é infinita ou o argumento utilizado pode gerar curto-circuito. - foldl pode ser utilizada quando o operador não gera curto-circuito ou quando se tem interesse em trabalhar com a lista invertida. Composição de funções (.): - Seguem as propriedades associativa e a presença da função identidade (elemento neutro). - Permite a composição de listas e também é uma ferramenta útil para tornar o código mais conciso.
29 GABRIEL MENDONÇA FARIAS Em Haskell, é possível provar matematicamente se a programação está correta, já que a mesma se baseia no uso de funções. Além disso, é possível utilizar o QuickCheck, para inferir propriedades ao algoritmo e verificar se seu funcionamento é o esperado segundo as propriedades estabelecidas. Para testar um projeto usando o QuickCheck, é necessário criar um projeto e modificar o arquivo .cabal, inserindo propriedades, que podem ser utilizadas através da função import no programa que está a ser desenvolvido. É possível verificar determinadas propriedades através de funções. Ao utilizar a função QuickCheck é possível automatizar os testes a serem feitos para verificar as propriedades das funções, buscando um contra exemplo e retornando o primeiro caso a apresentar uma discrepância do esperado. O teste de Collatz também pode ser utilizado para verificar propriedades, no entanto, é necessário que sua função atue sobre um valor n, que de algum modo se chegue a n = 1 e que collatz 1 = 1 Funções em Haskell podem ser interpretadas como dados, logo, é possível criar funções que tenham como dados de entradas e saídas outras funções. Inclusive, é possível inserir funções nos os valores recebidos em uma lista. A função map é indicada para transformar uma lista de certo tipo de entrada, em uma lista de outro tipo na saída. Filters são condições colocadas na hora de se formar uma lista, tal que n deva respeitar aquela condição permitindo que aquele valor entre ou não na lista, estes podem ser colocados nos guards das listas, ou mesmo escrevendo a função filter. O operador pipe $ auxilia no processo de separar aplicações dentro da função, o que pode tornar a programação mais clara e com menor uso de parêntesis. Foldr é uma forma de agregar funções de funções, generalizando partes da aplicação.
30 GABRIEL MURAKAMI ALVES QuickCheck) QuickCheck é uma biblioteca Haskell baseada em propriedades que permite a aplicação de testes unitários automatizados. Nela, podemos implementar testes que garantem que sua função possui um comportamento esperado. Por exemplo, idempotência, paridade, ordenação e etc. Podemos definir n propriedades para uma mesma função. Em sua execução o QuickCheck cria casos de testes progressivos, partindo dos mais simples até os mais complexos. Ao econtrar um erro ele aborta a execução e retorna o caso encontrado. Funções de Alta Ordem) São denominadas função de alta ordem toda e qualquer função que recebe como argumento uma ou mais funções ou que seu retorno seja uma função. Funções de alta ordem muito comuns para listas são o `map` e o `filter`. Ambas recebem uma função como argumento e a aplicam em cada elemento da lista. Uma função de alta ordem interessante é a `foldr`. Nesse caso, diferente das acima citadas, além de aplicar a função de argumento em cada elemento, a mesma gera a resposta através de resultados parciais "dobrando" a lista. Podendo por exemplo criar equivalentes às funções `sum` e `product` de maneira simples. A função `foldl` possui o mesmo comportamento de `foldr` porém resolvede maneira inversa. Dessa forma, se a função de argumento for associativa, a aplicação de `foldr` e `foldl` não se alteram. A escolha entre uma ou outra depende da aplicação do problema, algo que pode não ser trivial e requerer análise mais aprofundada.
38 GABRIEL RIOS SOUZA QuickCheck: - Ferramenta para testes de códigos baseados em propriedades (Provar Corretude do Algoritmo) - Princípios: - Define-se uma propriedade (invariante) do algoritmo - O mecanismo de teste gera automática e aleatoriamente casos de teste - Comando para utilizá-lo no Main.hs: import Test.QuickCheck - A biblioteca QuickCheck gera casos de testes progressivos, começando de casos simples até casos mais complexos em busca de erros. - Exemplo de utilização no ghci, após a implementação da função/propriedade prop_idempotencia no Main.hs: quickCheck prop_idempotencia - Ao encontrar um erro, ele retorna a instância mais simples que deu errado. - Podemos utilizar a função ==> (implicação) dentro da propriedade para especificar que só queremos fazer testes caso algo seja verdade. - OBS: ao utilizar ==> na sua propriedade, dentro da assinatura da mesma, o tipo de retorno deve ser Property. - É possível utilizar modificadores no argumento para especificar qual tipo de argumento você deseja que seja usado nos testes: - Exemplos: - NonNegative - Positive - Por padrão o QuickCheck faz 100 testes na propriedade desejada, mas é possível alterar esse número: - Exemplo QuickCheck para 5000 testes (utilizando sintaxe de records ainda não vista '{' '}') na função/propriedade prop_seImparNaoPar: quickCheckWith stdArgs {maxSuccess = 5000} prop_seImparNaoPar - Lembre-se o QuickCheck dizer que algo passou em X testes apenas quer dizer que ele não encontrou nenhum contra-exemplo para a propriedade sendo testada, não que a propriedade tenha sido provada. Funções de Alta Ordem: - Recebem funções como argumento, ou devolvem uma função. - Exemplos: - map (aplica uma função em uma lista) - filter (retorna elementos da lista em que uma função retorna True) - all - any - takeWhile - dropWhile - o operador Pipe $ serve para separar as aplicações das funções e remover os parênteses. Folding (Folds): funções de recursão - foldr - foldl (Caudal) - Usos: - foldr: se a lista passada como argumento é infinita ou o operador pode gerar curto-circuito. - foldl: caso contrário ou queira trabalhar com a lista invertida.
28 GABRIEL ROSSETTO MIGLIORINI QuickCheck é uma biblioteca que permite testar se o código funciona como esperado. Para isso declaramos funções que capturem propriedades a serem testadas. Por exemplo, no caso de um código de ordenamento de lista temos a propriedade de tamanho constante. Ou seja, independente da quantidade de vezes que ordenamos a lista o tamanho se mantém. Então, criamos uma função para analisar isso e então passamos como parâmetro do QuickCheck. Após isso o QuickCheck injeta conjuntos de argumentos pré prontos e verifica se as propriedades de saída são as esperadas. Funções de alta ordem ~Toda função que recebe um ou mais argumentos que são funções é chamada função de alta ordem. ~A função MAP serve para aplicar uma função sobre todos elementos de uma lista. ~A função filter serve, como o nome sugere, para filtrar elementos de uma lista. ~O operador $ ajuda no layout das funções uma vez permite a elimininação de parênteses entre funções. ~All, any, takeWhile e dropWhile são demais funções auxiliares para operar sobre listas. ~Funções compostas em haskell utilizam o operador (.) e possuem propriedade associativas e de elemento neutro.
35 GEORGE HARRISON ROCHA • QuickCheck: - Ferramenta que verifica a corretude de um código ao gerar automaticamente casos aleatórios de entrada e saída das funções a fim de verificar se apresentam certas propriedades; - Sua biblioteca gera casos de testes progressivos; - Retorna a instância com saída inesperada mais simples ao encontrar um erro; - Podemos especificar instâncias que não queremos testar; - Os testes passarem não implicam em ausência de erros; - Nas aulas foram apresentados testes de propriedades de alguns algoritmos, como QuickSort, Paridade e Fatorial. • Funções de Alta Ordem: - São funções que recebem funções como argumentos ou retornam uma função; - Essas funções permitem aumentar a expressividade dos códigos em Haskell; - Em Haskell funções podem ser representadas como um tipo de dado; - Aplicação Parcial: envolve passar menos argumentos que o esperado para uma função. É uma maneira de criar funções em tempo de execução; - Funções de alta ordem para listas: - Map: Uma função que recebe uma lista e uma função como argumentos, 'mapeia' cada elemento da lista e aplica a função passada como argumento. Retorna a lista 'mapeada'; - Filter: Uma função que recebe uma lista e uma função como argumentos e retorna uma lista contendo apenas os elementos que satisfazem a função passada como argumento; - Essas duas funções costumam ser utilizadas juntas; - Temos outras funções úteis de alta ordem, como all, any, takeWhile, dropWhile... • Folding - folr e folrl: funções genéricas que dobram uma lista aplicando uma função em cada elemento da lista. - A escolha entre essas duas funções, quando é possível usar qualquer uma das duas, é feita após analisar o desempenho das duas versões. • Composição de funções - No Haskell temos o operador (.), que define a composição de funções de forma semelhante à da matemática.
36 GERALDO MAJELLA NUNES JUNIOR
37 GIANCARLO KAMI DELL ARINGA VIANA Nesta semana foram introduzidos o QuickCheck, que serve para realizar testes de propriedades em algoritmos, e funcoes de alta ordem, mais especificamente map, filter e o operador pipe. map aplica uma funcao em cada elemento de uma lista, enquanto filter retorna uma lista com os elementos da lista recebida que sao aceitos pela funcao recebida. Por fim, foi introduzidp a funcao fold, que realiza elementos em todos os elementos de uma lista e seu subproduto.
79 GIOVANNA NOGUEIRA QuickCheck é uma biblioteca do haskell utilizada para realizar testes automáticos e aleatórios (gera os dados de teste aleatoriamente) baseando-se nas propriedades do código, mostrando depois de quantos testes e em que caso houve a falha. Funções de Alta Ordem são aquelas que recebem outras funções como argumento ou que devolvem uma função, ou ambas as situações. São úteis para criar funções genéricas que dependem de funções externas como parâmetro, e permitem aumentar a expressividade do código, principalmente quando há padrões recorrentes. Exemplos apresentados: map, filter, foldr, foldl. Uma aplicação parcial ocorre quando algum argumento da função é omitido para ser inserido posteriormente, como direto durante a execução.
34 GIOVANNI ALMEIDA DE SOUSA Semana 3 - Paradigmas de Programação 1. Quickcheck a. Ferramenta para teste de código que define uma propriedade invariante do algoritmo e gera automaticamente e aleatoriamente casos de testes. b. A biblioteca realiza os testes de forma progressiva, com entradas mais simples até as mais complexas buscando por erros. Caso seja encontrado, será retornado o caso mais simples com erro. c. Exemplo de declaração: quickCheck prop_idempotencia i. Para prop_idempotencia: prop_idempotencia :: Ord a => [a] -> Bool prop_idempotencia xs = qsort (qsort xs) == qsort xs d. Não haver erros nos testes de Quickcheck não significa que o código não contém erros, mas sim que nenhum contraexemplo foi encontrado dentro do universo testado. 2. Funções de Alta Ordem a. Em Haskell, funções podem ser pensadas como um tipo de dado, tanto para argumento de entrada como de saída. b. Funções de alta ordem recebem uma ou mais funções como argumento ou devolvem uma função como resposta. c. A função map transforma uma função do tipo [a] para outra do tipo [b], seguindo a seguinte definição: map :: (a -> b) -> [a] -> [b] map f xs = [f x | x <- xs] d. Outra função bastante utilizada para manipulação de listas é o filter, que devolverá uma lista dos valores quando o predicado p de x for True, conforme definição: filter :: (a -> Bool) -> [a] -> [a] filter p xs = [x | x <- xs, p x] e. Outras funções de alta ordem: all, any, takeWhile e dropWhile. f. Função foldr pode ser utilizada para definir algumas funções, por exemplo a função sum: foldr :: (a -> b -> b) -> b -> [a] -> b foldr f v [] = v foldr f v (x:xs) = f x (foldr f v xs)
39 GIULIA RIBEIRO DE CARVALHO
41 GUILHERME FERREIRA GALDINO Quick Check - Ferramenta de testes definindo propriedades para que se gere casos automáticos e aleatórios prop_idempotencia :: Ord a => [a] -> Bool prop_idempotencia xs = qsort (qsort xs) == qsort xs quickCheck prop_idempotencia Funções de Alta Ordem - Funções que recebem outra função como argumento ou retornam outra função ou, até mesmo, ambos. - Aplicação Parcial Para funções que possuem mais do que um argumento, é possível omitir o último argumento soma3 = soma 3 <=> soma3 x = soma 3 x Exemplos de funções de Alta ordem Map map :: (a -> b) -> [a] -> [b] map f xs = [f xs | x < xs] map (+1) [1,2,3] = [2,3,4] Filter filter :: (a -> Bool) -> [a] -> [a] filter p xs = [xs | x <- xs, p x] filter even [1..10] = [2,4,6,8,10] Operador pipe ($) - Evitar repetição de parênteses - ($) :: (a -> b) -> a -> b somaQuadPares :: [Int] -> Int somaQuadPares ns = sum $ map (^2) $ filter even ns Folding - Sabendo que boa parte das funções recursivas possuem o padrão, o folding generaliza este padrão. - FoldR foldr :: (a -> b -> b) -> b -> [a] -> b foldr f v [] = v foldr f v (x:xs) = f x (foldr f v xs) Na prática fica: a1 `f` (a2 `f` (a3 `f` v)) foldr (+) 0 [1,2,3] 1 + (2 + (3 + 0)) - FoldL ou Folding Caudal foldl :: (a -> b -> a) -> a -> [b] -> a foldl f v [] = v foldl f v (x:xs) = foldl f (f v x) xs Na prática fica: ((v `f` a3) `f` a2) `f` a1 - Dependendo do caso, o foldr e o foldl possuem desempenhos diferentes para o mesmo problema. O estudo é um pouco mais avançado e será discutido posteriormente. Por enquanto a seguinte regra vale: Se a lista passada como argumento é infinita, use foldr Se o operador utilizado pode gerar curto-circuito, use foldr Se a lista é finita e o operador não irá gerar curto-circuito, use foldl Se faz sentido trabalhar com a lista invertida, use foldl Composição de funções - O operador (.) é equivalente ao f o g na matemática (.) :: (b -> c) -> (a -> b) -> (a -> c) f . g = \x -> f (g x) - Associativa (f . g) . h == f . (g . h) - Identidade (id = elemento neutro) f . id = id . f = f - Exemplo somaDosQuadradosImpares = sum . takeWhile (<10000) . filter odd . map (^2) $ [1..]
42 GUILHERME FUZISAWA DE SA
43 GUSTAVO MATHEUS LIMA SANTOS Haskell possui uma biblioteca para realizar testes nos resultados de um código para verificar sua corretude. Isto é implementado através da biblioteca QuickCheck que realiza testes baseados em propriedades como se a lista está ordenada, se a lista tem o mesmo tamanho da entrada. Por padrão esta biblioteca realiza 100 testes em que a complexidade aumenta progressivamente. Também é possível filtrar os casos de teste para não verificar casos que não façam sentido. Em Haskell podemos utilizar funções como entrada e/ou saída de outras funções, ou seja, podemos considerar uma função como tipo de dado. Por exemplo, uma função que retorna a função soma deve ter a seguinte assinatura: soma :: Int -> (Int -> Int) Também há a aplicação parcial de uma função em que um nome (como se fosse o nome de uma variável) recebe uma expressão e a aplica, por exemplo: dobra = (*2) As funções que recebem uma ou mais funções como argumento ou devolvem uma função são chamadas funções de alta ordem. Elas permitem aumentar a expressividade do código quando há padrões recorrentes. Alguns exemplos de funções de alta ordem comumente aplicadas às listas são: map, filter, even e odd. Essas funções podem ser aplicadas em conjunto, como comumente ocorre com map e filter. Haskell também possue funções que dobram a lista aplicando a função f em cada elemento da lista e um resultado parcial, é o caso das funções foldr e foldl. Em geral, utiliza-se foldr quando a lista passada como argumento é infinita e se o operador utilizado pode gerar curto-circuito, caso contrário utiliza-se foldl que também é utilizada quando faz sentido trabalhar com a lista invertida. Similarmente ao conceito matemático de composição de funções, haskell permite composições de funções através do operador ponto (.)
33 GaMendes Nessa semana do curso aprendemos que a linguagem Haskell permite, em algumas situações, provar matematicamente que seu programa está correto (usando indução), mas quando isso não é possível, a única saída é realizar testes com várias entradas diferentes, e analisar as saídas respectivas, procurando por possíveis inconsistências. Fazer isso manualmente seria extremamente trabalhoso, e passível de erros, e por isso, a linguagem Haskell dispõe, além de outras, de uma biblioteca de testes, QuickChek, para ajudar nesse trabalho. O QuickCheck é uma ferramenta para teste de código baseado em propriedades, que a partir de uma invariante definida pelo usuário, gera automática e aleatoriamente casos de testes para nossos programas. Depois de aprendermos a testar nosso código com a biblioteca QuickCheck, fomos apresentados ao conceito de funções de alta ordem. Em Haskell, podemos pensar em uma função como um tipo de dado. Esse tipo tanto pode ser utilizado como argumento de entrada assim como o argumento de saída da função, resumindo, funções de alta ordem, é o conceito que viabiliza passar uma função como parâmetro para outra função. Ainda dentro do conceito de funções de alta ordem, aprendemos sobre a possibilidade de aplicação parcial na linguagem Haskell, que trata-se de passar menos do que o número total de argumentos para uma função que recebe vários argumentos. Depois disso, vimos sobre a aplicação de funções de alta ordem em listas, e algumas funções padrões da linguagem Haskell, como map, filter, foldR, foldL. Também vimos como "implementá-las na mão”. Ainda nesse tópico, após verificar que as linhas ficavam muito extensas dependendo da quantidade de funções que usávamos, aprendemos como organizar nosso código em várias linhas usando o operador pipe.
8 HEITOR BELLINI - QuickCheck Gera casos de teste para avaliar propriedades conhecidas de um algoritmo (funções de propriedade). Exemplo: qsort :: Ord a => [a] -> [a] qsort [] = [] qsort (x:xs) = qsort lhs ++ [x] ++ qsort rhs where lhs = [e | e <- xs, e < x] rhs = [e | e <- xs, e > x] prop_minimum :: Ord a => [a] -> Bool prop_minimum xs = head (qsort xs) == minimum xs Em caso de falha, retorna o caso mais simples onde a falha ocorreu: > quickCheck prop_minimum *** Failed! Exception: 'Prelude.head: empty list' (after 1 test): [] OBS: o tipo Property permite descartar casos de testes que não se aplicam à propriedade avaliada (como na função propriedade acima): prop_minimum :: Ord a => [a] -> Property > quickCheck prop_minimum +++ OK, passed 100 tests. - Funções de Alta Ordem São funções que podem receber funções como argumento ou retornar funções. Também podemos pensar em funções como tipo de dados: soma :: Int -> (Int -> Int) -- função soma retorna uma função (Int -> Int) soma x y = x+y soma3 = soma 3 soma3 2 >>> 5 - Função map: È definida como: map :: (a -> b) -> [a] -> [b] -- recebe como parâmetro uma função f e uma lista map f xs = [f x | x <- xs] -- e retorna outra lista que foi aplicada à função f - Função filter: È definida como: filter :: (a -> Bool) -> [a] -> [a] -- recebe uma função e uma lista como parâmetro filter p xs = [x | x <- xs, p x] -- e retorna uma lista na qual atendeu ao predicado p Ambas funções são geralmente utilizadas juntas: somaQuadPares :: [Int] -> Int somaQuadPares ns = sum [n^2 | n <- ns, even n] -- ou implicitamente, pode-se: -- somaQuadPares ns = sum (map (^2) (filter even ns)) - $ È definida como: ($) :: (a -> b) -> a -> b Possibilita o uso de $ ao invés de parênteses! - foldr È definida como: foldr :: (a -> b -> b) -> b -> [a] -> b foldr f v [] = v foldr f v (x:xs) = f x (foldr f v xs) Onde (x:xs): a1 : (a2 : (a3 : [])) Substituindo cons por f e [] por v (valor padrao): a1 `f` (a2 `f` (a3 `f` v)) Logo, em linhas gerais foldr começa "do inicio da lista", e foldl "o fim da lista". foldl é definida abaixo: foldl :: (a -> b -> a) -> a -> [b] -> a foldl f v [] = v foldl f v (x:xs) = foldl f (f v x) xs Onde: ((a3 : []) : a2) : a1 Substituindo: ((a3 `f` v) `f` a2) `f` a1
44 HENRIQUE AUGUSTO DE OLIVEIRA Ao desenvolver uma aplicação ou funcionalidade, é necessário verificar se a mesma se comporta da forma esperada através de testes. Uma opção é o QuickCheck, que é uma biblioteca para corretude de código e testes automatizados. Para implementar, no <arquivo_do_programa>.cabal, é necessário colocar QuickCheck nos builds dependencies e importar o "Test.QuickCheck" no código. O objetivo principal é gerar testes das propriedades que se deseja testar de forma automática. Ao dar erro, ele retorna o caso mais simples de erro. É possível usar um verificador de valores do QuickCheck, como por exemplo NonNegative, que assume que um elemento não possa ser negativo. Pode ser entendido função de alta ordem como funções que recebem funções como argumento ou retornam funções. É muito útil para criar função genérica que depende de função externa. Passar menos argumentos para uma função que recebe mais de um argumento é uma definição de aplicação parcial. Por exemplo, ao definir uma função dobra como *2, ao aplicar o dobra no 5, o retorno será 10. O map é uma função que transforma uma lista do tipo a para o tipo b usando f::a -> b. O filter devolve uma lista de todos os valores cujo, aplicado um predicado em um valor, esse retorno é verdadeiro. Uma forma de organizar o código e utilizar menos parênteses é com o pipe. A ideia do fold é justamente dobrar a lista e aplicar uma função em cada elemento. Temos o foldr e o foldl. É indicado usar o foldr caso a lista passada possa ser infinita e o operador possa gerar curto circuito. O foldl é indicado para caso o operador não gere curto circuito, a lista é finita e faz sentido trabalhar com lista invertida.
46 HENRIQUE FANTATO SILVA DE ALBUQUERQUE Uma parte importante do desenvolvimento de software é o teste. Haskell permite, em algumas situações, provar matematicamente que seu programa está correto(indução). Outra forma de testar seu código é através da biblioteca QuickCheck, que com base em uma propriedade invariante do algoritmo criado, gera aleatoriamente casos de teste. Existe várias propriedades que podem ser utilizadas para testar um algoritmo, e para cada algoritmo existe uma propriedade correta. Exemplo: para um algoritmo de ordenação, podemos testar com base na propriedade de idempotência(ordenar duas vezes uma mesma lista, tem que gerar o mesmo resultado de ordenar apenas uma vez), ou até mesmo comparar o tamanho original da lista contra o tamanho da lista de saída (devem possuir o mesmo tamanho). Haskell também aceita uma função como um tipo de dado, logo podemos utilizar funções como como argumento de entrada ou de saída. Com base nessa propriedade, temos as funções de alta ordem, que recebem funções como argumento, ou devolvem uma função. O uso desse tipo de função torna o Haskell mais expressivo. Exemplos de funções de alta ordem: map, filter, etc.
92 HENRIQUE MAGRO DE SOUZA
47 IAN LACERDA DA SILVA
48 IGOR SAWAKI Em Haskell, uma função pode ser considerada como um tipo de dado e utilizada como parte de outras funções. Uma função que recebe uma outra função como argumento é chamada de função de alta ordem, por exemplo: - função map: aplica uma função f a cada elemento de uma lista; - função filter: devolve somente os elementos de uma lista que obedecem a um dado predicado. Para reduzir os parênteses que englobam funções, podemos utilizar o operador ($), separando as aplicações das funções. Este operador está relacionado à precedência dos "()". De outro modo, podemos fazer a composição de funções com o operador (.). Este operador está relacionado ao encadeamento de funções. As funções fold aplicam uma dada função entre cada elemento de uma lista, ou seja, o resultado da função aplicada em um elemento será um argumento da aplicação da função no elemento seguinte, além de um valor inicial. foldr começa a aplicação das funções pelo primeiro elemento da lista (associativo a direita), até chegar ao último elemento, que é aplicado com o valor inicial. Por exemplo: foldr f z [1..4] => 1:2:3:4:[] => 1:(2:(3:(4:[]))) => 1 f (2 f (3 f (4 f z))) foldl começa a aplicação pelo primeiro elemento da lista invertida (associativo a esquerda), até chegar ao último elemento, que é aplicado com o valor inicial. Por exemplo: foldr f z [1..4] => 1:2:3:4:[] => ((([]:1):2):3):4 => (((z f 1) f 2) f 3) f 4
78 IVO VECELIC NETO
49 JANUSA MAIA DA SILVA QuickCheck Após executar um programa sem erros podemos verificar a corretude através de testes de entrada e saída das funções criadas e verificar se elas apresentam algumas propriedades esperadas. Ex. Na ordenação de uma lista, a lista tem que estar ordenada, tem que ter o mesmo número de elementos e deve ter os mesmos elementos da lista inicial. Para incluir a biblioteca QuickCheck, adicionamos em build-depends no arquivo .cabal; Exemplos de execução: quickCheck (<nome_da_função> :: [Int] -> Bool). quickCheckWith stdArgs {maxSuccess = 5000} <nome_da_função>, que executará 5000 testes. Mais em: https://www.schoolofhaskell.com/user/pbv/an-introduction-to-quickcheck-testing https://www.fpcomplete.com/blog/2017/01/quickcheck https://hackage.haskell.org/package/QuickCheck Funções de alta ordem Recebem funções como argumentos ou retornam funções. -map: aplica uma função a cada elemento da lista e retorna a nova lista. -filter: filtra os elementos de uma lista, retornando uma lista do mesmo tipo. -Operador $: permite concatenar a aplicação de funções eliminando parênteses. -all: True se todos os elementos são verdadeiros. -any: True se algum elemento for verdadeiro. -takeWhile: retorna os elementos enquanto satisfazem a condição. -dropWhile: remove os elementos enquanto satisfazem a função. -foldr: recebe uma função, um valor e uma lista e retorna um valor. Ex.: foldr (+) 0 [1..3] => 1 + (2 + (3 + 0)) -foldl: implementa uma versão caudal da recursão. Ex.: foldl (+) 0 [1..3] => (( 0 + 1) + 2 ) + 3 - se a lista passada como argumento pode ser infinita ou se o operador utilizado pode gerar curto-circuito, use foldr. - se a lista é finita e o operador não gera curto-circuito, ou se se faz sentido trabalhar com a lista invertida, use foldl - quando usar foldl, o ideal pe usar o foldl’, importando do Data.List. Ele evita o estouro de pilha.
50 JEAN AUGUSTO DE ARAUJO
94 JEAN DA SILVA NEVES
51 JULIO NOVAES DA FONSECA Resumo Semana 3 - Julio Novais - RA 21073215 -------------------------------------------- Durante a Semana 3 aprendemos sobre: - QuickCheck - Uma biblioteca para realizar testes confiáveis e automatizados para testar algoritmos com base em suas propriedades - Como instalar e utilizar a biblioteca e gerar casos de teste com base em propiedades como idempotencia, tamanho, etc. - Funções de alta ordem (Higher Order Functions) - Basicamente, funcões que manipulam outras funcões - Funcionamento e casos de usos de funcões de alta ordem nativas do Haskell como map, filter, etc. - Folding com foldr e foldl e quando usar cada um deles - Composição de funções - Como fazer composição de funções e seus casos de uso - O operador ., seu funcionamento e diferenças para o operador $
52 KAREN OLIVEIRA DOS SANTOS Apresentação da biblioteca QuickCheck que serve para gerar os testes. Funções de alta ordem permite receber um função dentro de outra ou retornar uma função Composição de funções, igual a composição de funções da matemática. Ex: 2*(x^2). Um função aplica a potência e outra a multiplicação. A aula foi voltada para implementação dessas funcionalidades nem Haskell.
53 KELVIN ALVES DOS SANTOS
54 KLEVERSON NASCIMENTO PINTO - Quickcheck: - Ferramenta onde é possível testar códigos em haskell - Os casos de testes são gerados aleatoriamente pela própria plataforma - É possível definir o número de casos de testes, bem como definir algumas pré-condições para os valores que serão gerados - Importante: Apesar de dar um forte indício de que a implementação está correta, não pode ser considerado uma prova formal - Funções de alta ordem: - Em haskell as funções podem ser tratadas como um tipo, tal como String, Integer, Bool e etc. - São chamadas de funções de alta ordem funções que recebem uma função como paramêtro ou que devolvem uma função - Funções de alta ordem muito usadas em listas: - Map - Filter - Fold - É a base que permite que funções como map e filter sejam implementadas - Tem o foldr e o foldl, a diferença é se o cálculo será feito da direita pra esquerda ou da esquerda pra direita - Decidir entre o foldr e o foldl depende do problema, pode não ser trivial - Composição de funções - Podem ser usados parenteses, ponto final ou $ para definir a composição de funções
93 LARISSA RODRIGUES DE ALMEIDA #QuickCheck O teste de um software é muito importante para verificação da corretude. O Haskell possui formas de testes como indução matemática e verificação das entradas e saídas para analisar se apresentam os resultados esperados. O QuickCheck é uma ferramenta que auxilia nos testes dos códigos. Para utilizar essa ferramenta, é necessário seguir alguns passos: - Analisar as propriedades de entrada e saída esperadas do código. - Definir uma invariante do algoritmo. - Codificar as comparações necessárias com base na invariante. - O QuickCheck irá gerar de forma automática e aleatória diversos casos de testes e disponibilizará quantos testes passaram. Caso houver algum teste que não tenha passado, ele irá informar a instância mais simples que deu errado. #Funções de Alta Ordem No Haskell é possível utilizar funções de alta ordem, no qual podem receber uma ou mais funções como argumento ou podem devolver uma função. Essas funções permitem o aumento da expressividade em padrões recorrentes, principalmente em listas. Alguas funções de alta ordem úteis são: - Map: uma função que recebe uma lista e a transforma (f :: a -> b). - Filter: função que filtra os elementos de uma lista. - Operador Pipe: separa as aplicações das funções e remove os parênteses. #Folding A função foldr nos auxilia em diversos tipos de cálculos em listas. O funcionamento da função se baseia em dobrar a lista aplicando a função "f" em cada elemento, gerando um resultado parcial. Outra expressão similar é o foldl, porém a função é aplicada da esquerda para a direita, diferentemente do foldr.
56 LEANDRO RIBEIRO DE ALMEIDA
57 LEANDRO VICTOR FERREIRA QuickCheck: Utiliza-se para realização de teste no algoritmo, para isso o QuickCheck parte de alguns princípios para verificar se o código partindo de inputs possui determinadas propriedades. Para isso ocorrer, deve-se definir qual propriedade do algoritmo deseja ser testada e com isso elaborar o mecanismo que irá realizar esta verificação. Os testes são realizados a partir da importação do Test.QuickCheck e com isso pode ser utilizado nos mecanismos. Função de Alta Ordem: Uma função recebe esse nome, quando por ela pode receber uma função como input ou ter como output, além de poder realizar ambos. Essa habilidade torna-se útil na criação de funções genéricas que dependem de funções externas tidas como parâmetros de inputs nas funções principais. Mapeamento: Usa-se a função map para aplicar um método,por meio de uma função, item a item da lista. Isso implica uma nova lista, mas com seus itens modificados de acordo com a regra da condição dentro do map. Filtragem: Aplica-se a função filter quando se deseja selecionar elementos de acordo com um propriedade específica, por meio de uma função, dentre todos os elementos da lista, tendo como resultado apenas os itens que possuam a propriedade designada.
58 LEONARDO SANTIAGO HAMPSHIRE Testes de Propriedades - QuickCheck -> Teste automáticos através das propriedades desejadas do algoritmo -> Metodo complementar baseado em exemplos Para incluir a biblioteca: -> Dentro de Cabal, build-depends: QuickCheck -> No arquivo (Main) importar a biblioteca Test.QuickCheck Teste no arquivo: -- $> vetor[objetos] em outro terminal: ghcid --allow-eval o quickcheck vai aumentando o nível de complexade conforme são implementados mais testes -> Isso permite descartar testes que não fazem sentido pro programa. Funções de Alta Ordem -> Em haskell uma função pode ser considerada um "tipo de dado" -> Todas as funções em haskell são, efetivamente, funções de um único argumento -> Definição de função pode ser interpretada como uma equaçãoo [f x | x <- xs] (map) -> Função MAP -> mapeia um array de acordo com uma função de entradao -> Função Filter -> define um predicado para elementos de uma lista -> Operador "Pipe" ($) -> Permite melhor organização do código evitando parenteses
86 LOUIS PHILLIPE SARDA DUBOIS Semana 2 – Aula 1: QuickCheck: testes baseados em propriedades, essa biblioteca automatiza a geração de dados para testes, gera testes progressivos, começando de casos mais simples até casos mais complexos, retorna a instância mais simples que deu errado. Para rodar: quickCheck prop_Nome_Func Para alterar quantidade de testes: quickCheckWith stdArgs {maxSuccess = 5000} prop_Nome_Func Conjectura de Collatz: é bem simples de formular de maneira informal dado um número natural, se o número é par então divida por 2; senão multiplique por 3 e adicione 1, após um número finito de iterações, chega-se sempre no número 1 para qualquer valor inicial. Semana 2 – Aula 2: Funções como tipos: funções podem ser consideradas um tipo de dado, podendo ser utilizada como argumentos de entrada e/ou saída de outras funções. Exemplo: soma :: Int -> (Int -> Int) soma x y = x+y soma3 = soma 3 soma3 2 Resultado: 5 Aplicação Parcial: soma3 = (+3) soma3 2 Resultado: 5 Funções de alta ordem: funções que recebem uma ou mais funções como argumento, ou devolvem uma função. duasVezes :: (a -> a) -> a -> a duasVezes f x = f (f x) duasVezes (*2) 3 => 12 duasVezes reverse [1,2,3] => [1,2,3] Operador pipe($): usado para separar as aplicações das funções e remover os parênteses Funções de alta ordem úteis: all, any, takeWhile, dropWhile Folding: foldr Exemplo soma todos elementos da lista: foldr (+) 0 [1,2,3] sum = foldr (+) 0 length = foldr (\_ n -> n + 1) 0 Função foldl: length = foldr (\_ n -> n + 1) 0 length = foldl (\n _ -> n + 1) 0 foldr vs foldl Lista infinita/operador pode gerar curto-circuido => foldr Caso contrário, e se faz sentido trabalhar com a lista invertida => foldl
64 LUCAS AKIRA HASEGAVA QuickCheck Ferramente utilizada para testar codigos Exemplo qsort :: Ord a => [a] -> [a] qsort [] = [] qsort (x:xs) = qsort lhs ++ [x] ++ qsort rhs where lhs = [e | e <- xs, e < x] rhs = [e | e <- xs, e > x] > quickCheck (prop_length :: [Int] -> Bool) *** Failed! Falsifiable (after 5 tests and 1 shrink): [1,1] import Test.QuickCheck qsort :: Ord a => [a] -> [a] qsort [] = [] qsort (x:xs) = qsort lhs ++ [x] ++ qsort rhs where lhs = [e | e <- xs, e <= x] rhs = [e | e <- xs, e > x] > quickCheck (prop_length :: [Int] -> Bool) +++ OK, passed 100 tests. -------------------------- Funções de Alta Ordem Funções que recebem funções como argumento e devolvem uma função Exemplos [f x | x <- xs] map f xs = [f x | x <- xs] > filter even [1..10] [2,4,6,8,10] Operador pipe somaQuadPares ns = sum $ map (^2) $ filter even ns ------------------------ Fold Funções de fold permitem percorrer uma lista de valores gerando um resultado cumulativo. Exemplos Folfd snoc x xs = xs ++ [x] reverse = foldr snoc [] Foldl reverso' = foldl (flip (:)) [] ------------------------ Composição de Funçoes Permite a construção de funções complexas partindo de funções simples. -- A função fn fn x = ceiling (negate (tan (cos (max 50 x)))) -- Pode ser reescrita fn = ceiling . negate . tan . cos . max 50 somaDosQuadradosImpares = sum (takeWhile (<10000) (filter odd (map (^2) [1..]))) -- ou somaDosQuadradosImpares = sum . takeWhile (<10000) . filter odd . map (^2) $ [1..]
63 LUCAS BRANDAO PEREIRA Paradigmas da programação Resumo 3 Quick check Instalação do Quickcheck Edite o arquivo quickcheck.cabal e acrescente o seguinte ao final da linha build-depends: `build-depends: base >= 4.7 && <5, QuickCheck` E depois digite: `stack setup` `stack build` O QuickCheck é uma ferramenta para teste de código baseado em propriedades A biblioteca QuickCheck automatiza a geração de dados para testes e gera casos de testes progressivos, começando de casos simples até casos mais complexos em busca de erros Se der All good, está ok! Mas não significa que uma conjectura está provada, apenas que os testes passaram. Funções de propriedades Junto do quickcheck, utilizamos funções de propriedades, que nos auxiliam a testar se a solução esta correta Nessas funções propriedades, podemos colocar condições para a execução, assim descartando casos de teste indevidos ex: `prop_minimum xs = not (null xs) ==> head (qsort xs) == minimum xs` QuickCheckWith Usado quando se quer usar argumentos ex: quickCheckWith stdArgs {maxSuccess = 5000} prop_collatz (seta o numero de testes desejado) Funções como tipos Em Haskell, podemos pensar em uma função como um tipo de dado Basicamente toda função é uma função de um único argumento, onde esse argumento pode ser outra função Aplicação parcial Aplica-se alguns argumentos previamente deixando outros para serem aplicados arbitrariamente Funções de alta ordem São funções que recebem outras funções como parâmetro ou que devolvem uma função Map Uma função que transforma uma lista do tipo a para o tipo b utilizando uma função f :: a -> b Filter Utilizado junto do map, insere uma condição ao mapear uma lista, filtrando-a Entre outras funções de alta ordem que podem ser utilizadas para nos auxiliar all even takewhile any dropwhile foldr foldl
65 LUCAS DAVID VADILHO # Resumo Semana 3 ## Testes de Propriedades - Quickcheck Definimos propriedades desejadas pelo algorítmo e casos de teste automáticos e aleatórios são criados automaticamente. No `.cabal`: - `build-depends: QuickCheck` - `import Test.QuickCheck` - Tipo de return de `quickCheck`: `Property` - Quickcheck tem alguns tipos, ex.: `NonNegative`, `Positive`, para auxiliar nos testes ## Funções de Alta Ordem Funções que recebem funções como argumento ou que retornam função - Aplicação parcial: podemos obter uma função ao aplicar a função em apenas algunns de seus parâmetros - Podemos omitir argumentos caso eles aparecam apenas no fim da linha ### Map Captura o padrão `[f x | x <- xs]` ```haskell map' :: (a -> b) -> [a] [b] map' f [] = [] map' f (x:xs) = f x : map f xs ``` ### Filter Captura o padrão `[x | x <- xs, p x]` ```haskell filter' :: (a -> Bool) -> [a] -> [a] filter' p [] = [] filter' p (x:xs) | p x = x : filter' p xs | otherwise = filter' p xs ``` - Funções úteis: `$`, `all`, `any`, `takeWhile` e `dropWhile` ### Fold Padrão ```haskell f [] = v f (x:xs) = g x (f xs) ``` - Pode ser `foldr` ou `foldl` ### Composição `.` ~ Matemática
62 LUCAS SILVA AMORIM 1. QuickCheck: Ferramenta para teste de código baseado em propriedades - Teste de propriedades: Prova matematicamente que uma função está correta, testando suas propriedades, tendo como input uma grande quantidade de entradas aleatórias - A biblioteca QuickCheck automatiza a geração da massa de dados para o teste, esses casos tem complexidade progressiva. 2. Função de alta ordem - Funções como First class citizen: Funções são tratados como tipos de dados. - High Order Functions: Funções que recebem funções como parametro OU retornam funções - Partial: É possível aplicar funções parcialmente funções, pré definindo um ou mais paramentros. O retorno de um partial, é uma função que recebe menos argumentos que a original (já que alguns deles foram pré definidos). Exemplo: soma3 = (+ 3) -- Retorna uma função \x -> x, tal que, adiciona em 3 o parametro x - Map: Recebe uma função f: [a] -> [b] e uma lista [a], e aplica f a cada elemento de [a], a fim de retornar a lista [b] - Filter: Recebe um predicado p: a -> Bool e uma lista [b], e filtra todos os valores de [b] que nâo estão de acordo com o predicado p. - Foldr: Recebe f: \a b -> b, [a], b. Onde: b = valor inicial do "acumulador" f = função aplicada entre os items da coleção [a] Exemplo: foldr (+) 0 [1, 2, 3] -- 1 + (2 + (3 + 0)) *Obs: Similar ao reduce em outras linguagens - Foldl: Similar a foldl, mas aplica a função nos items da collections na ordem inversa - Composição de funções: Permite realizar a operação matemática de composição de funções, a partir do operador "." Exemplo: f . g = \x -> f (g x)
66 LUCAS YUDI FUKAZAWA CASSIN Aula 3 QuickCheck Testes de unidade Define-se propriedades do algoritmo, então realiza testes aleatórios Ex.: Para um algoritmo de ordenação, testa-se a propriedade da idempotencia Propriedade: prop xs = algoritmo (algoritmo xs) == algoritmo xs QuickCheck para gerar casos aleatórios quickCheck prop Pode-se especificar os testes para o quickCheck, commo definir o tipo de entrada (quickCheck (prop :: [Int]-> Bool)) Como não permitir listas vazias (prop xs = not (null xs) ==> ...). Nesse caso a assinatura da função passa a utilizar 'Property' Funções de alta ordem São funções que ou recebem outras funções como argumento, ou retornam outras funções ou ambos Aplicações parciais Deixa alguns argumentos livres para serem aplicados depois Ex.: dobra = (*2) == dobra x = (*2) x Função map => Aplica aos elementos de uma lista a função passada Função filter => Aplica a função passada a todos os elementos de uma lista, caso o resultado da função seja verdadeiro o elemento estará na nova lista, caso o contrário, não. Função $ => Recebe uma função e um parâmetro dessa função e o aplica na função ((a -> b) -> a -> b). all, any, takeWhile, dropWhile fold foldl => Recebe uma lista, um valor inicial e um predicado. Aplica aos elementos dessa lista o predicado, até o final (avaliação preguiçosa -> até onde for necessário) (((z `f` x3) `f` x2) `f` x1) Repare que é aplicado da esquerda para a direita. Foldr é o contrário, da direita para a esquerda Predicado para foldr => \elemento acumulador -> ... Predicado para foldl => \acumulador elemento -> ... Composição de função Assim como na matemática podemos compor funções Ex.: f . g . h . i x == (f (g (h (i x))))
55 LUCAS ZOCCHIO O QuickCheck é uma ferramenta de teste de código baseada em propriedades. Cria-se uma propriedade (uma função que retorna um booleano) e o QuickCheck gera uma série de casos aleatórios de teste. Com essa biblioteca também é possível definir os tipos dos dados de entrada e estabelecer parâmetros adicionais de teste, como o número de casos requerido. Funções de alta ordem são funções que recebem funções como argumento ou retornam funções. Com esse tipo de função é possível aumentar o poder de expressividade da linguagem. Exemplos desse tipo de função já implementados em Haskell são "map","filter","any","all","takeWhile" e "dropWhile". Com essas funções é possível reescrever expressões de maneira mais simplificada e compreensível. Algumas funções recursivas com um caso base podem ser simplificadas com o uso de "foldr", que aplica recursivamente uma função a cada elemento de uma lista. "foldr (+) 0 [1,2,3]", por exemplo, faz a operação "(1 + (2 + (3 + 0)))", portanto aplica a função passada em cada elemento recursivamente e termina no caso base. Há a versão "foldl" que faz a aplicação no sentido inverso e a "foldl'" que evita o estouro de pilha de recursão. O operador "." permite a composição de funções, como em "f . g", aplicando a função "f" após a aplicação de "g". Este operador pode ser usado no lugar ou junto do "$" (pipe), que permite concatenar a aplicação de funções sem o uso dos parênteses.
67 LUCCA IANAGUIVARA KISANUCKI QuickCheck: teste de código baseados em propriedades Define a propriedade do algoritmo e depois gera automáticamente e aleatoriamente casos de teste Recebe uma função como argumento: QuickCheck (prop_length :: [Int] -> Bool) Pode definir uma função/propriedade como: prop_length :: Ord a => [a] -> Bool prop_length xs = length (qsort xs) == length xs Passar no QuickCheck não significa que a propriedade tenha sido provada. Funções de alta ordem É possível passar funções como argumento: duasVezes :: (a -> a) -> a -> a Aplicação parcial Se a função tiver um ou mais argumento função é possível usar a aplicação Parcial Ex: dobra = (*2) Função Alta Ordem para Lista: [f x | x <- xs] map f xs = [f x | x <- xs] Função Filter para usar um predicado em lista: Filter: [x | x <- [1..10], even x] Filter e Maps são usados em conjutos muitas vezes: somaQuadPares ns = sum [n^2 | n <- ns, even n] Funções Uteis: all even [2,4,6,8] any odd [2,4,6,8] takeWhile even [2,4,6,7,8] dropWhile even [2,4,6,7,8] Podemos usar o operador pipe($) em vez de parenteses: somaQuadPares = sum $ map (^2) $ filter even Função foldr ela dobra a lista aplicando a função f em cada elemento da lista e um resultado parcial sum = foldr (+) 0 product = foldr (*) 1 Função foldl foldl :: (a -> b -> a) -> a -> [b] -> a foldl f v [] = v foldl f v (x:xs) = foldl f (f v x) xs Algumas regras: Se lista infinita: foldr Se operador pode gerar cc: foldr Else: foldl Se faz sentido uma lista invertida: foldl Composição de funções Na matematica f ∘ g, em haskell temos . fn = ceiling . negate . tan . cos . max 50
68 LUIZ FELIPE LEAL GOMES AZZOLINI
69 MARCELO CECILIO FAGUNDES DA SILVA FILHO A biblioteca quickcheck é usada para fazer testes de funções no Haskell. Com ela é possível gerar valores aleatórios, passando de menos para mais complexos. Para fazer isso é gerado uma função que retorna um booleano para verificar a veracidade de uma propriedade esperada de determinada função. Se a função retornar verdadeiro, o teste irá passar, se não o teste falha. Após a primeira falha os testes param. O padrão são 100 testes, porém é possível alterar esse valor. No haskell é possível passar como parâmetros de uma função outra função. Para especificar o tipo de entrada ou saída como um função basta usar os parentheses e determinar o tipo da função (Exemplo: (Int -> Int)). Essas funções são chamadas de funções de alta ordem. Algumas funções de alta ordem foram apresentadas durante a aula. Entre elas estava: Função map: dada uma função e uma lista, retorna outra lista de mesmo tamanho, porém com o valor retornado da função passada para cada elemento da lista. Função filter: dada uma função que retorna o booleano e uma lista, retorna uma lista sem os valores cuja a função retorna falso. Funções foldr e foldl: são funções que aplicam uma função entre os elementos da lista de dois em dois, e troca o valor [] por um valor passado. A diferença entre as duas é a ordem em que as operações são feitas. Por exemplo dado uma lista [1,2,3], uma função f e valor [] como 0, a função foldr faria 1 `f` (2 `f` (3 `f` 0)) equanto foldl faria ((0 `f` 1) `f` 2) `f` 3. A recomendação é usar foldr quando a lista for infinita, ou operador utilizado pode gerar curto-circuito e foldl se a lista for finita e fizer sentido usar a lista invertida.
80 MARIANA MIWA OKUMA MIYASHIRO Quickcheck - realiza testes baseados em propriedades - princípios: definir propriedade do algoritmo gerar testes automaticamente - teste feito com: quickCheck <propriedade> - Alterar número de testes: quickCheckWith stdArgs {maxSuccess = 1000} <prop> - Usar modificadores (NonNegative, Positive) Ex1: num algoritmo de ordenação - criando o algoritmo quicksort (com um pequeno erro) testamos o propriedade idempotencia testamos propriedade tamanho (falhou aqui, pois não considerava elementos iguais) - quicksort com filter: testamos propriedade que o primeiro elemento é o menor e falhou -> corrigimos usando operador ==> (implicação) testando com modelo (algoritmo que cumpre mesma tarefa e está correto) Ex2: testando paridade testamos função par verificando a propriedade de alternância par e ímpar pode-se testar a função ímpar verificando se quando par, não é ímpar Ex3: testando fatorial testamos se fatorial de n+1 é igual a fatorial de n vezes n+1, mas falhou por não contemplar 0 e negativos podemos usar ⇒ como anteriormente, mas também podemos usar modificador NonNegative Conjectura de Collatz : Sequência de operações que sempre alcança 1 para qualquer número testamos saída (utilizamos Positive n na propriedade) Funções de alta ordem Funções como tipos: elas podem ser argumento de entrada/saída Aplicação parcial (para funções com mais de um argumento): reescrever a função explicitando os parênteses nos tipos Funções de alta ordem: recebem uma ou mais funções como argumento ou devolvem uma função, permitem aumentar expressividade Listas: - função map e filter podem receber outras funções como argumento - operador $: para remover os parênteses - outras funções de alta ordem: all, any, takeWhile, dropWhile Função foldr: dobra lista aplicando função em cada elemento Função foldl: versão caudal de foldr Ambas podem ser usadas para criar outras funções: product = foldl (*) 1 Foldr x Foldl: - lista infinita: foldr - operador que gera curto-circuito: foldr - lista finita e operador não curto-circuito: foldl - lista invertível: foldl Composição de funções: operador (.) - associativa - elemento neutro: id
71 MATHEUS ALEXANDRE DE SENA
70 MATHEUS DA COSTA BAIO QuickCheck Ferramenta para teste de código. Define-se a propriedade do algoritmo a ser testado e depois há o mecanismo de testes que gera testes automáticos e testes aleatórios. Parecido com testes unitários. Primeiro passo é importar o Test.QuickCheck. Após isso criam-se as propriedades. Depois é só chamar a função quickCheck para cada propriedade. Funções de Alta Ordem Funções que recebem outras funções como argumento, funções que retornam outras funções ou funções que recebem e retornam funções. Map -> retorna os elementos da lista aplicados à uma segunda função Filter -> retorna os elementos da lista tal que obdeçam a um predicado $ -> Operador PIPE -> permite eliminar os parênteses pois seguem precedências All, Any, takeWhile e dropWhile Foldr -> Função que percorre a lista aplicando uma função no último elemento em relação ao valor padrão, reaplicando a função utilizando o resultado dessa primeira aplicação em relação ao penúltimo elemento e assim sucessivamente até o primeiro elemento. Foldl -> Função parecida com o Foldr, porém realiza a inversão da lista antes de aplicar as funções. O ideal é utilizar o Foldl’ que força a avaliação em cada passo da implementação. Se a lista pode ser infinita ou causar curto circuito, utilizar foldr Flip -> Inverte a lista Composição de funções. Operador (.) Tal que: f . g = \x -> f (g x) Também é útil para reduzir parênteses. Funciona da mesma forma que a composição em matemática.
73 MIGUEL MIRA FONSECA Uma forma de testar um programa é fazer testes de entrada e saída, de tal modo a verificar se dado uma entrada X o programa retorna uma saída Y. Em Haskell temos a biblioteca QuickCheck, onde a syntax quickCheck prop, roda a função a ser testada prop com um conjunto de entradas X e comparar a saída da função com valores Y esperados. Em Haskell temos o que é chamado funções de alta ordem, que seria funções que recebem uma função como parâmetro ou retornam uma função. Como exemplos temos a função map que aplica uma função a uma lista: map (\x -> x * x) [1, 2, 3] => [1, 4, 9]. E a função filter que filtram uma lista com base em uma função predicado: filter (\x -> x > 2) [1, 2, 3] => [3]. As funções foldr e foldl permitem agregar os valores de uma lista a partir da aplicação de uma função f a direita ou a esquerda da lista, respectivamente. Se a função f for associativa, então foldr e foldl apresentam o mesmo resultado. Também é recomendado usar a função foldl’ ao invés da função foldl, visto que a primeira faz uma avalição estrita, evitando um possível estouro da pilha do programa. Uma forma de evitar o uso dos parênteses para fazer composição de funções é usar o operador (.) ou o operador ($) que permite melhorar a legibilidade do código.
74 MURILO GUIMARÃES BALLE
77 NATALIA LEITE VARES DE SOUZA QUICKCHECK QuickCheck são testes baseados em propriedades, assim são complementares aos testes baseados em exemplos. Ao testar um algoritmo de ordenação, por exemplo, o QuickCheck espera que as seguintes propriedades sejam satisfeitas: - A lista de saída está ordenada - A lista de saída tem o mesmo tamanho da lista de entrada - A lista de saída contém os mesmos elementos da lista de entrada FUNÇÕES DE ALTA ORDEM No Haskell, funções podem ser utilizadas como argumento de entrada de outras funções, transformando as funções em um tipo de dado. Funções de alta ordem são funções que recebem outras funções como argumento ou devolvem uma função em suas saídas. Funções de alta ordem para listas: - Função map: Uma função que transforma uma lista do tipo a para o tipo b utilizando uma função; - Função filter: devolve uma lista de todos os valores cujo predicado p de x é verdadeiro; Para os dois casos (map e filter) podem ser utilizadas funções parciais. As funções map e filter podem ser utilizados em conjunto. - Operador pipe ($): é utilizado para separar as aplicações das funções e remover os parênteses - Outras funções: all (retorna verdadeiro se toda a lista satisfaz a função), any (retorna verdadeiro caso algum item satisfaça a função), takeWhile (mantem os elementos que satisfazem a função), dropWhile (remove os elementos que satisfazem a função) FOLDING Dobra a lista aplicando a função f em cada elemento da lista e um resultado parcial. Função foldr: percorre lista da direita para a esquerda, útil em listas infinitas Função foldl: percorre lista da esquerda para a direita, útil em listas finitas COMPOSIÇÃO DE FUNÇÕES No Haskell, podemos utilizar o conceito matemático de composição de funções, permitindo a aplicação de uma função sobre outra. Para isso é utilizado o operador (.)
76 NATALIA REGINA COSTANZI
75 NATHALIA CORREA DOS SANTOS Nessa semana aprendemos a utilizar a biblioteca QuickCheck, uma biblioteca que permite que realizemos testes unitários em nossos códigos, ou seja, testarmos algumas propriedades em nossos códigos e validarmos se o nosso código retorna a saida esperada de acordo com algumas entradas pré definidas. Além disso, vimos tambem funções de alta ordem. As funções de alta ordem recebem ou retornam funções (ou ambas). Em haskell podemos considerar funções como um tipo de variável. Aprendemos como definir e utilizar duas funções bem importantes para desenvolvimento de códigos, a função Map e Filter. A função Map é uma função que transforma uma lista a em uma lista b utilizando uma função F. f :: a -> b. Ou seja, aplicamos F em todos os elementos de a, transformando em b. Já a função Filter devolve uma lista cujo o predicado F de x devolve True, realizando assim uma filtragem dos elementos da lista. Outras funções bastante uteis são: all, any, takeWhile e dropWhile.
85 PAULO GABRIEL MASSA
81 PAULO HENRIQUE EIJI HAYASHIDA Com a biblioteca QuickCheck pode-se testar um programa, através de testes aleatórios bem estruturados, onde os primeiros testes são mais básicos e sua complexidade vai aumentando a medida que aumenta-se a quantidade de testes. A importação da biblioteca pode ser feita com o comando import Test.QuickCheck. Para o teste da função qsort pode-se testar algumas propriedades como: idempotencia, ordenar duas vezes é igual a ordenar uma vez; tamanho, tamanho da lista ordenada é igual ao tamanho da lista original; primeiro elemento tem que ser o minimo da lista original. Funções de Alta Ordem, recebem uma função como parametro ou retornam uma função. Aplicação parcial, aplica um dos argumentos e deixa os outros argumentos para serem definidos posteriormente. Numa função se a variável que aparece no final da expressão, ela pode ser omitida, mantendo sua funcionalidade. Algumas funções de alta ordem são: map, recebe e aplica uma função em uma lista; filter, dadas condições pode retornar uma lista menor ou igual a original; all, caso todos os elementos de uma lista atendam a um predicado, retorna verdadeiro; any, caso algum elemento da lista cumpra uma condição, retorna verdadeiro; takewhile, pega elementos enquanto atender a uma condição; dropwhile, retira elementos de uma lista até que uma condição seja atingida. Fold recebe uma função, um valor padrão e uma lista, para retornar um resultado do mesmo tipo do valor padrão.
84 PEDRO ANTUNES NEGRÃO Na terceira semana de aula foram apresentados diversas ferramentas que visam nos auxiliar no desenvolvimento de um programa mais eficiente e conciso, como o uso do QuickCheck, funções de alta ordem, Folding e composição de funções. Há um jargão conhecido no mundo do Haskell que diz que “se o código compilou, então está correto!”, porém, para verificar a corretude do código, é necessário realizar diversos testes. E é nisso que entra a biblioteca QuickCheck, que consegue gerar testes automáticos e aleatórios. Através da assinatura de cada função, o QuickCheck utiliza as propriedades de entrada da função e cria 100 testes por padrão, indo de casos simples até casos mais complexos. Se tudo der certo, ele retorna com uma mensagem “OK, passed 100 tests”, mas caso encontre algum erro, ele retorna a instância mais simples onde apareceu o erro. Além disso, é preciso reforçar que mesmo que o código passe em milhares de testes, não podemos afirmar com 100% de certeza que o código está correto. Sobre funções de alta ordem, são funções que recebem como argumento uma ou mais funções ou devolvem alguma função. Um exemplo é a função map, que é passado como argumento uma função e uma lista e retorna uma lista alterada pela função. Também existe o filter, que consegue filtrar elementos de uma lista. É possível simplificar a escrita do código utilizando o operador pipe, permitindo escrever em cada linha uma função que é precedido pelo operador ‘$’. Existe também as funções foldr e foldl, que são passados como argumento uma função, um valor padrão, que varia de acordo com cada problema, e uma lista (i.e. foldr (+) 0 [1..10] = soma os números de 1 a 10). Por fim, aprendemos a utilizar composição de funções, que substitui o uso excessivo de parênteses por pontos.
82 PEDRO BRAGA DOS SANTOS BACELLAR
83 PEDRO MACHADO NERY DOS SANTOS O módulo Haskell quickcheck pode ser utilizado para testes automáticos e aleatórios a partir da definição de propriedades esperadas de algoritmos. Embora a testagem não garanta a corretude de algoritmos, é um passo que permite evitar erros futuros de implementação num conjunto de entradas esperadas. Funções de alta ordem são funções que recebem funções como parâmetro ou retornam funções. São úteis na criação de funções genéricas que dependem de funções externas passadas como parâmetro. Em linguagens funcionais "Função" pode ser considerado um tipo de dado. Uma aplicação parcial é um procedimento padrão em funções de alta ordem em aplica apenas alguns argumentos e deixa outros livres, o que serve para alterar operadores. Aumentam a expressividade do código no caso de padrões recorrentes. Entre elas podemos citar takewhile, product, map e filter. Pode-se utilizar o conceito de tipos polimórficos de maneira a definir uma variável de tipo para não especificar o tipo de saída em funções de alta ordem, ou mesmo em funções que se apliquem a mais de um tipo (estrito, devido à tipagem forte do Haskell). Uma class constraint ou restrição de classe assume esse papel e permite, por exemplo, que uma função definida para o tipo Integral se aplique tanto a Int quanto a Integer. Também foram estudadas formas características de linguagens funcionais como a compreensão de listas e a recursão. No primeiro caso, uma lista é definida de forma declarativa a partir de um conjunto de partida e um predicado, enquanto que no segundo caso uma função chama a si mesma, o que pode substituir laços não presentes em linguagens funcionais. Guarded expressions podem ser utilizadas de maneira a se clarificar a recursibilidade nesses casos.
90 PEDRO REGIO SHOJI
87 PIETRO DI CONSOLO GREGORIO A biblioteca QuickCheck permite a realização de testes automáticos da corretude se baseando para isso nas propriedades (invariantes) desejadas do algoritmo. Os casos de testes gerados são progressivos, ou seja, os testes iniciais são feitos com casos simples avançando-se para casos mais complexos e, além disso, esses casos podem ser especificados, por exemplo para não serem nulos, maiores do que zero, etc. A linguagem Haskell permite que funções sejam passadas como argumentos e também retornadas por outras funções. Isso possibilita a chama aplicação parcial, na qual uma função recebe outra função que requer mais de um argumento e "fixa" alguns destes parâmetros. As funções que recebem funções como argumento ou devolvem uma função são chamadas de funções de alta ordem. Algumas funções de alta ordem são: map, a qual aplica a função passada em todos os elementos da lista; filter, a qual retorna uma lista com os valores da lista original que fazem com que a função passada retorne verdadeiro; operador pipe ($) separa as aplicações das funções, interligando a saída de uma função na entrada de outra e as funções de folding (foldr e foldl) aplicam a função recebida para combinar todos os elementos da lista recebida. O operador . é utilizado para fazer a composição de funções, aplicando a função à esquerda após a aplicação da função à direita.
16 RAFAEL BRUNO FERREIRA FIGUEIREDO Quickcheck: Forma eficiente do haskell testar códigos, quando este não é totalmente provado matematicamente. É uma ferramenta que cria casos de teste a partir de uma propriedade invariável do programa. Assim a ferramente cria testes aleatórios e verifica se o programa atende à regra. Funções de Alta ordem: São funções que recebem funções como parâmetro. Na assinatura das funções deve-se delimiar a entrada e saida da função para o compilador organizar os tipos possíveis. Map: aplica uma função em todos os elementos de uma lista. Filter: Limpa uma lista de acordo com a função (que retorna booleano) $: Facilita a alicação de funções encadeadas pra evidar usar muitos parenteses Folding: São funções de alta ordem que aplicam funções em elementos de listas 2 a 2. A foldr roda a lista do ultimo elemento para o primeiro. foldl roda do primeiro para o ultimo. foldr f [] -> (a 'f' (b 'f' (c 'f' (d 'f' e)))) foldl f [] -> ((((a 'f' b) 'f' c) 'f' d) 'f' e)
88 RAFAEL PAUWELS DE MACEDO O primeiro assunto da semana foi sobre como usar a biblioteca QuickCheck para testar com entradas aleatórias e com sentido, diferentes funções dentro do Haskell. Podemos definir funções e descrever propriedades que precisam ser válidas para que a função seja considera certa, depois aplicamos o quickCheck para validar se a propriedade é verdadeira. Uma assinatura padrão das propriedades que checamos com o quickCheck é a -> Bool, mas podemos detalhar mais os testes com tipos integrados com a biblioteca como Positive a -> Property. O outro tema, funções de alta ordem, são funções que recebem outras funções como argumento ou que retornam funções como saída. Destas funções se destacam o map, filter e foldr/foldl que respectivamente aplicam uma função f sobre todos os elementos da lista [a] retornando [b], filtram os elementos [a] com base no predicado p e retorna uma lista [a] e recebem uma lista [a] e aplicam uma função f de forma recursiva sobre a lista. Foldr por exemplo ao aplicar a função soma em [1, 2, 3] faria (1:(2:(3:[]))), substituindo : por soma. Ainda sobre o foldl nota-se a importancia de usar foldl' importado de Data.list, visto que a implementação foldl padrão pode causar estouro de pilha. Por último entramos no assunto de composição de funções, ou seja como podemos usar o . para compor funções do tipo (f . g) x = f (g x) onde a identidade e associatividade de f e g são válidas. Assim conseguimos ver formas diferentes e as vezes mais legíveis de resolver problemas dentro da linguagem.
89 RAPHAEL RAMOS DA SILVA
59 RENAN FERREIRA LIMA Durante o desenvolvimento de algoritmos é importante a realização de testes para averiguar se todas as propriedades foram corretamente implementadas. Uma forma mais automatizada de fazer isso em Haskell é utilizando a ferramenta QuickCheck, o conceito desta é baseado na definição de uma invariante para o algoritmo, em seguida a ferramenta gera casos de testes. É possível realizar milhares de casos de testes, auxiliando de forma significativa na correção de eventuais falhas. Durante a aula foi abordado como implementar esse recurso, exemplificando com alguns casos de uso como: ordenação e manipulação de vetores, uso de fatorial e aplicação da conjectura de Collatz. Em algumas dessas aplicações ocorreram falhas ao rodar o QuickCheck devido a falta de definição do domínio dos casos de testes, i.e., fatorial com entrada negativa, parâmetros de comparação divergentes, entre outros. Uma vez ajustadas as condições de testes os erros cessaram, o intuito foi demonstrar que o QuickCheck gera casos de testes progressivos dos mais simples ao mais complexo e quando ocorrem falhas, ele retorna a instância mais simples que falhou. Além do QuickCheck, também foi abordada a questão das funções de Alta Ordem e a aplicação de foldr, foldl, foldl’ em listas. Dentre os tópicos mencionados estão: a importância do uso de assinaturas para diminuir erros de implementação e favorecer a compilação; análise de diferentes funções em listas, verificando as principais diferenças de sintaxe e compilação.
91 RENAN GONCALVES MIRANDA QuickCheck O teste é uma das partes mais importantes na engenharia de software, uma das formas para realizar esses testes é verificando se as entradas e saídas atendem as propriedades do programa. Em haskell, há uma biblioteca para realizar esses tipos de testes, a QuickCheck. Essa biblioteca deve ser adicionada no arquivo cabal do projeto e importada no arquivo do código (import Test.QuickCheck). O QuickCheck gera caso de testes progressivos, passando do mais fácil ao mais difícil. Ele recebe uma função como argumento. Na biblioteca do QuickCheck temos diversos parâmetros para utilização, exemplo o maxSuccess (quickCheckWith stdArgs {maxSuccess = 1000}), que realiza o número de testes estabelecidos pelo programador. Funções de Alta Ordem Funções que podem receber outras funções como argumento ou retorna funções ou ambas as situações. Uteis para a criação de funções genéricas que dependem de funções externas que são passadas como parâmetros para a função principal. Map (mapeamento), é uma função de alta ordem que recebe uma função de a para b que recebe uma lista a e retorna um lista b, exemplo map (*2) [1, 2, 3], que pega função (*2) aplica a cada elemento da lista [1, 2, 3] , retornando o uma lista com o dobra([2, 4, 6]) os elementos [1, 2, 3]. Filter (filtragem), é uma função que recebe como primeiro argumento um filtro que retorna um booleano e aplica esse filtro na lista recebida, exemplo filter even [1 .. 10], que filtra através da função even os elementos impar da lista e os retorna. All é uma função que retorna verdade se todos os elementos da lista atender a condição estabelecida, o any se pelo menos um atender. Nas funções folds, recebemos a função o padrão e a lista. Na foldr, temos uma avaliação caudal já na foldl a avaliação começa na cabeça.
96 RENATO VINICIUS TURTIENSKI POSSA QuickCheck O haskell, por conta de ser puramente funcional, permite provar matematicamente em algumas situações que o programa está certo (através de indução) Também, o bom e velho teste de entrada e saídas das funções criadas para verificar se as soluções são as desejadas também é bem-vindo A definição de QuickCheck se dá: 1 definir uma propriedade do algoritmo que seja invariante 2 ter um mecanismo que gere automaticamente e randomicamente casos a serem testados A biblioteca QuickCheck faz o trabalho 2 para você, i.e., a geração de dados para testes (e faz outras coisas úteis também). Funções de Alta Ordem Em haskell, a gente pode imaginar que uma função seja um tipo de dado, assim como um char, ou um int, que loucura. Em consequência, considerando uma função como um tipo de dado, podemos usá-lo como argumento de entrada e saída da função(de outras ou dela mesma, só cuidado aí pra não cair num looping recursivo infinito) Composição de funções: Temos na matemática, f o g, definica como a função composição z(x) de f em g(x), i.e., f(g(x)), o no haskell temos o operardor (.), esse carinha aí faz esse papel no nossa nova linguagem de programação favorita.
95 TAMIRES CHRISTYNE DA SILVA
98 VICTOR LOURENCO BORGES QuickCheck - biblioteca para haskell para facilitar testes de funções - Criamos propriedades a serem testadas (ordenação, tamanho), e especificamos o tipo de entradas que queremos. A lib irá gerar entradas de complexidade variada para validar a propriedade em questão Funções de alta ordem - podemos omitir um parâmetro da função desde que ele seja chamado no final da aplicação - recebem e/ou retornam outras funções - map: recebe uma função e uma lista. Aplica a função para cada item da lista - filter: recebe uma condição e uma lista. Aplica a condição para cada item, e retorna os que passaram - foldr: "dobra" a lista aplicando uma função de 2 args,um valor base e uma lista: (a0 f (a1 f (a2 f 0))), e retornando um valor "agregado" da operação. - foldl: Igual a foldr, mas inverte a ordem das chamadas: (0 f a2) f a1). Quando a operação for associativa (a f b = b f a) terá o mesmo resultado da R. - Em termos de desempenho, se a lista passada pode ser infinita, ou pode haver curto circuito (break) usar foldr. - composição: podemos reescrever f ( g ( h x ) como (f . g . h) x
99 VINICIUS DE OLIVEIRA CAMPOS DOS REIS
100 VINICIUS LOURENCO DA SILVA Para testarmos a corretude de um código, o haskell disponibiliza a biblioteca QuickCheck, que permite a realização de testes a partir de propriedades definidas que se deseja ter dentro do seu código. Para utilizar o quickcheck deve-se adicionar essa biblioteca no arquivo cabal do projeto, para que ele baixe a biblioteca. As funções de alta ordem são resumidamente funções que retornam ou recebem outras funções como parâmetro. * A função map é uma função de alta ordem que recebe uma lista A e a transforma numa lista B utilizando uma função F sobre todos os elementos de A. * A função Filter é uma função de alta ordem que filtra elementos de uma lista com base em uma função F chamada de guards. Podemos usar as funções Map e Filter juntas, de maneira análoga ao que é realizado em compreensão de listas, por exemplo. O operador pipe "$" pode ser utilizado para melhorar a leitura do código, podendo ser utilizado para separar a aplicação de diferentes funções sem a utilização de parênteses, que podem poluir e dificultar a leitura do código. As funções foldr e foldl podem ser utilizadas para simplificar funções recursivas. A diferença entre as duas é que enquanto o foldr implementa uma recursão simples, a foldl implementa uma recursão de cauda. Quando usar foldr e foldl ? * Quando é possível causar um curto circuito, ou seja, se após a primeira avaliação já é possível retornar o valor da operação total, pode-se aproveitar da avaliação preguiçosa do haskell e, portanto deve-se escolher a foldr, do contrário pode-se usar a foldl. * Quando a lista é infinita, utilizar foldr. * Caso faça sentido trabalhar com a lista invertida, usar foldl.
0 VITOR MARINI BLASELBAUER
101 VITOR RUBENS SNIQUER LEAO MARTINS
97 VITTORIA ARIEL DOS SANTOS BOROTTO => QuickCheck Biblioteca para testes baseados em propriedades do algoritmo, utilizando inducao Propriedades de um algoritmo de ordenacao: lista de saida ordenada lista de saida mesmo tamanho que a de entrada lista de saida tem que ter os mesmo elementos gerando dados de teste automaticamente, funcao que recebe uma funcao p.e: quickCheck <function> Principios: definir uma propriedade do algoritmo que nao varie, e assim o quickCheck gera automaticamente os casos de teste de forma aleatoria Metodo Complementar aos testes unitarios Essa biblioteca gera casos progressivos, do mais simples ao complexo. Podemos omitir o argumento de entrada se ele for o ultimo ex: quadruplica x = duasVezes (*2) x quadruplica = duasVezes (*2) => Funçōes de Alta Ordem [map, filter, all, any, takeWhile, dropWhile] Recebem outras funcoes como argumento, e/ou retornam funcoes Funcao -> considerada um tipo de dado em haskell Uso: permitem aumentar a expressividade dos codigos, principalmente com padroes recorrentes: -- para cada elemento da lista aplicar uma funcao [f x | x <- xs] Aplicacao Parcial: pode ser utilizado em qualquer função com mais do que um argumento, otimizando a sintaxe. Exemplos de Funcoes de Alta Ordem para listas: map filter Map e Filter normalmente usados em conjuntos Chamado de map: funcao que recebe uma funcao de a->b e uma lista de [a] retornando uma lista [b] all retorna false ou verdadeiro dependendo dos elementos da lista => Outras Funcoes de Alta Ordem Folding: ela dobra a lista apos aplicar uma função f em cada elemento. 1. Foldr 2. Foldl => Composicao de Funcoes: como ja estudado na matematica, uma funcao de funcao: f(g(x)), no haskell utiliza-se o operador: (.), ou seja: f . g
102 WALTER OSCAR TRUJILO
103 WESLEY AXEL DE BARROS Para esta semana 03, tivemos dois topicos importantes para o estudo de Haskell na disciplina de Paradigmas de Programação. O estudo do QuickCheck, que é uma ferramenta utilizada para testar funções no código com base em propriedades definidas, permitindo automatizar estes testes, trazendo facilidade em verificar se uma função está correta em um valor x de testes que pode ser definido pelo usuario. E o estudo de Funções de Alta Ordem, que são funções que recebem uma ou mais funções como argumentos ou retornam uma função como valor. Utilizamos funções de alta ordem quando queremos, simplificar funções recorrentes no código. Estudamos as funções "map", "filter", que com base em uma lista, aplicam uma função f ou filtram a lista com base numa função/argumento f. Estudamos também a utilizar o operador pipe "$" na hora de escrever as funções de alta ordem para melhor indentação. Verificamos as funções, foldr, foldl e foldl1, que são funções que dobram a lista conforme uma função f. Aplicando recursivamente uma função f nos elementos. Mudando apenas por onde começar a aplicar a função na lista. E aprendemos também diferentes tipos de composição de funções.
104 WESLEY BATISTA SOARES QuickCheck serve para testar códigos em Haskell (baseado em propriedades, como tamanho de uma lista ou se está ordenada), ele gera testes automaticamente baseado na propriedade. Executa os casos de teste de forma preguiçosa, caso um teste falhe (de menor complexidade), ele já para os testes retornando a caso que falhou. Podemos restringir os testes com propriedades/parâmetros e solicitar quantos testes quisermos também. Em Funções de Alta Ordem, podemos definir funções como tipo, e assim, passar funções como parâmetros para outras funções. Também podemos devolver uma função como retorno. Podemos usar funções de alta ordem em listas, algumas são o map (para mapear um lista aplicando o predicado à lista), o filter (para filtrar uma lista conforme um predicado) e o fold (para reduzir uma lista, como um reduce). Também é possível termos composição de funções em Haskell, através da função ponto (.).
40 WILLIAM DE SOUZA GOMES Com a biblioteca QuickCheck é possível testar as funções a fim de verificar sua corretude. A biblioteca pode ser incluida no arquivo de extensão .cabal e depois basta importar no programa e chamar a função na qual queira testar. O programa começa com testes mais simples até os mais complexos conforme vai passando. O Quickcheck não valida a conjectura da função ele coleta evidências baseada em testes. Funções de alta ordem recebem funções como argumento ou retornam funções, são bastante úteis para criar funções genéricas que dependem de funções externas.
105 WILLIAM SENA SILVA
106 WILLIAN CORTEZ resumo semana AULA 03 Para importar uma biblioteca, deve ser inserido no arquivo .cabal, adicionado ao main e para ser testado no ambiente ghci deve ser importado novamente. A biblioteca quickCheck auxilia nos testes de funções de uma forma simplificada, e vai escalonando a sua complexidade, até 100 testes, facilitando a etapa do projeto de testes. Podendo ser alterado a quantidade de testes através de argumentos, modificando o maxSuceess, ou outros cenários. Funções de alta ordem - toda função que recebe uma ou mais funções, como argumento é chamada do tipo alta ordem, permitindo aumentar a expressividade dos algoritmos. Exemplo: [f x | x <- xs] "Dado uma lista xs para cada elemento dela, vou aplicar a seguinte função f" função map: map' :: (a -> b) -> [a] -> [b] map' f xs = [f x | x <- xs] map' f [] = [] "função map recursivo" map' f (x:xs) = f x : map f xs função filter: filter' :: (a -> Bool) -> [a] -> [a] filter' p xs = [x | x <- xs, p x] filter' p [] = [] "função filter recursiva" filter' p (x:xs) | p x : x : filter' p xs | otherwise = filter' p xs função foldr foldr :: (a -> b -> b) -> b -> [a] -> b foldr f v [] = v foldr f v (x:xs) = f x (foldr f v xs)
27 francesquini