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

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

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

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

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

-----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-----

Thomas Schilling writes:

matchAndDropPrefx dropMatchingPrefix

stripMatchingPrefix? -- -David House, dmhouse@gmail.com

2007/7/1, Bulat Ziganshin :

functionThatRemovesItsFirstArgumentFromSecondOneOrReturnsNothing`PleaseSendSuggestionsAboutFurtherImprovingThisFunctionNameToTheUnitedKongdomCambridgeMicrosoftResearchLabsSimonPeytonJones`ThankYouForUsingOurFunction`CopyrightIanLynagh`AllRightsReserved

Hmm... fuctionThatRemovesItsFirstArgumentFromSecondOneOrReturnsNothing`theLicensesForMostSoftwareAreDesignedToTakeAwayYourFreedomToShareAndChangeItByContrastTheGnuGeneralPublicLicenseIsIntendedTo... Ah. Now I see why BSD is preferred in Haskell circles. :-) - Benja

Ketil Malde wrote:

On Sun, 2007-07-01 at 12:45 +0200, apfelmus wrote:

...

Here's an (admittedly crazy) approach

Why is it so crazy? The orthogonality issues with the different ways of breaking up lists (split/break/span/take/drop), and the multitude of possible predicates (either too complicated, or too specific) has always been an annoyance to me. I thought your solution was quite nice!

One problem is that you have to use drop (first 2) instead of drop 2 now. This can be remedied with some type-class hackery. Another problem is that performance will suffer a bit with the general approach. So, the specialized versions are likely to be kept around anyway. (Type classes can help with specialization, too.) Other than that, the general approach to drop & friends is not so crazy. But I don't like my implementation, so let's build a better one: One problem of the implementation is that I think it doesn't handle nicely the different semantics of dropPrefix compared to drop or dropWhile : whereas the latter don't fail on a premature end of the list, the dropPrefix version should fail. (The question whether it should fail with an error or with Nothing can be delegated by providing different variants of drop). The solution comes automatically when pondering what a Dropper really is: it's a *parser*. In other words, drop & friends are just functions that parse the beginning of a string and return how much has been parsed. Put differently, their feature is to ignore the "AST" resulting from a parse. type Dropper a = Parser a () -- token type a, result type () Here, I don't mean the usual (s -> (a,s)) parsers, but an implementation that fits the stream-like nature of our dropper: either a determinstic data Parser c r = Get (c -> Dropper c r) | Result r | Fail or a non-deterministic parser data Parser c a = Get (c -> Dropper c r) | Result r (Dropper c r) | Fail The latter are, of course, Koen Classen's parallel parsing processes (http://www.cs.chalmers.se/~koen/pubs/jfp04-parser.ps). Now, which ones to choose? With deterministic parsers, we loose the normal behavior of drop and dropWhile to accept lists that are too small. Thus, we choose non-deterministic parsers and implement drop with a "maximum munch" behavior -- drop as much as we can parse, but not more drop :: Dropper a -> [a] -> [a] drop p xs = case drop' p xs of Nothing -> error "drop: parse failed" Just xs -> xs where drop' Fail _ = Nothing drop' (Result _ p) xs = drop' p xs `mplus` Just xs drop' (Get f) (x:xs) = drop' (f x) xs drop' (Get _) [] = Nothing Here, the second equation of drop tries to drop more but jumps back via Maybe's `mplus` if that fails. With the usual Monad and MonadPlus instances for Parser c a, we can now write -- take while the condition is satisfied while :: (a -> Bool) -> Dropper a while = many' . satisfy where many' p = return () `mplus` p >> many' -- accept the first n characters or less first :: Int -> Dropper a first 0 = return () first n = return () `mplus` (get >> first (n-1)) -- parse a given String prefix :: Eq a => [a] -> Dropper a prefix [] = eaten prefix (x:xs) = get >>= \c -> if c == x then prefix xs else mzero By returning successes early, while and first accept an unexpected end of input. An alternative version of first that complains when not enough characters are available to drop would be exactly :: Int -> Dropper a exactly 0 = return () exactly n = get >> exactly (n-1) or exactly n = sequence_ (replicate n get) Regards, apfelmus

Ian Lynagh wrote:

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.

FWIW, the version in GHC is called "matchPrefixMaybe". Cheers, Simon