Proposal #1464: add dropPrefix to Data.List

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
27 messages Options
12
Reply | Threaded
Open this post in threaded view
|

Proposal #1464: add dropPrefix to Data.List

Ian Lynagh

Hi all,

I seem to have a copy of this function in everything I write sooner or
later, so I'd like to propose its addition to Data.List. It strips a
prefix from a list and, if successful, returns the tail. I often use it
with pattern guards:

    foo :: String -> IO ()
    foo x
     | Just y <- dropPrefix "foo=" = putStrLn ("foo is " ++ show y)
    foo _ = putStrLn "Unknown"

but you can of course achieve the same by using case etc.

The definition is:

    dropPrefix :: Eq a => [a] -> [a] -> Maybe [a]
    dropPrefix [] ys = Just ys
    dropPrefix (x:xs) (y:ys)
     | x == y = dropPrefix xs ys
    dropPrefix _ _ = Nothing

Let's try 11 July for a discussion deadline.


Thanks
Ian

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal #1464: add dropPrefix to Data.List

Arie Peterson
Ian Lynagh wrote:

> I seem to have a copy of this function in everything I write sooner or
> later, so I'd like to propose its addition to Data.List.

|modify succ|; I have an identical function in my inter-project file of
common functions.


Greetings,

Arie

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal #1464: add dropPrefix to Data.List

Chris Smith-39
In reply to this post by Ian Lynagh
Ian Lynagh wrote:
> The definition is:
>
>    dropPrefix :: Eq a => [a] -> [a] -> Maybe [a]
>    dropPrefix [] ys = Just ys
>    dropPrefix (x:xs) (y:ys)
>     | x == y = dropPrefix xs ys
>    dropPrefix _ _ = Nothing

Hmm.  That would replace a function I write today if only it were:

    dropPrefix :: (Monad m, Eq a) => [a] -> [a] -> m [a]
    dropPrefix [] ys = return ys
    dropPrefix (x:xs) (y:ys)
     | x == y = dropPrefix xs ys
    dropPrefix _ _ = fail "parse error"

I don't know if you'd consider this desire common enough to do the standard
library that way, but I noticed this, so I figured I'd mention something.

--
Chris Smith

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal #1464: add dropPrefix to Data.List

Bryan O'Sullivan
Chris Smith wrote:

> Hmm.  That would replace a function I write today if only it were:

+1 on the monadic variant, of which I have a copy just like Chris's.

        <b
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal #1464: add dropPrefix to Data.List

Robin Bate Boerop
I coded a function like this today.  So, it's addition to a library
somewhere would be useful.

I also note that Ian's version is a special case of Chris's version,
so there's really no conflict here.  (Yet.)

On 27/06/07, Bryan O'Sullivan <[hidden email]> wrote:
>
> +1 on the monadic variant, of which I have a copy just like Chris's.

--
Robin Bate Boerop
http://robin.bateboerop.name
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal #1464: add dropPrefix to Data.List

Iavor Diatchki
In reply to this post by Bryan O'Sullivan
Hi,
I can see how this function can be useful.  However, I am strongly
opposed to adding the general monadic version---not all monads support
graceful failure, and for monads that do not support it, the only
option is to throw a run-time exception, which is at odds with the
purity of Haskell (which leads to headaches when you try to write
robust code).  I think that the "Maybe" version is perfectly adequate
but if we have to have an overloaded version, then we should use
"MonadPlus".
-Iavor


On 6/26/07, Bryan O'Sullivan <[hidden email]> wrote:

> Chris Smith wrote:
>
> > Hmm.  That would replace a function I write today if only it were:
>
> +1 on the monadic variant, of which I have a copy just like Chris's.
>
>         <b
> _______________________________________________
> Libraries mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/libraries
>
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal #1464: add dropPrefix to Data.List

Donald Bruce Stewart
iavor.diatchki:

> Hi,
> I can see how this function can be useful.  However, I am strongly
> opposed to adding the general monadic version---not all monads support
> graceful failure, and for monads that do not support it, the only
> option is to throw a run-time exception, which is at odds with the
> purity of Haskell (which leads to headaches when you try to write
> robust code).  I think that the "Maybe" version is perfectly adequate
> but if we have to have an overloaded version, then we should use
> "MonadPlus".
> -Iavor

And in the dlist library we provide,

    maybeToMonadPlus :: MonadPlus m => Maybe a -> m a
    maybeToMonadPlus = maybe mzero return

For those who want it. (Maybe *that* should be in Data.Maybe).

-- Don
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal #1464: add dropPrefix to Data.List

Stefan Holdermans
In reply to this post by Chris Smith-39
Ian, Chris,

