Consider the task of determining the positions of the First symbols in a regular expression. We can solve this problem with three helper functions. The first helper countCh counts the number of Ch symbols in an RE. The second helpr matchesEmpty determines whether an RE can match the empty string. The third firstWithIndex determines the first symbols counting from a given index position.

data RE = Epsilon | Ch Char | Seq RE RE | Alt RE RE | Star RE | Group RE deriving Show

countCh Epsilon = 0
countCh (Ch c) = 1
countCh (Seq r1 r2) = (countCh r1) + (countCh r2)
countCh (Alt r1 r2) = (countCh r1) + (countCh r2)
countCh (Star r) = countCh r
countCh (Group r) = countCh r

matchesEmpty Epsilon = True
matchesEmpty (Ch c) = False
matchesEmpty (Seq r1 r2) = (matchesEmpty r1) && (matchesEmpty r2)
matchesEmpty (Alt r1 r2) = (matchesEmpty r1) || (matchesEmpty r2)
matchesEmpty (Star r) = True
matchesEmpty (Group r) = matchesEmpty r

firstWithIndex i Epsilon = []
firstWithIndex i (Ch c) = [i]
firstWithIndex i (Seq r1 r2)
   | matchesEmpty r1 = (firstWithIndex i r1) ++ (firstWithIndex (i + countCh r1) r2)
   | otherwise       = (firstWithIndex i r1)
firstWithIndex i (Alt r1 r2) = (firstWithIndex i r1) ++ (firstWithIndex (i + countCh r1) r2)
firstWithIndex i (Star r) = firstWithIndex i r
firstWithIndex i (Group r) = firstWithIndex i r

firstSym r = firstWithIndex 1 r