Balanced brackets: Difference between revisions

Content added Content deleted
No edit summary
m (→‎{{header|Haskell}}: (Applied hlint, hindent))
Line 3,114: Line 3,114:
isBalanced :: String -> Maybe Int
isBalanced :: String -> Maybe Int
isBalanced = bal (-1) 0
isBalanced = bal (-1) 0
where
where bal :: Int -> Int -> String -> Maybe Int
bal _ 0 [] = Nothing
bal :: Int -> Int -> String -> Maybe Int
bal i _ [] = Just i
bal _ 0 [] = Nothing
bal i (-1) _ = Just i
bal i _ [] = Just i
bal i n ('[':bs) = bal (i+1) (n+1) bs
bal i (-1) _ = Just i
bal i n (']':bs) = bal (i+1) (n-1) bs
bal i n ('[':bs) = bal (i + 1) (n + 1) bs
bal i n (']':bs) = bal (i + 1) (n - 1) bs


-- Print a string, indicating whether it contains balanced brackets. If not,
-- Print a string, indicating whether it contains balanced brackets. If not,
Line 3,125: Line 3,126:
check :: String -> IO ()
check :: String -> IO ()
check s = maybe (good s) (bad s) (isBalanced s)
check s = maybe (good s) (bad s) (isBalanced s)
where
⚫
where good s = printf "Good \"%s\"\n" s
bad s n = printf "Bad \"%s\"\n%*s^\n" s (n+6) " "
good = printf "Good \"%s\"\n"
⚫
bad s n = printf "Bad \"%s\"\n%*s^\n" s (n + 6) " "


main :: IO ()
main :: IO ()
Line 3,132: Line 3,134:
let bs = cycle "[]"
let bs = cycle "[]"
rs <- replicateM 10 newStdGen
rs <- replicateM 10 newStdGen
zipWithM_ (\n r -> check $ shuffle (take n bs) r) [0,2..] rs
zipWithM_ (\n r -> check $ shuffle (take n bs) r) [0,2 ..] rs</lang>
</lang>
We put our list shuffling function in a separate module. For efficiency we use ''mutable'' vectors, although for the short lists in our example it doesn't really matter.
We put our list shuffling function in a separate module. For efficiency we use ''mutable'' vectors, although for the short lists in our example it doesn't really matter.
<lang haskell>
<lang haskell>module VShuffle
( shuffle
module VShuffle (shuffle) where
) where


import Data.List (mapAccumL)
import Data.List (mapAccumL)
Line 3,145: Line 3,147:


-- Generate a list of array index pairs, each corresponding to a swap.
-- Generate a list of array index pairs, each corresponding to a swap.
pairs
pairs :: (Enum a, Random a, RandomGen g) => a -> a -> g -> [(a, a)]
:: (Enum a, Random a, RandomGen g)
⚫
pairs l u r = snd $ mapAccumL step r [l..pred u]
=> a -> a -> g -> [(a, a)]
⚫
where step r i = let (j, r') = randomR (i, u) r in (r', (i, j))
⚫
pairs l u r = snd $ mapAccumL step r [l .. pred u]
where
step r i =
⚫
let (j, r') = randomR (i, u) r
in (r', (i, j))


-- Return a random permutation of the list. We use the algorithm described in
-- Return a random permutation of the list. We use the algorithm described in
-- http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm.
-- http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm.
shuffle
⚫
shuffle :: (RandomGen g) => [a] -> g -> [a]
:: (RandomGen g)
⚫
shuffle xs r = V.toList . runST $ do
⚫
=> [a] -> g -> [a]
⚫
v <- V.unsafeThaw $ V.fromList xs
shuffle xs r =
⚫
mapM_ (uncurry $ M.swap v) $ pairs 0 (M.length v - 1) r
⚫
V.toList . runST $
⚫
V.unsafeFreeze v
⚫
do v <- V.unsafeThaw $ V.fromList xs
</lang>
⚫
mapM_ (uncurry $ M.swap v) $ pairs 0 (M.length v - 1) r
⚫
V.unsafeFreeze v</lang>
Here's some sample output.
Here's some sample output.
<pre>
<pre>
Retrieved from "https://rosettacode.org/wiki/Balanced_brackets"