module Parens where

-- check in a string, whether parenthesis are balanced
--
-- two solutions
--
-- 1. with a monoid for counting opening and closing parenthesis
--    (seen in a talk by Edward Kmett about semigroups, monoids and inverse semigrops)
--
-- 2. naive solution: simplification by reduction

-- ----------------------------------------

data P = P !Int !Int deriving (Eq, Show)

instance Semigroup P where
  P x1 y1 <> P x2 y2
    | y1 < x2   = P (x1 + (x2 - y1))  y2
    | otherwise = P  x1  ((y1 - x2) + y2)

instance Monoid P where
  mempty = P 0 0

balanced :: Foldable t => t Char -> Bool
balanced s = toP s == mempty

showP :: P -> String
showP (P x y) = replicate x ')' ++ replicate y '('

-- the working horse
--
-- map-reduce with parse as map and <> as reduce

toP :: Foldable t => t Char -> P
toP s = foldMap parse s

parse :: Char -> P
parse '(' = P 0 1
parse ')' = P 1 0
parse _   = mempty

-- more abstract
-- modular, parsing and counting separated
-- constant space for intermediate results
-- may be parallelized due to Semigroup and Monoid instance
-- all chars are processed only once

-- ----------------------------------------

balanced' :: String -> Bool
balanced' = null . reduce []

showP' :: String -> String
showP' = reduce []

-- the working horse, scan input, reduce pairs of parenthesis
-- and remember none matching parenthesis
--
-- sequential and chars are compared multiple times
-- intermediate data may grow proportional to input size

reduce :: String -> String -> String
reduce xs         []         = reverse xs          -- input read, return result
reduce ('(' : xs) (')' : ys) = reduce xs ys        -- simplify a pair of ()
reduce xs           (y : ys)
  | y == '(' || y == ')'     = reduce (y : xs) ys  -- store parenthesis
  | otherwise                = reduce      xs  ys  -- forget all other chars

-- ----------------------------------------