Number of binary trees have N leaves with logging by Writer Monad

gistfile1.hs

import Control.Arrow (first)
import Control.Monad.List
import Control.Monad.Writer

liftList :: (Monad m) => [a] -> ListT m a
liftList = ListT . return

splites :: Int -> [(Int, Int)]
splites n = [ (x, n - x) | x <- [1..n-1] ]

countW :: Int -> (Int, [String])
countW 1 = (1, [])
countW n = first sum . runWriter . runListT $ do
    -- ListT (Writer [String]) Int
    (i, j) <- liftList (splites n)
    let cnt = fst (countW i) * fst (countW j)
    lift $ tell ["(" ++ show i ++ ", " ++ show j ++ ") = " ++ show cnt]
    return cnt

{-
  ghci> countW 5
  (14,["(1, 4) = 5","(2, 3) = 2","(3, 2) = 2","(4, 1) = 5"])

  ghci> mapM_ putStrLn . snd $ countW 5
  (1, 4) = 5
  (2, 3) = 2
  (3, 2) = 2
  (4, 1) = 5
-}