leftmost Split

[imz]

Could having a "leftmost" version of Split be handy?

Am I correct that LeftmostSplit m would be equivalent to Dual (Split (Dual m))?

[byorgey]

Sure, it could I suppose. Do you have a specific application in mind?

And no, I don't think it is the same as Dual (Split (Dual m)):

(Dual (Dual m1 :| Dual m2)) <> (Dual (Dual m3 :| Dual m4))
= (Dual m3 :| Dual m4) <> (Dual m1 :| Dual m2)
= (Dual m3 <> Dual m4 <> Dual m1) :| Dual m2
= (m1 <> m4 <> m3) :| m2

but we wanted m1 :| (m2 <> m3 <> m4).

[imz]

Yes, I see, I was wrong with the Dual thing. (It's a bit crazy realizing this.)

The specific application is splitting strings like -DDEBUG=3 or -DDEBUG into two parts (actually, the two cases of Split String), as it would be done with break, but in a more "type-safe" way (in some sense).

I've just written a function that would help for this application:

module Data.Monoid.Split.Leftmost(module Data.Monoid.Split
                                 ,module Data.Monoid.Split.Leftmost
                                 )
where

import Data.Monoid.Split

newtype Leftmost m = Leftmost{ getLeftmost :: Split m }

-- TODO: the instances

{- A general-purpose utility: -}

leftmostSplit :: (a -> Bool) -> [a] -> Split [a]
leftmostSplit p =
    getLeftmost
    . fold
    . fmap (Leftmost
            . \x -> if p x
                    then split
                    else M [x])

Still, I don't have a correct implementation of Leftmost.

[imz]

But think about the following equations:

Dual (M (Dual m1)) <> Dual (split) <> Dual (M (Dual m2))
<>
Dual (M (Dual m3)) <> Dual (split) <> Dual (M (Dual m4))
=
Dual (M (Dual m2) <> split <> M (Dual m1))
<>
Dual (M (Dual m4) <> split <> M (Dual m3))
=
Dual (Dual m2 :| Dual m1)
<>
Dual (Dual m4 :| Dual m3)
=
Dual ((Dual m4 :| Dual m3)
      <>
      (Dual m2 :| Dual m1))
=
Dual ((Dual m4 <> Dual m3 <> Dual m2)
      :|
      Dual m1)
=
Dual (Dual (m2 <> m3 <> m4)
      :|
      Dual m1)

This gives us the split we expected, only the sides of (:|) are
reversed...

I suspect that if we follow this rule in your initial counter-example
expression (by changing the sides of (:|)), we'll get the wanted
result.

So, in a sense, the problem would be in ambiguity of the meaning of
(:|) if it is used for all kinds of splits (as in my utility
function which might return x :| y, but then who knows which part
means what!..)

If we remember that the split that survives is to the right of :|,
we won't confuse things, because if we do a leftmostSplit, then the
split that survives is the left part of the initial input, and it will
be put to the right of :|.

[imz]

In a sense, there is no necessity to add the "leftmost Split" to your library. It can be shipped separately. But probably the world would be more clear, if it is together with your library.

[imz]

It's wrong for my mentioned application, because it throws away the splitting elements from the rest. (Of course!)

Prelude Data.Monoid.Split.Leftmost> leftmostSplit (== '=') "DEBUG=foo=bar"
"foobar" :| "DEBUG"

But it's a valid thing in its own nevertheless. (Remember the rule
that the right component is the part that survives multiple splits.)

[byorgey]

Yes, I agree it makes sense for it to be defined in this package instead of somewhere else. But without a specific use case I am not particularly motivated to do the work to add it. I would happily accept a pull request if you wanted to write such a module. Or we can just leave this ticket here as an idea for someone in the future.

[imz]

So. I have some definition, which I have tried out. But its usefulness is under question -- given the previous comments:

1. the sides are not in the natural order;
2. it's not suitable for the parsing I was thinking of.

Probably, I'll push it (perhaps, as a pull request) just to have it saved and let you and others decide what to do with it.

FYI:

As for my motivating goal, I've implemented it differently (and have not thought about its efficiency):

splitOnLeftmost :: (a -> Bool) -> [a] -> Either [a] ([a],[a])
splitOnLeftmost p = foldl append (Left mempty)
    where append (Right (splitted,rest)) x =
              Right (splitted,rest <> [x])
          append (Left accumulated) x =
              if p x
              then Right (accumulated,mempty)
              else Left (accumulated <> [x])