Instantly share code, notes, and snippets.

Embed
What would you like to do?
The balanced parentheses kata with two solutions in purescript
module Balanced where
import Prelude (Unit, discard, ($), (+), (-), (>=), (<=), (&&), (==), negate)
import Control.Monad.Eff (Eff)
import Control.Monad.Eff.Console (CONSOLE, logShow)
import Data.Foldable (traverse_, foldMap)
import Control.Monad.State (State, execState)
import Control.Monad.State.Class (modify)
import Data.String (toCharArray)
-- Kmett solution imports
import Data.Monoid (class Monoid)
import Data.Semigroup (class Semigroup)
import Data.Eq (class Eq)
-- standard way of using traverse (only for reference)
sumArray :: Array Int -> State Int Unit
sumArray = traverse_ \n -> modify \sum -> sum + n
trySumArray :: Int
trySumArray = execState (sumArray [1,2,3]) 0
-- Exercise from Purescript by Example chapter 11: test for balanced parentheses
-- a) use traverse and State Monad to check for balanced parens
type Scan = { pb :: Int -- parentheses balance
, pos :: Boolean -- did always stay positive
}
balArray :: Array Char -> State Scan Unit
balArray = traverse_ \c -> modify \scan -> scan {
pb = scan.pb + charValue c,
pos = scan.pb >= 0 && scan.pos
}
isBalanced1 :: String -> Boolean
isBalanced1 cs = isValid scan where
isValid {pb: 0, pos: true} = true
isValid _ = false
scan = execState (balArray (toCharArray cs)) {pb: 0, pos: true}
charValue :: Char -> Int
charValue '(' = 1
charValue ')' = -1
charValue _ = 0
-- b) stateless Edward Kmett solution shown at HaskellerZ meetup (adapted):
data B = B Int Int -- number of ))), number of (((
derive instance eqB :: Eq B
instance semigroupB :: Semigroup B where
append (B a b) (B c d)
| b <= c = B (a + c - b) (d) -- less ( than matching )) so overflow goes to the left
| true = B (a) (d + b - c) -- otherwise to the right
instance monoidB :: Monoid B where
mempty = B 0 0
parse :: Char -> B
parse ')' = B 1 0
parse '(' = B 0 1
parse _ = B 0 0
isBalanced2 :: String -> Boolean
isBalanced2 str = B 0 0 == foldMap parse (toCharArray str)
main :: forall e. Eff (console :: CONSOLE | e) Unit
main = do
logShow $ trySumArray
logShow $ false == isBalanced1 "("
logShow $ false == isBalanced1 ")"
logShow $ true == isBalanced1 "()"
logShow $ false == isBalanced1 ")()"
logShow $ false == isBalanced1 "(()"
logShow $ false == isBalanced1 "())"
logShow $ true == isBalanced1 "((()())())()"
logShow $ false == isBalanced2 "("
logShow $ false == isBalanced2 ")"
logShow $ true == isBalanced2 "()"
logShow $ false == isBalanced2 ")()"
logShow $ false == isBalanced2 "(()"
logShow $ false == isBalanced2 "())"
logShow $ true == isBalanced2 "((()())())()"
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment