Instantly share code, notes, and snippets.

# Dierk/Balanced.purs Created Sep 14, 2017

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 "((()())())()"