<!doctype html><html><head><metacharset="utf-8"><title>CodeMirror: Haskell mode</title><linkrel="stylesheet"href="../../lib/codemirror.css"><scriptsrc="../../lib/codemirror.js"></script><scriptsrc="../../addon/edit/matchbrackets.js"></script><scriptsrc="haskell.js"></script><linkrel="stylesheet"href="../../theme/elegant.css"><styletype="text/css">.CodeMirror{border-top:1pxsolidblack;border-bottom:1pxsolidblack;}</style><linkrel="stylesheet"href="../../doc/docs.css"></head><body><h1>CodeMirror: Haskell mode</h1><form><textareaid="code"name="code">module UniquePerms (
uniquePerms
)
where
-- | Find all unique permutations of a list where there might be duplicates.
uniquePerms :: (Eq a) => [a] -> [[a]]
uniquePerms = permBag . makeBag
-- | An unordered collection where duplicate values are allowed,
-- but represented with a single value and a count.
type Bag a = [(a, Int)]
makeBag :: (Eq a) => [a] -> Bag a
makeBag [] = []
makeBag (a:as) = mix a $ makeBag as
where
mix a [] = [(a,1)]
mix a (bn@(b,n):bs) | a == b = (b,n+1):bs
| otherwise = bn : mix a bs
permBag :: Bag a -> [[a]]
permBag [] = [[]]
permBag bs = concatMap (\(f,cs) -> map (f:) $ permBag cs) . oneOfEach $ bs
where
oneOfEach [] = []
oneOfEach (an@(a,n):bs) =
let bs' = if n == 1 then bs else (a,n-1):bs
in (a,bs') : mapSnd (an:) (oneOfEach bs)
apSnd f (a,b) = (a, f b)
mapSnd = map . apSnd
</textarea></form><script>vareditor=CodeMirror.fromTextArea(document.getElementById("code"),{lineNumbers:true,matchBrackets:true,theme:"elegant"});</script><p><strong>MIME types defined:</strong><code>text/x-haskell</code>.</p></body></html>