UFOP DECOM 2011/2
Prof. José Romildo Malaquias
BCC222 – Programação Funcional
Lista de Exercícios 11
Avaliação lazy
Exercício 1
Expressões regulares
Expressões regulares são padrões que podem ser usados para descrever
conjuntos de cadeias de caractres de vários formas, como por exemplo:
• os identificadores de uma linguagem de programação: cadeias de caracteres
alfanuméricos que começam com um caracter alfanumérico
• os números inteiros e reais de uma dada linguagem de programação
Existem cinco formas de expressões regulares:
x
(r1 |r2 )
(r1 r2 )
(r)?
casa com a cadeia vazia
casa com o caracter x
casa com uma cadeia s se r1 casa com s, ou r2 casa com s
casa com uma cadeia s se s pode se dividida em duas subcadeias s1 e s2
de forma que s = s1 + +s2 , e r1 casa com s1 e r2 casa com s2
casa com uma cadeia s se s pode se dividida em duas ou mais subcadeias
s = s1 + + · · · + +sn , cada uma das quais casa com r
1. Definir um tipo algébrico RegExp para representar expressões regulares. Utilizar operadores binários para representar (r1 |r2 ) e (r1 r2 ).
2. Defina uma função enumerate :: RegExp -> [String], que recebe uma expressão regular e resulta na lista de todas as cadeias com as quais a expressão regular casa.
Estas listas podem ser infinitas, mas como Haskell usa avaliação lazy, isto
não é um problema.
Para combinar duas listas infinitas, defina a função interleave :: [a] > [a] -> [a], que constrói o resultado pegando alternado valores de cada
uma das listas dadas como argumentos.
Para gerar todas as combinações de elementos de duas listas, defina a função cartesian :: [[a]] -> [[a]] -> [[a]], que concatena ele mentos da
primeira lista com elementos da segunda lista de todas as formas possíveis e
intercalando os elementos.
1