Balanced brackets: Difference between revisions
m
→{{header|Haskell}}: (Applied hlint, hindent)
Drkameleon (talk | contribs) No edit summary |
m (→{{header|Haskell}}: (Applied hlint, hindent)) |
||
Line 3,114:
isBalanced :: String -> Maybe Int
isBalanced = bal (-1) 0
where
bal i n (']':bs) = bal (i + 1) (n - 1) bs
-- Print a string, indicating whether it contains balanced brackets. If not,
Line 3,125 ⟶ 3,126:
check :: String -> IO ()
check s = maybe (good s) (bad s) (isBalanced s)
where
where good s = printf "Good \"%s\"\n" s▼
main :: IO ()
Line 3,132 ⟶ 3,134:
let bs = cycle "[]"
rs <- replicateM 10 newStdGen
zipWithM_ (\n r -> check $ shuffle (take n bs) r) [0,2 ..] rs</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.
<lang haskell>module VShuffle
( shuffle
) where
import Data.List (mapAccumL)
Line 3,145 ⟶ 3,147:
-- Generate a list of array index pairs, each corresponding to a swap.
pairs
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 =
in (r', (i, j))
-- 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.
shuffle
shuffle :: (RandomGen g) => [a] -> g -> [a]▼
:: (RandomGen g)
shuffle xs r = V.toList . runST $ do▼
v <- V.unsafeThaw $ V.fromList xs▼
shuffle xs r =
mapM_ (uncurry $ M.swap v) $ pairs 0 (M.length v - 1) r▼
V.unsafeFreeze v▼
Here's some sample output.
<pre>
| |||