Avoid uses of head and tail

[RyanGlScott]

Compiling ad with GHC 9.8.1 reveals a number of -Wx-partial warnings caused by uses of the partial head and tail functions:

[12 of 55] Compiling Numeric.AD.Internal.Tower ( src/Numeric/AD/Internal/Tower.hs, /home/ryanglscott/Documents/Hacking/Haskell/ci-maintenance/checkout/ekmett/ad/dist-newstyle/build/x86_64-linux/ghc-9.8.0.20230727/ad-4.5.4/build/Numeric/AD/Internal/Tower.o, /home/ryanglscott/Documents/Hacking/Haskell/ci-maintenance/checkout/ekmett/ad/dist-newstyle/build/x86_64-linux/ghc-9.8.0.20230727/ad-4.5.4/build/Numeric/AD/Internal/Tower.dyn_o )

src/Numeric/AD/Internal/Tower.hs:178:39: warning: [GHC-63394] [-Wx-partial]
    In the use of ‘tail’
    (imported from Prelude, but defined in Just GHC.List):
    "This is a partial function, it throws an error on empty lists. Replace it with drop 1, or use pattern matching or Data.List.uncons instead. Consider refactoring to use Data.List.NonEmpty."
    |
178 |         next xs = 1 : zipWith (+) xs (tail xs) ++ [1] -- next row in Pascal's triangle
    |                                       ^^^^

src/Numeric/AD/Internal/Tower.hs:179:36: warning: [GHC-63394] [-Wx-partial]
    In the use of ‘tail’
    (imported from Prelude, but defined in Just GHC.List):
    "This is a partial function, it throws an error on empty lists. Replace it with drop 1, or use pattern matching or Data.List.uncons instead. Consider refactoring to use Data.List.NonEmpty."
    |
179 |         next' xs = zipWith (+) xs (tail xs) ++ [1] -- end part of next row in Pascal's triangle
    |                                    ^^^^

[20 of 55] Compiling Numeric.AD.Internal.Forward.Double ( src/Numeric/AD/Internal/Forward/Double.hs, /home/ryanglscott/Documents/Hacking/Haskell/ci-maintenance/checkout/ekmett/ad/dist-newstyle/build/x86_64-linux/ghc-9.8.0.20230727/ad-4.5.4/build/Numeric/AD/Internal/Forward/Double.o, /home/ryanglscott/Documents/Hacking/Haskell/ci-maintenance/checkout/ekmett/ad/dist-newstyle/build/x86_64-linux/ghc-9.8.0.20230727/ad-4.5.4/build/Numeric/AD/Internal/Forward/Double.dyn_o )

src/Numeric/AD/Internal/Forward/Double.hs:139:15: warning: [GHC-63394] [-Wx-partial]
    In the use of ‘tail’
    (imported from Prelude, but defined in Just GHC.List):
    "This is a partial function, it throws an error on empty lists. Replace it with drop 1, or use pattern matching or Data.List.uncons instead. Consider refactoring to use Data.List.NonEmpty."
    |
139 |   go xss b = (tail <$> xss, f b (head <$> xss))
    |               ^^^^

src/Numeric/AD/Internal/Forward/Double.hs:139:34: warning: [GHC-63394] [-Wx-partial]
    In the use of ‘head’
    (imported from Prelude, but defined in Just GHC.List):
    "This is a partial function, it throws an error on empty lists. Use pattern matching or Data.List.uncons instead. Consider refactoring to use Data.List.NonEmpty."
    |
139 |   go xss b = (tail <$> xss, f b (head <$> xss))
    |                                  ^^^^

[21 of 55] Compiling Numeric.AD.Internal.Forward ( src/Numeric/AD/Internal/Forward.hs, /home/ryanglscott/Documents/Hacking/Haskell/ci-maintenance/checkout/ekmett/ad/dist-newstyle/build/x86_64-linux/ghc-9.8.0.20230727/ad-4.5.4/build/Numeric/AD/Internal/Forward.o, /home/ryanglscott/Documents/Hacking/Haskell/ci-maintenance/checkout/ekmett/ad/dist-newstyle/build/x86_64-linux/ghc-9.8.0.20230727/ad-4.5.4/build/Numeric/AD/Internal/Forward.dyn_o )

src/Numeric/AD/Internal/Forward.hs:202:15: warning: [GHC-63394] [-Wx-partial]
    In the use of ‘tail’
    (imported from Prelude, but defined in Just GHC.List):
    "This is a partial function, it throws an error on empty lists. Replace it with drop 1, or use pattern matching or Data.List.uncons instead. Consider refactoring to use Data.List.NonEmpty."
    |
