bag (empty) → 0.1

raw patch · 5 files changed

+120/−0 lines, 5 filesdep +basesetup-changed

Dependencies added: base

Files

• Data/Bag.hs +75/−0
• LICENSE +21/−0
• README +2/−0
• Setup.hs +2/−0
• bag.cabal +20/−0

@@ -0,0 +1,75 @@+module Data.Bag where+import Data.Monoid+import Data.Foldable+import Control.Monad++data BagTree a = Leaf a | Branch (BagTree a) (BagTree a) deriving (Show)+data Bag a = Bag (BagTree a) | Empty deriving (Show)++empty :: Bag a+empty = Empty++unit :: a -> Bag a+unit a = Bag $ Leaf a++merge :: Bag a -> Bag a -> Bag a+merge (Bag a) (Bag b) = Bag $ Branch a b+merge Empty b = b+merge a Empty = a++btconcat :: BagTree (BagTree a) -> BagTree a+btconcat (Leaf a) = a+btconcat (Branch a b) = Branch (btconcat a) (btconcat b)++bconcat :: Bag (Bag a) -> Bag a+bconcat Empty = Empty+bconcat (Bag a) =+    concat a+  where+    concat :: BagTree (Bag a) -> Bag a+    concat (Leaf x) = x+    concat (Branch a b) =+        let a' = concat a+            b' = concat b in+                case (a', b') of+                    (Bag a'', Bag b'') -> Bag $ Branch a'' b''+                    (Empty, b'') -> b''+                    (a'', Empty) -> a''++instance Monoid (Bag a) where+    mempty = empty+    mappend = merge++instance Foldable BagTree where+    foldMap f (Leaf x) = f x+    foldMap f (Branch a b) = (foldMap f a) `mappend` (foldMap f b)++instance Foldable Bag where+    foldMap _ Empty = mempty+    foldMap f (Bag t) = foldMap f t++instance Functor BagTree where+    fmap f (Leaf x) = Leaf $ f x+    fmap f (Branch a b) = Branch (fmap f a) (fmap f b)++instance Functor Bag where+    fmap _ Empty = empty+    fmap f (Bag t) = Bag $ fmap f t++instance Monad BagTree where+    return = Leaf+    m >>= f = btconcat $ fmap f m++instance Monad Bag where+    return = Bag . Leaf+    m >>= f = bconcat $ fmap f m++instance MonadPlus Bag where+    mzero = empty+    mplus = merge++instance Eq a => Eq (BagTree a) where+    a == b = (toList a) == (toList b)++instance Eq a => Eq (Bag a) where+    a == b = (toList a) == (toList b)

@@ -0,0 +1,21 @@+The MIT License (MIT)++Copyright (c) 2011 Daniel Waterworth++Permission is hereby granted, free of charge, to any person obtaining a copy of +this software and associated documentation files (the "Software"), to deal in +the Software without restriction, including without limitation the rights to +use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies +of the Software, and to permit persons to whom the Software is furnished to do +so, subject to the following conditions:++The above copyright notice and this permission notice shall be included in all +copies or substantial portions of the Software.++THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE +SOFTWARE.

@@ -0,0 +1,2 @@+bag provides an alternative to a list for cases where constant time +concatenation is required.

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

@@ -0,0 +1,20 @@+Name:                   bag+Synopsis:               A simple stable bag.+Version:                0.1+Category:               Data Structures+License:                MIT+License-file:           LICENSE+Extra-source-files:     README+Author:                 Daniel Waterworth <da.waterworth@gmail.com>+Maintainer:             Daniel Waterworth <da.waterworth@gmail.com>+Stability:              experimental+Build-Type:             Simple+Cabal-Version:          >=1.4+Description:+    bag provides an alternative to a list for cases where constant time +    concatenation is required.++Library+    Build-Depends:      base >= 4 && < 5+    Exposed-modules:+        Data.Bag