Q:

Haskell IO: remove a random element from a tree

Consider the following type to represent trees:
data Tree a = Empty
            | Leaf a
            | Fork (Tree a) (Tree a)

I need help definig the function removeRandom' :: Tree a -> IO (Tree a) that receives a tree with at least a leaf and returns the result of removing a random leaf from the tree (replacing it with Empty). The exercise had a suggestion: use the function randomRIO :: Random a => (a,a) -> IO a to generate the order of the element to remove
EDIT: trying method 2 of user Thomas
removeRandom' :: Tree a -> IO (Tree a)
removeRandom' t = let lengthTree = numbelems t
                  in do x <- randomRIO (0,lengthTree -1)
                        return (remove x t)

numbelems :: Tree a -> Int
numbelems Empty = 0
numbelems Leaf x = 1
numbelems Fork l r = (numbelems l) + (numbelems r)

remove :: Int -> Tree a -> Tree a
remove _ (Leaf x) = Empty
remove n (Fork l r) = let lengthLeft = numbelems l
                      in if (n>lengthLeft) then Fork l (remove (n-lengthLeft r)
                         else Fork (remove n l) r

A:

There are 2 ways to approach this problem

Convert to a list, remove the element, and convert back to a tree.

Pros: Simple to implement, you already have toList, all you need is fromList, and you can implement your solution simply as
removeAt :: Int -> [a] -> [a]
removeAt n as = a ++ tail s where (a, s) = splitAt n

removeRandom' tree = do
    element <- randomRIO (0, length tree)
    return $ fromList $ removeAt element $ toList tree

Cons: This method is not "True" to the problem statement removing a random leaf from the tree (replacing it with Empty) and will likely give you a brand new tree with no Empty values in it. I have only provided this as an option in an attempt to show where your toList method ends up.

Descend into the tree, until you hit the element to be removed, then rebuild the tree on the way back up

Pros: The meat of the algorithm is "Pure" as in, does not touch IO. You only actually need IO for a moment within removeRandom'. You can likely write a solution that looks a bit like this (interesting parts left blank ;).
removeAt :: Int -> Tree a -> Tree a
removeAt n tree = walk 0 tree
  where
    walk i Empty = ...
    walk i (Fork l r) = ...
    walk i l@(Leaf _)
      | i == n    = ...
      | otherwise = ...

removeRandom' tree = do
    element <- randomRIO (0, length tree)
    return $ removeAt element tree

Cons:  More complicated to implement, you need to know how to traverse back "up" a tree, rebuilding in your wake, and you will need to know how to write a recursive function with an accumulator such that you can track your position in the tree.

Either way you decide to go, you will need to write a function length :: Tree a -> Int that counts the number of leaves to use as input to randomRIO (which is an action that simply produces a random value in a given range).

