On Sun, Jul 20, 2014 at 3:34 PM, David Feuer
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)
The simpler version I posted yesterday is faster (albeit only slightly): unsnoc :: [a] -> Maybe ([a],a) unsnoc [] = Nothing unsnoc (x:xs) = Just $ go x xs where go x [] = ([], x) go x (y:ys) = let ~(zs,z) = go y ys in (x:zs, z) benchmarking unsnocMine/100 mean: 3.260214 us, lb 3.255431 us, ub 3.266097 us, ci 0.950 std dev: 27.05090 ns, lb 22.95311 ns, ub 33.29385 ns, ci 0.950 benchmarking unsnocMine/1000 mean: 34.70245 us, lb 34.64885 us, ub 34.76951 us, ci 0.950 std dev: 306.9910 ns, lb 258.8088 ns, ub 365.8965 ns, ci 0.950 benchmarking unsnocMine/10000 mean: 391.8438 us, lb 391.2511 us, ub 392.6225 us, ci 0.950 std dev: 3.468850 us, lb 2.804837 us, ub 4.484818 us, ci 0.950 benchmarking unsnocFeuer/100 mean: 3.366828 us, lb 3.361829 us, ub 3.373251 us, ci 0.950 std dev: 28.86669 ns, lb 24.10196 ns, ub 35.24502 ns, ci 0.950 benchmarking unsnocFeuer/1000 mean: 35.47399 us, lb 35.43366 us, ub 35.53489 us, ci 0.950 std dev: 250.7868 ns, lb 182.3132 ns, ub 351.4392 ns, ci 0.950 benchmarking unsnocFeuer/10000 mean: 408.7365 us, lb 408.0784 us, ub 409.5018 us, ci 0.950 std dev: 3.618910 us, lb 3.032826 us, ub 4.662995 us, ci 0.950 -- Live well, ~wren