>    dropPrefix :: (Monad m, Eq a) => [a] -> [a] -> m [a]
>    dropPrefix [] ys = return ys
>    dropPrefix (x:xs) (y:ys)
>     | x == y = dropPrefix xs ys
>    dropPrefix _ _ = fail "parse error"

I also would like a monadic variant better (cf. Data.Map.lookup).  
However, I'd name it differently---not sure how, though---and reserve  
dropPrefix for

   dropPrefix          :: (Eq a) => [a] -> [a] -> [a]
   dropPrefix prefix l =  go prefix l where
     go (x : xs) (y : ys) | x == y = go xs ys
     go []       ys                = ys
     go _        _                 = l

which, to me, at least, seems more in line with drop and dropWhile.

Just my two cents, though.

Cheers,

   Stefan
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal #1464: add dropPrefix to Data.List

Tomasz Zielonka
In reply to this post by Iavor Diatchki
On Tue, Jun 26, 2007 at 10:00:02PM -0700, Iavor Diatchki wrote:
> I can see how this function can be useful.  However, I am strongly
> opposed to adding the general monadic version---not all monads support
> graceful failure, and for monads that do not support it, the only
> option is to throw a run-time exception, which is at odds with the
> purity of Haskell (which leads to headaches when you try to write
> robust code).  I think that the "Maybe" version is perfectly adequate
> but if we have to have an overloaded version, then we should use
> "MonadPlus".

Also, no functions in Data.List work with Monads right now, so this
one would be an exception. If dropPrefix is to use Monad interface, so
should find, findIndex, lookup and elemIndex.

$ echo ':b Data.List' | ghci | grep Monad

$ echo ':b Data.List' | ghci | grep Maybe
lookup :: (Eq a) => a -> [(a, b)] -> Maybe b
elemIndex :: (Eq a) => a -> [a] -> Maybe Int
find :: (a -> Bool) -> [a] -> Maybe a
findIndex :: (a -> Bool) -> [a] -> Maybe Int
unfoldr :: (b -> Maybe (a, b)) -> b -> [a]

Best regards
Tomek
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal #1464: add dropPrefix to Data.List

Henning Thielemann
In reply to this post by Ian Lynagh

On Wed, 27 Jun 2007, Ian Lynagh wrote:

> I seem to have a copy of this function in everything I write sooner or
> later, so I'd like to propose its addition to Data.List. It strips a
> prefix from a list and, if successful, returns the tail. I often use it
> with pattern guards:
>
>     foo :: String -> IO ()
>     foo x
>      | Just y <- dropPrefix "foo=" = putStrLn ("foo is " ++ show y)
>     foo _ = putStrLn "Unknown"
>
> but you can of course achieve the same by using case etc.
>
> The definition is:
>
>     dropPrefix :: Eq a => [a] -> [a] -> Maybe [a]
>     dropPrefix [] ys = Just ys
>     dropPrefix (x:xs) (y:ys)
>      | x == y = dropPrefix xs ys
>     dropPrefix _ _ = Nothing
>
> Let's try 11 July for a discussion deadline.

Indeed, I have written this function, too, but only one time, namely for
disecting CGI URLs:

maybePrefixOf :: Eq a => [a] -> [a] -> Maybe [a]
maybePrefixOf (x:xs) (y:ys) = if x==y then maybePrefixOf xs ys else Nothing
maybePrefixOf [] ys = Just ys
maybePrefixOf _  [] = Nothing
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal #1464: add dropPrefix to Data.List

Conor McBride
In reply to this post by Ian Lynagh
Hi Ian

I think I have this thing lying around as well:

On 27 Jun 2007, at 02:26, Ian Lynagh wrote:

>     dropPrefix :: Eq a => [a] -> [a] -> Maybe [a]
>     dropPrefix [] ys = Just ys
>     dropPrefix (x:xs) (y:ys)
>      | x == y = dropPrefix xs ys
>     dropPrefix _ _ = Nothing

But while I was grepping for it, I found I had written something
slightly different. Recalling that Monoid w makes Applicative ((,) w),
I have

   leftFactor :: Eq x => [x] -> [x] -> ([x], ([x], [x]))
   leftFactor (x : xs)  (y : ys) | x == y  = ([x], ()) *> leftFactor  
xs ys
   leftFactor xs        ys                 = pure (xs, ys)

Properties:

   if leftFactor xs ys = (zs, (xs', ys'))
   then zs is the longest list such that
     xs == zs ++ xs'
     ys == zs ++ ys'

You get dropPrefix cheaply

   dropPrefix :: Eq a => [a] -> [a] -> Maybe [a]
   dropPrefix xs ys
     | (_, ([], zs)) <- leftFactor xs ys = Just zs
     | otherwise = Nothing

but I also use it to do "common ancestor" calculations on hierarchical
namespaces. Indeed, I have in the past used this thing on paths/contexts
to determine whether two subterms of a given term were nested or not.

