content: import Control.Applicative
  import Data.List
  import Text.PrettyPrint
  
  
  data Expr = C Int | Op String Expr Expr
  
  toDoc (C     x  ) = int x
  toDoc (Op op x y) = parens $ toDoc x <+> text op <+> toDoc y
  
  ops :: [(String, Int -> Int -> Int)]
  ops = [("+",(+)), ("-",(-)), ("*",(*)), ("/",div)]
  
  
  solve :: Int -> [Int] -> [Expr]
  solve res = filter ((Just res ==) . eval) . genAst
    where
      genAst [x] = [C x]
      genAst xs  = do
        (ys,zs) <- split xs
        let f (Op op _ _) = op `notElem` ["+","*"] || ys <= zs
        filter f $ Op <$> map fst ops <*> genAst ys <*> genAst zs
  
      eval (C      x  ) = Just x
      eval (Op "/" _ y) | Just 0 <- eval y = Nothing
      eval (Op op  x y) = lookup op ops <*> eval x <*> eval y
  
  
  select :: Int -> [Int] -> [[Int]]
  select 0 _  = [[]]
  select n xs = [x:zs | k <- [0..length xs - n]
                      , let (x:ys) = drop k xs
                      , zs <- select (n - 1) ys
                      ]
  
  split :: [Int] -> [([Int],[Int])]
  split xs = [(ys, xs \\ ys) | n <- [1..length xs - 1]
                             , ys <- nub . sort $ select n xs
                             ]
  
  
  main = mapM_ (putStrLn . render . toDoc) $ solve 24 [2,3,8,9]
  