Proposal: add uncons (and unsnoc) to Data.List
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
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA256 +1 for uncons. - -- Alexander alexander@plaimi.net https://secure.plaimi.net/~alexander -----BEGIN PGP SIGNATURE----- Version: GnuPG v2 Comment: Using GnuPG with Thunderbird - http://www.enigmail.net/ iF4EAREIAAYFAlPK9g4ACgkQRtClrXBQc7UoOAD/QHo90rH+pmChxmAesL6UBugi b1xtOkU5WvOMN8eu7wAA/1poLAAnXAG8DrA84vd+GInAMSHUy/RQVpSsdEZgXxmO =9Zcv -----END PGP SIGNATURE-----
+1 for uncons, I've wanted that a few times.
On Sat, Jul 19, 2014 at 11: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
_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries
On Sat, Jul 19, 2014 at 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)
+1 for uncons. Yes, uncons is a view, but I see no benefit in naming the function after that fact— given that "uncons" is the standard/popular name, and that we don't typically name any other views "viewFoo".
-- 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 ++ _|_, _|_)
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) I've never had any reason to use it. But since the implementation is tricky, I'm +1 if other folks want it. -- Live well, ~wren
Am 20.07.2014 05:01, schrieb wren romano:
Yes, uncons is a view, but I see no benefit in naming the function after that fact— given that "uncons" is the standard/popular name, and that we don't typically name any other views "viewFoo".
As I said, I chose the name according to Data.Sequence: http://hackage.haskell.org/package/containers-0.5.5.1/docs/Data-Sequence.htm... There is also: http://hackage.haskell.org/package/containers-0.5.5.1/docs/Data-Map-Lazy.htm... http://hackage.haskell.org/package/containers-0.5.5.1/docs/Data-Set.html#v:m... But I am not bound to it.
I'd favor unsnoc and uncons over viewL / viewR as the type is a bit different having no dedicated view data type, etc. uncons seems by far more commonly reinvented name for the concept, being used across bytestring, parsec, etc. https://www.fpcomplete.com/hoogle?q=uncons&env=ghc-7.4.2-stable-13.09 While the viewL/viewR's out there all have their heritage in the Data.Seq / fingertree usage. https://www.fpcomplete.com/hoogle?q=viewl&env=ghc-7.4.2-stable-13.09 I tend to reserve using viewL / viewR for the dedicated data type variant, as because the latter fits in a bit worse with other uses of Maybe but can be ever so slightly more efficient due to the dedicated constructor I often try to supply both. Also a motivation for the uncons nomenclature is it preserves something like symmetry between `unfoldr uncons` and `foldr (:) []`. It is a much easier to sell an uncons/unsnoc than to sell new data types and a viewL/viewR to go with them, and it seems to me to be better to reserve the latter names for folks who do want to supply such a beast. -Edward On Sun, Jul 20, 2014 at 12:07 AM, Henning Thielemann < schlepptop@henning-thielemann.de> wrote:
Am 20.07.2014 05:01, schrieb wren romano:
Yes, uncons is a view, but I see no benefit in naming the function
after that fact— given that "uncons" is the standard/popular name, and that we don't typically name any other views "viewFoo".
As I said, I chose the name according to Data.Sequence:
http://hackage.haskell.org/package/containers-0.5.5.1/ docs/Data-Sequence.html#v:viewl
There is also: http://hackage.haskell.org/package/containers-0.5.5.1/ docs/Data-Map-Lazy.html#v:minView http://hackage.haskell.org/package/containers-0.5.5.1/ docs/Data-Set.html#v:minView
But I am not bound to it.
_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries
On Sun, 20 Jul 2014 01:38:12 -0400, Edward Kmett
I'd favor unsnoc and uncons over viewL / viewR as the type is a bit different having no dedicated view data type, etc.
uncons seems by far more commonly reinvented name for the concept, being used across bytestring, parsec, etc.
https://www.fpcomplete.com/hoogle?q=uncons&env=ghc-7.4.2-stable-13.09
While the viewL/viewR's out there all have their heritage in the Data.Seq / fingertree usage.
https://www.fpcomplete.com/hoogle?q=viewl&env=ghc-7.4.2-stable-13.09
I tend to reserve using viewL / viewR for the dedicated data type variant, as because the latter fits in a bit worse with other uses of Maybe but can be ever so slightly more efficient due to the dedicated constructor I often try to supply both.
Also a motivation for the uncons nomenclature is it preserves something like symmetry between `unfoldr uncons` and `foldr (:) []`.
It is a much easier to sell an uncons/unsnoc than to sell new data types and a viewL/viewR to go with them, and it seems to me to be better to reserve the latter names for folks who do want to supply such a beast.
-Edward
For my intuition, it seems like view* functions are generally intended to be mixed with view patterns for pattern matching on something with non-exported constructors; whereas uncons for example doesn't really make sense as a pattern since matching against Just (x, xs) is no different than matching against x:xs. Moving forwards in the GHC 7.8 world, I'd almost suggest that everything that was previously a “viewX” function should now actually be a *pattern synonym*, like: pattern (xs :> x) <- (viewRTree -> Just2 xs (Elem x)) (Even better for types where this allows construction as well, but for Data.Sequence there are many possible ways to represent the same sequence, so a view pattern is required *somewhere*.)
+1 for uncons
I already searched for that function using this name.
On Jul 19, 2014 11: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
_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries
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
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA256 On 20/07/14 21:34, David Feuer wrote:
I don't know how it compares to Alexander's implementation My branch only has the naïve uncons. I do not have unsnoc at all. I am happy to add it. I.e., I am +0 on adding unsnoc. I do not have much input on which of the proposed implementations are better. I think we need benchmarks.
Alexander alexander@plaimi.net https://secure.plaimi.net/~alexander -----BEGIN PGP SIGNATURE----- Version: GnuPG v2 Comment: Using GnuPG with Thunderbird - http://www.enigmail.net/ iF4EAREIAAYFAlPMOHsACgkQRtClrXBQc7VIcgD/Y0C20WdsITc0XDOlJ21Luaa6 btzX8T326IDWyCCBSV8A/A98Li3pPrjOiNiHuQOY80dXbsSbjc4nLzlTVzqx12L7 =4Z2O -----END PGP SIGNATURE-----
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
participants (9)
-
Alexander Berntsen -
Alois Cochard -
David Feuer -
Edward Kmett -
Henning Thielemann -
John Wiegley -
Niklas Haskell -
Oliver Charles -
wren romano