Why would immutability guarantee no cycles? Here is a line of valid haskell:

        star e = let (sp, a) = (Split a e, atom sp) in sp

EDIT: I guess I should probably explain it: star is a function that takes an expression "e" and returns the value "sp" which is "Split a e" where "a" is the results of calling the "atom" function on "sp". This is creating a representation of a regex star operator. Note that the tuple defined in the let definition is only to define a name for the two values of the tuple so that they can refer to each other.