smartGroup (empty) → 0.0.0

raw patch · 4 files changed

+175/−0 lines, 4 filesdep +basedep +containersdep +heapsetup-changed

Dependencies added: base, containers, heap

Files

LICENSE +30/−0
Setup.hs +2/−0
SmartGroup.hs +81/−0
smartGroup.cabal +62/−0

+ LICENSE view

@@ -0,0 +1,30 @@+Copyright (c)2010, Sam Anklesaria++All rights reserved.++Redistribution and use in source and binary forms, with or without+modification, are permitted provided that the following conditions are met:++    * Redistributions of source code must retain the above copyright+      notice, this list of conditions and the following disclaimer.++    * Redistributions in binary form must reproduce the above+      copyright notice, this list of conditions and the following+      disclaimer in the documentation and/or other materials provided+      with the distribution.++    * Neither the name of Sam Anklesaria nor the names of other+      contributors may be used to endorse or promote products derived+      from this software without specific prior written permission.++THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS+"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT+LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR+A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT+OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,+SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT+LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,+DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY+THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE+OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

+ Setup.hs view

@@ -0,0 +1,2 @@+import Distribution.Simple+main = defaultMain

+ SmartGroup.hs view

@@ -0,0 +1,81 @@+module SmartGroup (groupAll, groupNum, groupLog) where+import Data.Heap as Heap+import Data.Set as Set+import Data.Map as Map+import Data.Monoid+import Data.Ord++data StringL = StringL {str :: String, count :: Int} deriving (Eq, Show)+instance Ord StringL where compare (StringL i a) (StringL x b) = compare a b `mappend` compare i x+data SizeMap = Unsplittable (Set String) | Splittable (Map StringL (Set String)) deriving (Eq, Show)+instance Ord SizeMap where+         compare (Splittable a) (Splittable b) = compare (Map.size a) (Map.size b)+         compare (Unsplittable a) (Unsplittable b) = compare a b+         compare (Unsplittable _) (Splittable _) = LT+         compare (Splittable _) (Unsplittable _) = GT+type WordAssoc = MaxHeap SizeMap++toSet (Unsplittable x) = x+toSet (Splittable x) = Set.unions (Map.elems x)++intLog :: Int -> Int+intLog = truncate . logBase 2 . fromIntegral++groupWith :: (Int -> WordAssoc -> WordAssoc) -> Int -> [String] -> [[String]]+groupWith f i = mkList . f i . mkAssoc . mkMap++-- | Divide list into as many groups as possible+groupAll :: Int -> [String] -> [[String]]+groupAll = groupWith $ \i x->+         let cycleSplit n = case splitIt i n of+                  (Just a) -> cycleSplit a+                  Nothing -> n+         in cycleSplit x++-- | Divide list into about n different groups+groupNum :: Int -> Int -> [String] -> [[String]]+groupNum i = groupWith $ \x->+         let splitTimes n m =+                if Heap.size m >= n then m else+                   case splitIt x m of+                     (Just a) -> splitTimes n a+                     Nothing -> m+         in splitTimes i++-- | Divide list into groups such that the amount of groups+--   equals the log of the number of elements+groupLog :: Int -> [String] -> [[String]]+groupLog i s = groupNum (intLog (length s)) i s++mkMap :: [String] -> Map String (Set String)+mkMap = foldl (\m x->+        foldl (\m' i-> if length i > 3+              then Map.alter (Just . maybe (Set.singleton x) (Set.insert x)) i m' else m')+        m (words x)) Map.empty++mkAssoc :: Map String (Set String) -> MaxHeap SizeMap+mkAssoc m = Heap.singleton . Splittable . Map.mapKeys (\k-> StringL k (Set.size (m Map.! k))) $ m++splitIt :: Int -> WordAssoc -> Maybe WordAssoc+splitIt i s = case Heap.view s of+         (Just ((Unsplittable _),_)) -> Nothing+         (Just ((Splittable x),xs)) ->+               let+                  (Just (as,b)) = Map.maxView x+                  x1 = sizeMap i $ flip Map.mapMaybe b $ \n->+                      let m = Set.difference n as+                      in if Set.null m then Nothing else Just m+                  x2 = sizeMap i $ flip Map.mapMaybe b $ \n->+                      let m = Set.intersection n as+                      in if Set.null m then Nothing else Just m+                  x3 = as Set.\\ (Set.unions (Map.elems b))+               in Just $ (if Set.null x3 then id else Heap.insert (Unsplittable x3)) $+                   Heap.insert x1 $ Heap.insert x2 xs++sizeMap :: Int -> (Map StringL (Set String)) -> SizeMap+sizeMap i m = case Map.findMax m of+        (StringL _ c,_) -> if c >= i then Splittable m+                 else Unsplittable (Set.unions (Map.elems m))++mkList :: WordAssoc -> [[String]]+mkList = Prelude.map (Set.toList . toSet) . Heap.toList

+ smartGroup.cabal view

@@ -0,0 +1,62 @@+-- smartGroup.cabal auto-generated by cabal init. For additional+-- options, see+-- http://www.haskell.org/cabal/release/cabal-latest/doc/users-guide/authors.html#pkg-descr.+-- The name of the package.+Name:                smartGroup++-- The package version. See the Haskell package versioning policy+-- (http://www.haskell.org/haskellwiki/Package_versioning_policy) for+-- standards guiding when and how versions should be incremented.+Version:             0.0.0++-- A short (one-line) description of the package.+Synopsis:            group strings by words in common++-- A longer description of the package.+Description:         Given a list of strings, smartGroup provides a set of functions+                     to group them into smaller lists based on the most common words of the set.++-- URL for the project homepage or repository.+Homepage:            http://patch-tag.com/r/salazar/smartgroup++-- The license under which the package is released.+License:             BSD3++-- The file containing the license text.+License-file:        LICENSE++-- The package author(s).+Author:              Sam Anklesaria++-- An email address to which users can send suggestions, bug reports,+-- and patches.+Maintainer:          amsay@amsay.net++-- A copyright notice.+-- Copyright:           ++Category:            Algorithms++Build-type:          Simple++-- Extra files to be distributed with the package, such as examples or+-- a README.+-- Extra-source-files:  ++-- Constraint on the version of Cabal needed to build this package.+Cabal-version:       >=1.2+++Library+  -- Modules exported by the library.+  Exposed-modules:     SmartGroup+  +  -- Packages needed in order to build this package.+  Build-depends:       base >= 3 && < 5, containers < 1, heap < 1.1+  +  -- Modules not exported by this package.+  -- Other-modules:       +  +  -- Extra tools (e.g. alex, hsc2hs, ...) needed to build the source.+  -- Build-tools:         +