It's interesting that most of the Haskell solutions are somewhat similar

Well, I didn't read the instructions that carefully and I was a bit surprised. Perhaps there are others like me who already have an intuition of how regular expressions work, and who would be confused by the unusual precendences given in the instructions.

I would expect "ab|c" to be Or (Str [Normal 'a', Normal 'b']) (Normal 'c') and not `Str [Normal 'a', Or (Normal 'b') (Normal 'c')]