I don't know how it compares to Alexander's implementation, and I haven't
done any benchmarking, and only limited profiling, but it looks like the
following simple implementation does less allocation than Henning's *on GHC
7.8.3*. I know some changes are coming to the list fusion code, so his, or
some other, may suddenly get much better than this in the next version
(when applied to a good producer).
unsnoc :: [a] -> Maybe ([a],a)
unsnoc [] = Nothing
unsnoc (a:as) = Just $ unsnoc' a as
where
unsnoc' a as = forcePair $
case as of
[] -> ([], a)
(x:xs) -> case unsnoc' x xs of
(rst,lst)->(a:rst, lst)
forcePair ~(a,b) = (a,b)
On Jul 19, 2014 6:47 PM, "David Feuer"
Alexander Berntsen indicates that he has a branch all ready to go. Henning Thienemann seems to prefer the term viewL. Alexander says that Edward Kmett says that uncons/unsnoc is the more common term. Personally, I find uncons and unsnoc to be more intuitive names. Details:
uncons :: [a] -> Maybe (a, [a]) uncons [] = Nothing uncons (a:as) = Just (a,as)
-- Henning's implementation of "viewR", renamed, looks like
unsnoc :: [a] -> Maybe ([a], a) unsnoc = foldr (\x -> Just . forcePair . maybe ([],x) (mapFst (x:))) Nothing
I wonder if it would be possible to tease that apart a bit to get the maybe out of the loop, which I think might be prettier. The really tricky part of unsnoc is making it lazy enough—messing around with it a bit suggested that it's very easy to mess up the pair lifting. The tough rule seems to be this mouthful, if I'm not mistaken:
unsnoc (xs ++ (y : _|_)) = Just (xs ++ _|_, _|_)
David