“Necesito ayuda para resolver la función Haskell de manipulación de regex”.
La definición
hs
firsts :: RE sym -> [sym]
firsts = undefined
Los datos de RE
hs
data RE sym -- sym es el tipo de símbolos del alfabeto
= RSym sym -- coincide con un solo símbolo
| REps -- coincide con la cadena vacía
| RZero -- no coincide con nada
| RStar (RE sym) -- elección
| RPlus (RE sym) -- concatenación
| RAlt (RE sym) (RE sym) -- repetición 0+
| RSeq (RE sym) (RE sym) -- repetición 1+
deriving (Show)
El alfabeto utilizado en las expresiones regulares
hs
data Alphabet = A | B | C deriving (Show, Eq)
firsts re devuelve una lista que contiene cada símbolo que ocurre primero en alguna cadena del lenguaje para re.
Por ejemplo, si re representa “A(C|B)|BC”, entonces las cadenas en su lenguaje son AB, AC y BC. En este caso, firsts re podría devolver [A,B].
Observe que la firma del tipo no incluye Eq sym o Ord sym. Esto significa que su código no podrá ordenar ni eliminar duplicados de la lista de símbolos que devuelve.
Los requisitos que su código debe cumplir son:
1. la lista devuelta debe ser finita (¡incluso si el lenguaje es infinito!)
2. cada símbolo en la lista debe ser el primer símbolo en alguna cadena del lenguaje
3. para cada cadena del lenguaje, su primer símbolo debe aparecer en la lista
Los símbolos individuales pueden aparecer en cualquier orden y pueden ser duplicados cualquier número finito de veces.
davy.ai
Explicación de la función ‘firsts’ en Haskell
La función ‘firsts’ toma una expresión regular (‘RE’) como entrada y devuelve una lista de símbolos de alfabeto (‘sym’). La expresión regular incluye diferentes tipos de patrones de coincidencia, como la coincidencia con un solo símbolo (‘RSym sym’), una cadena vacía (‘REps’) o nada (‘RZero’), entre otros. Además, el alfabeto utilizado en la expresión regular está definido como ‘Alphabet = A | B | C’.
El objetivo principal de la función ‘firsts’ es extraer la lista de símbolos que ocurren primero en alguna cadena dentro del lenguaje de la expresión regular. Por ejemplo, si la expresión regular representa “A(C|B)|BC”, entonces el lenguaje de la expresión regular incluye las cadenas “AB”, “AC” y “BC”. La función ‘firsts’ extraería los símbolos “A” y “B”, ya que ambos ocurren primero en alguna cadena dentro del lenguaje de la expresión regular.
Es importante tener en cuenta que la lista devuelta por la función ‘firsts’ debe ser finita, incluso si el lenguaje de la expresión regular es infinito. Además, cada símbolo en la lista debe ser el primer símbolo en alguna cadena dentro del lenguaje y para cada cadena en el lenguaje, su primer símbolo debe aparecer en la lista. Sin embargo, la función no puede ordenar ni eliminar duplicados de la lista de símbolos que devuelve, ya que la firma de tipo no incluye ‘Eq sym’ o ‘Ord sym’.