From f4d8e907b6b2e4110e1c6a21b34b1b46566ff6d5 Mon Sep 17 00:00:00 2001 From: "klebinger.andreas@gmx.at" Date: Tue, 22 Jan 2019 16:17:40 +0100 Subject: 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. --- compiler/utils/Util.hs | 29 +++++++++++++++++------------ 1 file 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 -- cgit v1.2.1