Monoidal tree interview in Haskell
Welcome! Here are my thoughts what could be improved:


For top-level declarations, always do include types. I'm pretty sure in a few weeks it'll be difficult to realize what

mapTuple = join (***)


means without knowing that it's type is

mapTupple :: (b' -&gt; c') -&gt; (b', b') -&gt; (c', c')


Also as you don't need arrows anywhere else, it makes sense to specialize the type to avoid accidental errors and get nicer error messages.
I'd put a newline betweek 'data...' and 'label'. Keeping consistent style helps readability very much.
You don't need to nest 'let' expressions. You can write just

let midpoint = Seq.length s `div` 2
    subseq = Seq.splitAt midpoint s
    ...
in Branch label subtrees

Instead of creating a sequence and then converting it into a balanced tree, you can convert a list directly into a balanced tree in O(n). This is a nice exercise on its own!
Use Haddock markup in comments, you can then generate nice documentation very easily.

  Algorithm runs in Θ(n log n) which I believe is optimal. 


Are you sure?