A more frivolous usage is this variation on an ancient program:

   gcdList :: Eq x => [x] -> [x] -> Maybe [x]
   gcdList xs ys = case leftFactor xs ys of
     (_, ([], []))  -> Just xs
     (_, ([], zs))  -> gcdList xs zs
     (_, (zs, []))  -> gcdList zs ys
     _              -> Nothing

gcdList xs ys calculates the largest zs such that
   xs == [1..m] >> zs and ys == [1..n] >> zs
if any such exists.

I was wondering what solutions there might be to
   xs ++ ys == ys ++ xs
when out it popped! But I digress.

It could well be that dropPrefix is much the more common, and hence that
extra fuss required to get it from leftFactor isn't worth it, but I
thought I'd punt out the possibility.

As for whether these things should return in Maybe, or some arbitrary
MonadPlus m, well, that seems like one instance of a wider question. We
surely need a consistent policy here: do we target the specific  
*minimal*
notion of computation supporting whatever it is (in this case, failure),
or attempt to abstract an *arbitrary* such. If the latter, one  
should, of
course, ask if Monad is too specific...

Now I come to think about it, I quite like the minimal approach. It  
keeps
the individual operations as simple as possible, and it pulls out the
Maybe -> whatever homomorphism as a largest left factor. Or something.

All the best

Conor


_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal #1464: add dropPrefix to Data.List

Chris Smith-39
In reply to this post by Iavor Diatchki
Iavor Diatchki wrote:
> I can see how this function can be useful.  However, I am strongly
> opposed to adding the general monadic version---not all monads support
> graceful failure [...]

Absolutely.  Consider me in favor of the MonadPlus version, then.  I had
just copied style from Data.Map before.  Monad would be more convenient than
Maybe, but MonadPlus is better yet.

--
Chris Smith

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal #1464: add dropPrefix to Data.List

Cale Gibbard
In reply to this post by Iavor Diatchki
I agree regarding Maybe, but in the long run, I really think we should
bring back MonadZero. This issue comes up all the time because there's
not really a proper class for monads that do handle failure gracefully
any more. I personally consider 'fail' to be a wart, and mostly try to
ignore that it even exists. Monad really isn't the class for
expressing computations which might fail.

 - Cale

On 27/06/07, Iavor Diatchki <[hidden email]> wrote:

> Hi,
> I can see how this function can be useful.  However, I am strongly
> opposed to adding the general monadic version---not all monads support
> graceful failure, and for monads that do not support it, the only
> option is to throw a run-time exception, which is at odds with the
> purity of Haskell (which leads to headaches when you try to write
> robust code).  I think that the "Maybe" version is perfectly adequate
> but if we have to have an overloaded version, then we should use
> "MonadPlus".
> -Iavor
>
>
> On 6/26/07, Bryan O'Sullivan <[hidden email]> wrote:
> > Chris Smith wrote:
> >
> > > Hmm.  That would replace a function I write today if only it were:
> >
> > +1 on the monadic variant, of which I have a copy just like Chris's.
> >
> >         <b
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal #1464: add dropPrefix to Data.List

Ashley Yakeley
Cale Gibbard wrote:
> I agree regarding Maybe, but in the long run, I really think we should
> bring back MonadZero.

We should also separate out the two different kinds of MonadPlus
instances. There are those such as [] that satisfy

   mplus a b >>= k = mplus (a >>= k) (b >>= k)

And there are those such as Maybe, IO and STM that satisfy

   mplus (return a) b = return a

See <http://haskell.org/haskellwiki/MonadPlus>.

--
Ashley Yakeley

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal #1464: add dropPrefix to Data.List

Isaac Dupree
In reply to this post by Cale Gibbard
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Cale Gibbard wrote:
> I agree regarding Maybe, but in the long run, I really think we should
> bring back MonadZero. This issue comes up all the time because there's
> not really a proper class for monads that do handle failure gracefully
> any more. I personally consider 'fail' to be a wart, and mostly try to
> ignore that it even exists. Monad really isn't the class for
> expressing computations which might fail.

agree about Monad fail.... but does everything that can fail have to be
a monad?  /me thinks about non-monadic applicative and arrows (at least)...

there is a class ArrowZero even!