202 |   go xss b = (tail <$> xss, f b (head <$> xss))
    |               ^^^^

src/Numeric/AD/Internal/Forward.hs:202:34: warning: [GHC-63394] [-Wx-partial]
    In the use of ‘head’
    (imported from Prelude, but defined in Just GHC.List):
    "This is a partial function, it throws an error on empty lists. Use pattern matching or Data.List.uncons instead. Consider refactoring to use Data.List.NonEmpty."
    |
202 |   go xss b = (tail <$> xss, f b (head <$> xss))
    |                                  ^^^^

[40 of 55] Compiling Numeric.AD.Newton ( src/Numeric/AD/Newton.hs, /home/ryanglscott/Documents/Hacking/Haskell/ci-maintenance/checkout/ekmett/ad/dist-newstyle/build/x86_64-linux/ghc-9.8.0.20230727/ad-4.5.4/build/Numeric/AD/Newton.o, /home/ryanglscott/Documents/Hacking/Haskell/ci-maintenance/checkout/ekmett/ad/dist-newstyle/build/x86_64-linux/ghc-9.8.0.20230727/ad-4.5.4/build/Numeric/AD/Newton.dyn_o )

src/Numeric/AD/Newton.hs:265:13: warning: [GHC-63394] [-Wx-partial]
    In the use of ‘tail’
    (imported from Prelude, but defined in Just GHC.List):
    "This is a partial function, it throws an error on empty lists. Replace it with drop 1, or use pattern matching or Data.List.uncons instead. Consider refactoring to use Data.List.NonEmpty."
    |
265 |     dLeft = tail $ cycle d0
    |             ^^^^

src/Numeric/AD/Newton.hs:266:47: warning: [GHC-63394] [-Wx-partial]
    In the use of ‘head’
    (imported from Prelude, but defined in Just GHC.List):
    "This is a partial function, it throws an error on empty lists. Use pattern matching or Data.List.uncons instead. Consider refactoring to use Data.List.NonEmpty."
    |
266 |     xgx0 = Reverse.gradWith (,) (errorSingle (head d0)) x0
    |                                               ^^^^

src/Numeric/AD/Newton.hs:269:43: warning: [GHC-63394] [-Wx-partial]
    In the use of ‘tail’
    (imported from Prelude, but defined in Just GHC.List):
    "This is a partial function, it throws an error on empty lists. Replace it with drop 1, or use pattern matching or Data.List.uncons instead. Consider refactoring to use Data.List.NonEmpty."
    |
269 |       | otherwise     = x1 : go xgx1 eta (tail d)
    |                                           ^^^^

src/Numeric/AD/Newton.hs:272:57: warning: [GHC-63394] [-Wx-partial]
    In the use of ‘head’
    (imported from Prelude, but defined in Just GHC.List):
    "This is a partial function, it throws an error on empty lists. Use pattern matching or Data.List.uncons instead. Consider refactoring to use Data.List.NonEmpty."
    |
272 |         (_, xgx1) = Reverse.gradWith' (,) (errorSingle (head d)) x1
    |                                                         ^^^^

It's likely that some uses of head/tail here are unnecessary and could be replaced with total functions. For example, the zipWith f xs (tail xs) pattern used in Numeric.AD.Internal.Tower could easily be replaced with a function like this one:

zipWithTail :: (a -> a -> b) -> [a] -> [b]
zipWithTail _ [] = []
zipWithTail f xs@(_:xss) = zipWith f xs xss

Other uses of head and tail are genuinely partial, however. For instance, the transposeWith function in Numeric.AD.Internal.Forward is not total:

λ> transposeWith (\_ -> id) [[] :: [()]] [()]
[[*** Exception: Prelude.head: empty list
CallStack (from HasCallStack):
  error, called at libraries/base/GHC/List.hs:1782:3 in base:GHC.List
  errorEmptyList, called at libraries/base/GHC/List.hs:89:11 in base:GHC.List
  badHead, called at libraries/base/GHC/List.hs:83:28 in base:GHC.List
  head, called at src/Numeric/AD/Internal/Forward/Double.hs:141:34 in ad-4.5.4-inplace:Numeric.AD.Internal.Forward.Double

For these functions, we should give better error messages when they are supplied bad inputs and document what precisely the bad inputs are.

I'm not as certain whether other functions are total or not, so we'll have to take a closer look.