betterHand function returns a Hand, so it is not clear what to do if hands are equal.

It's lazier; it works when is is infinite. I suspect (though I don't exactly recall) that's why I wrote it that way in the first place. Of course, the requirement to return the lexicographically least solution prevents doing anything useful with infinite lists, so it got transformed into this solution.

If you're bothered by the possibility of creating nested loops, you could manually fuse it:

indices is = unfoldr go (0, is)
  where go (_, []) = Nothing
        go (a, _:bs) = Just (a, (a+1,bs))

But I don't think that is necessary.

The real problem here is the use of (!!), turning what should be a quadratic algorithm cubic.

OMG. indices is a very brutal way to get N sequential integers. Consider using

let n = length is
    indices = [0..n]

Please add more complex tests - as valid as invalid too. Current tests are VERY simple!

Actually, tests for equility need to be added:

Normal 'x' == Normal 'x'
Normal 'x' /= Any
...

This will detect such cheaters

Choose any your own variant, but write it clearly in kata task conditions.

I've added some invalid tests, one question is what to do with ""? Is it Nothing or is it Just (Str [])? Now I test for Nothing (as that's what my solution does :D) But I can change that.. What do you think?

well spotted. thanks. Fixed.

cheers, I will add some invalid tests

"(a|b)*"  -> ZeroOrMore (Str [ Or (Normal 'a') (Normal 'b') ] )

at the end of second paragraph examples should be

"(a|b)*"  -> ZeroOrMore (Or (Normal 'a') (Normal 'b') )