Proposal: add uncons (and unsnoc) to Data.List

[wren romano]

On Sun, Jul 20, 2014 at 3:34 PM, David Feuer <david.feuer at gmail.com> wrote:
> 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