Derive the definition of null

We can sometimes produce much better code by deriving the
definition of `null` rather than using the default. For example,
given

    data SnocList a = Lin | Snoc (SnocList a) a

the default definition of `null` will walk the whole list, but of
course we can stop as soon as we see `Snoc`. Similarly, if a
constructor contains some other `Foldable` type, we want to use its
`null` rather than folding over the structure.

Partially fixes Trac #13280

Reviewers: austin, bgamari, RyanGlScott

Reviewed By: RyanGlScott

Subscribers: rwbarton, thomie

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

1 files changed, 28 insertions, 22 deletions

diff --git a/docs/users_guide/8.4.1-notes.rst b/docs/users_guide/8.4.1-notes.rst
index 4470bb9e79..193515c077 100644
--- a/docs/users_guide/8.4.1-notes.rst
+++ b/docs/users_guide/8.4.1-notes.rst
@@ -25,44 +25,50 @@ Compiler
 ~~~~~~~~
 
 - Derived ``Functor``, ``Foldable``, and ``Traversable`` instances are now
-optimized when their last type parameters have phantom roles. Specifically, ::
+  optimized when their last type parameters have phantom roles.
+  Specifically, ::
 
     fmap _ = coerce
     traverse _ x = pure (coerce x)
     foldMap _ _ = mempty
 
-These definitions of ``foldMap`` and ``traverse`` are lazier than
-the ones we would otherwise derive, as they may produce results without
-inspecting their arguments at all.
+  These definitions of ``foldMap`` and ``traverse`` are lazier than the ones we
+  would otherwise derive, as they may produce results without inspecting their
+  arguments at all.
 
-See also :ref:`deriving-functor`, :ref:`deriving-foldable`, and
-:ref:`deriving-traversable`.
+  See also :ref:`deriving-functor`, :ref:`deriving-foldable`, and
+  :ref:`deriving-traversable`.
 
 - Derived ``Functor``, ``Foldable``, ``Traversable``, ``Generic``, and
-``Generic1`` instances now have better, and generally better-documented,
-behaviors for types with no constructors. In particular, ::
+  ``Generic1`` instances now have better, and generally better-documented,
+  behaviors for types with no constructors. In particular, ::
 
-    fmap _ x = case x of
-    foldMap _ _ = mempty
-    traverse _ x = pure (case x of)
-    to x = case x of
-    to1 x = case x of
-    from x = case x of
-    from1 x = case x of
+      fmap _ x = case x of
+      foldMap _ _ = mempty
+      traverse _ x = pure (case x of)
+      to x = case x of
+      to1 x = case x of
+      from x = case x of
+      from1 x = case x of
+
+  The new behavior generally leads to more useful error messages than the
+  old did, and lazier semantics for ``foldMap`` and ``traverse``.
 
-The new behavior generally leads to more useful error messages than the
-old did, and lazier semantics for ``foldMap`` and ``traverse``.
+- Derived ``Foldable`` instances now derive custom definitions for ``null``
+  instead of using the default one. This leads to asymptotically better
+  performance for recursive types not shaped like cons-lists, and allows ``null``
+  to terminate for more (but not all) infinitely large structures.
 
 - Derived instances for types with no constructors now have appropriate
-arities: they take all their arguments before producing errors. This may not
-be terribly important in practice, but it seems like the right thing to do.
-Previously, we generated ::
+  arities: they take all their arguments before producing errors. This may not
+  be terribly important in practice, but it seems like the right thing to do.
+  Previously, we generated ::
 
-    (==) = error ...
+      (==) = error ...
 
 Now we generate ::
 
-    _ == _ = error ...
+      _ == _ = error ...
 
 - Lots of other bugs. See `Trac
    <https://ghc.haskell.org/trac/ghc/query?status=closed&milestone=8.4.1&col=id&col=summary&col=status&col=type&col=priority&col=milestone&col=component&order=priority>`_