Improve snocView implementation.

The new implementation isn't tailrecursive and instead
builds up the initial part of the list as it goes.

This improves allocation numbers as we don't build up an intermediate
list just to reverse it later.

This is slightly slower for lists of size <= 3. But in benchmarks
significantly faster for any list above 5 elements, assuming the
majority of the resulting list will be evaluated.

1 files changed, 17 insertions, 12 deletions

diff --git a/compiler/utils/Util.hs b/compiler/utils/Util.hs
index 876cd1ee6e..16864fe017 100644
--- a/compiler/utils/Util.hs
+++ b/compiler/utils/Util.hs
@@ -783,20 +783,25 @@ lastMaybe :: [a] -> Maybe a
 lastMaybe [] = Nothing
 lastMaybe xs = Just $ last xs
 
--- | If there is a good chance that you will only look at the last
--- element prefer seperate calls to @last@ + @init@.
--- @last@ does not allocate while traversing the list, while this
--- will. But if you are guaranteed to use both this will
--- usually be more efficient.
+-- | Split a list into its last element and the initial part of the list.
+-- @snocView xs = Just (init xs, last xs)@ for non-empty lists.
+-- @snocView xs = Nothing@ otherwise.
+-- Unless both parts of the result are guaranteed to be used
+-- prefer separate calls to @last@ + @init@.
+-- If you are guaranteed to use both, this will
+-- be more efficient.
 snocView :: [a] -> Maybe ([a],a)
-        -- Split off the last element
 snocView [] = Nothing
-snocView xs = go [] xs
-            where
-                -- Invariant: second arg is non-empty
-              go acc [x]    = Just (reverse acc, x)
-              go acc (x:xs) = go (x:acc) xs
-              go _   []     = panic "Util: snocView"
+snocView xs
+    | (xs,x) <- go xs
+    = Just (xs,x)
+  where
+    go :: [a] -> ([a],a)
+    go [x] = ([],x)
+    go (x:xs)
+        | !(xs',x') <- go xs
+        = (x:xs', x')
+    go [] = error "impossible"
 
 split :: Char -> String -> [String]
 split c s = case rest of