gistfile1.txt

data Op = Plus | Minus | Concat deriving Show

f l = concatMap (\r -> map (: r) l)

step :: Int -> Op -> (Int, Int) -> (Int, Int)
step digit op (carry, sum) = case op of
    Concat -> (digit * 10 ^ ceiling (logBase 10 (fromIntegral carry)) + carry, sum)
    Plus -> (digit, sum + carry)
    Minus -> (digit, sum - carry)

showStep :: Int -> Op -> String -> String
showStep digit op = ((show digit ++ case op of
    Concat -> ""
    Plus -> " + "
    Minus -> " - ") ++)

answers m n = map
    ((++ (" = " ++ show m)) . snd)
    (filter
      ((== m) . fst)
      (zipWith (,)
        (map
          (\ops -> uncurry (+) $
            foldr (uncurry step)
              (n, 0)
              (zipWith (,) [1 ..] ops))
          allOps)
        (map
          (\ops ->
            foldr (uncurry showStep)
              (show n)
              (zipWith (,) [1 ..] ops))
          allOps)))
  where
    allOps = iterate (f [Plus, Minus, Concat]) [[Plus], [Minus], [Concat]] !! (n - 2)