Add Foldable.{elem,maximum,minimum,sum,product} specializations.
authorMilan Straka <fox@ucw.cz>
Sun, 19 Oct 2014 12:07:42 +0000 (14:07 +0200)
committerMilan Straka <fox@ucw.cz>
Sun, 19 Oct 2014 12:07:42 +0000 (14:07 +0200)
Following #56, add specializations for other base-4.8 Foldable methods,
using strict folds and shortcircuiting.

The Set.elem uses only Eq a, so it runs in linear time.

Data/IntMap/Base.hs
Data/Map/Base.hs
Data/Set/Base.hs

index c1b2f4d..007e41e 100644 (file)
@@ -341,6 +341,36 @@ instance Foldable.Foldable IntMap where
   {-# INLINE null #-}
   toList = elems -- NB: Foldable.toList /= IntMap.toList
   {-# INLINE toList #-}
+  elem = go
+    where STRICT_1_OF_2(go)
+          go _ Nil = False
+          go x (Tip _ y) = x == y
+          go x (Bin _ _ l r) = go x l || go x r
+  {-# INLINABLE elem #-}
+  maximum = start
+    where start Nil = error "IntMap.Foldable.maximum: called with empty map"
+          start (Tip _ y) = y
+          start (Bin _ _ l r) = go (start l) r
+
+          STRICT_1_OF_2(go)
+          go m Nil = m
+          go m (Tip _ y) = max m y
+          go m (Bin _ _ l r) = go (go m l) r
+  {-# INLINABLE maximum #-}
+  minimum = start
+    where start Nil = error "IntMap.Foldable.minimum: called with empty map"
+          start (Tip _ y) = y
+          start (Bin _ _ l r) = go (start l) r
+
+          STRICT_1_OF_2(go)
+          go m Nil = m
+          go m (Tip _ y) = min m y
+          go m (Bin _ _ l r) = go (go m l) r
+  {-# INLINABLE minimum #-}
+  sum = foldl' (+) 0
+  {-# INLINABLE sum #-}
+  product = foldl' (*) 1
+  {-# INLINABLE product #-}
 #endif
 
 instance Traversable IntMap where
index 781ac3a..de074f4 100644 (file)
@@ -2675,6 +2675,31 @@ instance Foldable.Foldable (Map k) where
   {-# INLINE null #-}
   toList = elems -- NB: Foldable.toList /= Map.toList
   {-# INLINE toList #-}
+  elem = go
+    where STRICT_1_OF_2(go)
+          go _ Tip = False
+          go x (Bin _ _ v l r) = x == v || go x l || go x r
+  {-# INLINABLE elem #-}
+  maximum = start
+    where start Tip = error "Map.Foldable.maximum: called with empty map"
+          start (Bin _ _ v l r) = go (go v l) r
+
+          STRICT_1_OF_2(go)
+          go m Tip = m
+          go m (Bin _ _ v l r) = go (go (max m v) l) r
+  {-# INLINABLE maximum #-}
+  minimum = start
+    where start Tip = error "Map.Foldable.minumum: called with empty map"
+          start (Bin _ _ v l r) = go (go v l) r
+
+          STRICT_1_OF_2(go)
+          go m Tip = m
+          go m (Bin _ _ v l r) = go (go (min m v) l) r
+  {-# INLINABLE minimum #-}
+  sum = foldl' (+) 0
+  {-# INLINABLE sum #-}
+  product = foldl' (*) 1
+  {-# INLINABLE product #-}
 #endif
 
 instance (NFData k, NFData a) => NFData (Map k a) where
index 67ade4e..7e792f4 100644 (file)
@@ -283,10 +283,19 @@ instance Foldable.Foldable Set where
     {-# INLINE null #-}
     toList = toList
     {-# INLINE toList #-}
+    elem = go
+      where STRICT_1_OF_2(go)
+            go _ Tip = False
+            go x (Bin _ y l r) = x == y || go x l || go x r
+    {-# INLINABLE elem #-}
     minimum = findMin
     {-# INLINE minimum #-}
     maximum = findMax
     {-# INLINE maximum #-}
+    sum = foldl' (+) 0
+    {-# INLINABLE sum #-}
+    product = foldl' (*) 1
+    {-# INLINABLE product #-}
 #endif