Extend `Foldable` class with `length` and `null` methods

This completes the `Foldable` class by two important operations which
this way can be optimised for the underlying structure more easily.

A minor fix for the `containers` submodule was needed to due name clash

Addresses #9621

Reviewed By: ekmett, dfeuer, austin

Differential Revision: https://phabricator.haskell.org/D250

3 files changed, 11 insertions, 1 deletions

diff --git a/libraries/base/Data/Foldable.hs b/libraries/base/Data/Foldable.hs
index 688fd06ec0..d8310ca49e 100644
--- a/libraries/base/Data/Foldable.hs
+++ b/libraries/base/Data/Foldable.hs
@@ -149,6 +149,14 @@ class Foldable t where
     {-# INLINE toList #-}
     toList t = build (\ c n -> foldr c n t)
 
+    -- | Test whether the structure is empty.
+    null :: Foldable t => t a -> Bool
+    null = foldr (\_ _ -> False) True
+
+    -- | Returns the size/length of a finite structure as an 'Int'.
+    length :: Foldable t => t a -> Int
+    length = foldl' (\c _ -> c+1) 0
+
     -- | Does the element occur in the structure?
     elem :: (Foldable t, Eq a) => a -> t a -> Bool
     elem = any . (==)
@@ -186,8 +194,10 @@ instance Foldable [] where
     foldl1  = List.foldl1
     foldr   = List.foldr
     foldr1  = List.foldr1
+    length  = List.length
     maximum = List.maximum
     minimum = List.minimum
+    null    = List.null
     product = List.product
     sum     = List.sum
     toList  = id
diff --git a/libraries/base/Data/List.hs b/libraries/base/Data/List.hs
index 795baec6af..193ebbc0c4 100644
--- a/libraries/base/Data/List.hs
+++ b/libraries/base/Data/List.hs
@@ -213,4 +213,4 @@ import Data.Traversable
 import Data.OldList hiding ( all, and, any, concat, concatMap, elem, find,
                              foldl, foldl1, foldl', foldr, foldr1, mapAccumL,
                              mapAccumR, maximum, maximumBy, minimum, minimumBy,
-                             notElem, or, product, sum )
+                             length, notElem, null, or, product, sum )
diff --git a/libraries/containers b/libraries/containers
-Subproject e84c5d2145415cb0beacce0909a551ae5e28d39
+Subproject 085e1b8b2cfbd1159bbc9f8cbf6a4127cc32227