Haskell mode

1
module UniquePerms (
2
    uniquePerms
3
    )
4
where
5
 
6
-- | Find all unique permutations of a list where there might be duplicates.
7
uniquePerms :: (Eq a) => [a] -> [[a]]
8
uniquePerms = permBag . makeBag
9
 
10
-- | An unordered collection where duplicate values are allowed,
11
-- but represented with a single value and a count.
12
type Bag a = [(a, Int)]
13
 
14
makeBag :: (Eq a) => [a] -> Bag a
15
makeBag [] = []
16
makeBag (a:as) = mix a $ makeBag as
17
  where
18
    mix a []                        = [(a,1)]
19
    mix a (bn@(b,n):bs) | a == b    = (b,n+1):bs
20
                        | otherwise = bn : mix a bs
21
 
22
permBag :: Bag a -> [[a]]
23
permBag [] = [[]]
24
permBag bs = concatMap (\(f,cs) -> map (f:) $ permBag cs) . oneOfEach $ bs
25
  where
26
    oneOfEach [] = []
27
    oneOfEach (an@(a,n):bs) =
28
        let bs' = if n == 1 then bs else (a,n-1):bs
29
        in (a,bs') : mapSnd (an:) (oneOfEach bs)
30
    
31
    apSnd f (a,b) = (a, f b)
32
    mapSnd = map . apSnd
33
 
 

MIME types defined: text/x-haskell.