Disjoint set in Haskell
Naming

While it's usually not a big deal to have names like d and d' flying around, seeing d''' made me wonder: is there no better name for that?

Indentation

data Action
  = Add Int
        Int
  | Check Int
          Int
  deriving (Show, Read)


That seems.. unusal. Why is the second Int on a new line? Nice of you to seperate the constructors to their own lines, though.

data Action
    = Add Int Int
    | Check Int Int
    deriving (Show, Read)


Handling errors

You've said your error handling is atrocious. I wouldn't really call it that, because it simply does not exist. You never take any action on Nothing, which means the repl will stop as soon as something bad happens.

The glaring problem: The rat's tail

repl :: DisjointSet Int -&gt; IO ()
repl d = do
  line &lt;- getLine
  case (Read.readMaybe line) of
    Just action -&gt;
      case action of
        Add k1 k2 -&gt;
          case (merge k1 k2 d) of
            Just d' -&gt; repl d'
        Check k1 k2 -&gt;
          case (find k1 d) of
            Just (k1', d') -&gt;
              case (find k2 d') of
                Just (k2', d'') -&gt; do
                  if (k1' == k2')
                    then putStrLn "Together"
                    else putStrLn "Apart"
                  repl d''


Having lots of nested cases always yells: refactor me. 

Let's follow the flow of repl for a second...

Get a line and read it to an Action. If that is possible, diverge on the type of action: if it's an Add, merge them and repeat on success. If it's a Check, find the first one. If it's found, find the second one. If that is found, show whether they are together or apart and repeat.

There are lots of actions and processes stuffed together here, so let's help the poor repl breathe by splitting it up into pieces.

Reading input

What should happen when the user types garbage, such as "Bananas are a fruit"? Maybe we should just try again... so let's do that.

getAction :: IO Action
getAction = case Read.readMaybe &lt;$&gt; getLine of
    Just action -&gt; return action
    Nothing     -&gt; putStrLn "Oops, try again..." &gt;&gt; getAction


We read a line of user input and Read.readMaybe it to form an Action (&lt;$&gt; is just the infix operator for fmap). If that succeeds, horray, we got ourselves an Action! If not.. say something to the user and try again.

Executing the action

What should happen on an error here? That is your decision to make. If anything goes wrong, I'll just return the old DisjointSet and do nothing. I like to indent the case-statements based on the indentation level on the case itself, so let's do that.

execute :: DisjointSet Int -&gt; Action -&gt; IO (DisjointSet Int)
execute d (Add a b)   = return $ maybe d id (merge a b d)
execute d (Check a b) = case find a d of
                          Nothing       -&gt; return d
                          Just (a', d') -&gt; case find b d' of
                                             Nothing         -&gt; return d
                                             Just (b', d'') -&gt; if a' == b'
                                                                then putStrLn "Together" &gt;&gt; return d''
                                                                else putStrln "Apart"    &gt;&gt; return d''


(Note to Editors: The long line is on purpose)
Damn, that's still long.

Monads to the rescue!

The beauty of Maybe as a monad is that it'll stop doing whatever it does and just return Nothing once it encounters one. So let's use that!

execute :: DisjointSet Int -&gt; Action -&gt; IO (Maybe (DisjointSet Int))
execute d (Add a b)   = return $ merge a b d
execute d (Check a b) = do
    (together, d'') &lt;- (do
             (a', d')  &lt;- find a d
             (b', d'') &lt;- find b d'
             return (a' == b', d''))
    when together       (putStrLn "Together")
    when (not together) (putStrLn "Apart")
    return d''


Putting it together

Using these fancy new functions, your new repl would be:

repl :: DisjointSet Int -&gt; IO ()
repl d = getAction &gt;&gt;= execute d &gt;&gt;= \c -&gt; case c of
    Just d' -&gt; repl d'
    Nothing -&gt; return ()