There is a Monad=>MonadPlus, an Arrow=>ArrowZero=>ArrowPlus, an
Applicative=>Alternative, a Monoid. (and the Monoid kind of has the same
issue as the two kinds of MonadPlus instances, considering the proposal
to change Data.Map's Monoid instance, perhaps)

There is a MonadFix and a ArrowLoop, but no ApplicativeFix.

The arrows are somewhat special cases since they involve
different-looking types. (I wonder how much things are going to change
when we start using associated-types... after some years...)

This feels like somewhat of an ad-hoc mess at the moment :-/

for now, I wholeheartedly support the Maybe version of dropPrefix for
the purpose of going into the existing Data.List

Isaac
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFGhXn3HgcxvIWYTTURAorzAJ9GlcLCk2P0/NHrNddKeQivSU3vZQCgybiq
FTfTp6zdJjJfqPFPbH5O1A0=
=EcsX
-----END PGP SIGNATURE-----
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal #1464: add dropPrefix to Data.List

Thomas Schilling-2
> for now, I wholeheartedly support the Maybe version of dropPrefix for
> the purpose of going into the existing Data.List

+1

It's most consistent with the existing functions.  Also, most  
suggested more general implementations can be built atop of that one.

Thomas
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal #1464: add dropPrefix to Data.List

Ian Lynagh
In reply to this post by Ian Lynagh
On Wed, Jun 27, 2007 at 02:26:05AM +0100, Ian Lynagh wrote:
>
>     dropPrefix :: Eq a => [a] -> [a] -> Maybe [a]
>     dropPrefix [] ys = Just ys
>     dropPrefix (x:xs) (y:ys)
>      | x == y = dropPrefix xs ys
>     dropPrefix _ _ = Nothing

Summary so far:

Something should go in.

The Maybe version seems more popular than generalisations, especially
because Data.List already uses Maybe for the same sort of task in other
functions.

I don't think I tend to want the extra generality of Conor's leftFactor,
and no-one else has "me-too"ed it either. Also, writing "(_, ([], zs))"
rather than "Just zs" would be a bit cumbersome, so I think I'd like
dropPrefix even if we also had leftFactor.

Thus, based on the feedback thus far, I think dropPrefix as defined
above should go in, with 'generalising Data.List functions' and
'implementing "leftFactor"' being left to possible future proposals.

On names, Stefan wrote "I'd name it differently---not sure how", as the
existing drop* functions always returns a list. Other names I considered
were stripPrefix and removePrefix, but I can't think of any commonality
between those names and existing functions off the top of my head.


Thanks
Ian

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal #1464: add dropPrefix to Data.List

David House
In reply to this post by Thomas Schilling-2
Thomas Schilling writes:
 > It's most consistent with the existing functions.  Also, most  
 > suggested more general implementations can be built atop of that one.

Indeed, one could always write:

  embed :: Monad m => Maybe a -> m a
  embed Nothing = fail "Nothing"
  embed (Just x) = return x

--
-David House, [hidden email]
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal #1464: add dropPrefix to Data.List

Isaac Dupree
In reply to this post by Ian Lynagh
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Ian Lynagh wrote:
> I don't think I tend to want the extra generality of Conor's leftFactor,
> and no-one else has "me-too"ed it either. Also, writing "(_, ([], zs))"
> rather than "Just zs" would be a bit cumbersome, so I think I'd like
> dropPrefix even if we also had leftFactor.
>
> Thus, based on the feedback thus far, I think dropPrefix as defined
> above should go in, with 'generalising Data.List functions' and
> 'implementing "leftFactor"' being left to possible future proposals.

Agreed. I very well might use leftFactor, but... it is interesting...
hmm... too interesting to replace dropPrefix, I think... I really wish I
could try out leftFactor in something I'm already doing, to get a better
feel for it :)))


> On names, Stefan wrote "I'd name it differently---not sure how", as the
> existing drop* functions always returns a list. Other names I considered
> were stripPrefix and removePrefix, but I can't think of any commonality
> between those names and existing functions off the top of my head.

The name dropPrefix is somewhat redundant, since all existing "drop"
functions will only remove prefixes of a list anyway.  The other
connontation of "drop" is _wrong_ here: returning as much of the
original list as can't be dropped (as opposed to returning a Maybe).
Therefore, I see little or no merit in "drop" being part of the name,
assuming "Prefix" is.  I think I prefer stripPrefix.

Isaac
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFGhjV0HgcxvIWYTTURAmUQAJ4xXY/QVn5pA2uEs1YjQUm0tF3DegCgqreu
KlMc4lOMFULvtLGs80LCLqI=
=uF9S
-----END PGP SIGNATURE-----
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal #1464: add dropPrefix to Data.List

Thomas Schilling-2
In reply to this post by Ian Lynagh
On 30 jun 2007, at 02.35, Ian Lynagh wrote:
> On names, Stefan wrote "I'd name it differently---not sure how", as  
> the
> existing drop* functions always returns a list. Other names I  
> considered
> were stripPrefix and removePrefix, but I can't think of any  
> commonality
> between those names and existing functions off the top of my head.

matchAndDropPrefx
dropMatchingPrefix

?

/ Thomas
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
12