Another sequence operation

On Sun, Dec 6, 2009 at 5:35 PM, martin odersky <martin.odersky@epfl.ch> wrote:

I have come across several times now across the need to define a
function over traversables with a signature like this:

def findMapped[B](f: A => Option[B]): Option[B]

This method should apply the option-valued function `f` to successive
elements of the collection
until a defined value is found, and return that value, or return None
if `f` returns None for all elements of the collection.

Questions:

1) Is there a simple way to achieve this with the existing
functionality on collections?
2) I believe people have already proposed something like this. Does
anyone know specifics?
3) Would you be in favor of including something like this in the
collection libraries?
4) Is findMapped a good name? I am not sure. Another possibility would
be `firstDefined'. Other suggestions?

I would prefer `findMapped`, or maybe `findDefined`.`firstDefined` makes less sense when faced with collections that don't have a concept of implicit order.  

Cheers

On Sun, Dec 06, 2009 at 06:35:03PM +0100, martin odersky wrote:
> I have come across several times now across the need to define a
> function over traversables with a signature like this:
>
> def findMapped[B](f: A => Option[B]): Option[B]

Note that this is essentially partialMap.headOption. There is an
equivalence between PartialFunction[A, B] and A => Option[B] which we
should openly recognize and try to handle consistently.

pfToOpt(f: PartialFunction[A, B]): A => Option[B] =
x => if (f isDefinedAt x) Some(f(x)) else None

I think partial functions are superior here, and the reverse optToPf is
not so likely to be a smooth transformation since f has to be evaluated
even when the result will be None.

(I'm always afraid to comment on this sort of thing because tony is
going to point out that we're totally blowing it...)

On Sun, Dec 6, 2009 at 7:22 PM, Paul Phillips wrote:
> On Sun, Dec 06, 2009 at 06:35:03PM +0100, martin odersky wrote:
>> I have come across several times now across the need to define a
>> function over traversables with a signature like this:
>>
>> def findMapped[B](f: A => Option[B]): Option[B]
>
> Note that this is essentially partialMap.headOption.  There is an
> equivalence between PartialFunction[A, B] and A => Option[B] which we
> should openly recognize and try to handle consistently.
>
>  pfToOpt(f: PartialFunction[A, B]): A => Option[B] =
>    x => if (f isDefinedAt x) Some(f(x)) else None
>
I agree in principle. But I'd like something that avoids the double
evaluation of `f' (in both directions).

Cheers

On Mon, Dec 07, 2009 at 11:31:35AM +0100, martin odersky wrote:
> I agree in principle. But I'd like something that avoids the double
> evaluation of `f' (in both directions).

I'm totally fine with a function like you described (although I think
naming it "mapFind" makes more what-it-does sense), I was making more of
a general point that we should probably have some strategy regarding
partial functions and option producing methods, lest we end up with a
composition quilt with a patchwork feel.

How does Haskell handles it? Surely they must have something equivalent.

On Sun, Dec 6, 2009 at 3:35 PM, martin odersky <martin.odersky@epfl.ch> wrote:

I have come across several times now across the need to define a
function over traversables with a signature like this:

def findMapped[B](f: A => Option[B]): Option[B]

This method should apply the option-valued function `f` to successive
elements of the collection
until a defined value is found, and return that value, or return None
if `f` returns None for all elements of the collection.

Questions:

1) Is there a simple way to achieve this with the existing
functionality on collections?
2) I believe people have already proposed something like this. Does
anyone know specifics?
3) Would you be in favor of including something like this in the
collection libraries?
4) Is findMapped a good name? I am not sure. Another possibility would
be `firstDefined'. Other suggestions?

Cheers

 -- Martin

--
Daniel C. Sobral

I travel to the future all the time.

On Mon, Dec 7, 2009 at 12:45 PM, Paul Phillips wrote:
> On Mon, Dec 07, 2009 at 11:31:35AM +0100, martin odersky wrote:
>> I agree in principle. But I'd like something that avoids the double
>> evaluation of `f' (in both directions).
>
> I'm totally fine with a function like you described (although I think
> naming it "mapFind" makes more what-it-does sense), I was making more of
> a general point that we should probably have some strategy regarding
> partial functions and option producing methods, lest we end up with a
> composition quilt with a patchwork feel.
>
Yes, good point. The first thing we should do is add a method

def lift: A => Option[B] = { x => if (isDefinedAt(x)) Some(x) else None }

to partial functions. That gives us a way to convert one to the other.
We probably should also add a conversion in the other direction, but
not clear yet where and how it should be called.

The next question is whether collection methods should by preference
take partial functions or option-valued functions as parameters. I am
not sure about that one yet.
The main argument for partial functions is easy integration with
pattern matching.

xs partialMap { case P => E }

is a bit nicer than

xs filterMap { case P => Some(E); case _ => None }

or

xs partialMap { case P => E }.lift

Also, partial functions might give better efficiency in some contexts.

The main arguments for option-valued functions are that
1. Types are simpler. A => Option[B] reads better than PartialFunction[A, B].
2. It's easier in general to produce a literal of type A => Option[B]
(unless you do pattern matching anyway).

Btw, why does partialMap take a (pf: PartialFunction[Any, B])
argument? Does that not constrain the type too much? I would use a
(pf: PartialFunction[A, B]) instead.

Cheers

On Mon, Dec 07, 2009 at 05:23:49PM +0100, martin odersky wrote:
> def lift: A => Option[B] = { x => if (isDefinedAt(x)) Some(x) else None }

That is a winner.

> Btw, why does partialMap take a (pf: PartialFunction[Any, B])
> argument? Does that not constrain the type too much? I would use a
> (pf: PartialFunction[A, B]) instead.

That's how I originally did it. I ended up changing it because, if I
remember correctly, contravariance and type inference don't mix. There
was some very common situation where I had to write noisy extra code all
the time, which went away by using Any. I didn't like it then or now, I
agree A => B is clearly better in principle. I can try it out again so
I can be more specific.

On 07.12.2009, at 17:23, martin odersky wrote:

> def lift: A => Option[B] = { x => if (isDefinedAt(x)) Some(x) else None }
>
> to partial functions. That gives us a way to convert one to the other.
> We probably should also add a conversion in the other direction, but
> not clear yet where and how it should be called.

how about adding

def unapply(x: A): Option[B] = { if (isDefinedAt(x)) Some(apply(x)) else None }

instead (assuming the apply was missing from your lift definition) ?

This would enable some other useful things:

val OuterEnv = { case "myVar" => 7 }

val Env = { case "myOtherVar" => 8 } orElse OuterEnv

expr match {
case Var(Env(x)) => x
...
}

somePartialFun.lift would then become somePartialFun.unapply _

> The next question is whether collection methods should by preference
> take partial functions or option-valued functions as parameters. I am
> not sure about that one yet.
> The main argument for partial functions is easy integration with
> pattern matching.
>
> xs partialMap { case P => E }
>
> is a bit nicer than
>
> xs filterMap { case P => Some(E); case _ => None }
>
> or
>
> xs partialMap { case P => E }.lift

I think it's not only a bit nicer, but a clear win clarity wise. Personally, I see a large number of use cases for partialMap in my code, and I think partialFind would also be very useful.

> Also, partial functions might give better efficiency in some contexts.

It might also be worth considering to make the compiler generate unapply/lift in the same manner as isDefinedAt. Avoiding the duplicate pattern matching should be beneficial for cases like partialMap when the pattern is complex, e.g. with deeply nested extractors as in the Env example above.

Cheers,
- Tiark

On Mon, Dec 7, 2009 at 6:43 PM, Tiark Rompf wrote:
>
> On 07.12.2009, at 17:23, martin odersky wrote:
>
>>  def lift: A => Option[B] = { x => if (isDefinedAt(x)) Some(x) else None }
>>
>> to partial functions. That gives us a way to convert one to the other.
>> We probably should also add a conversion in the other direction, but
>> not clear yet where and how it should be called.
>
> how about adding
>
>        def unapply(x: A): Option[B] = { if (isDefinedAt(x)) Some(apply(x)) else None }
>
> instead (assuming the apply was missing from your lift definition) ?
>
> This would enable some other useful things:
>
>        val OuterEnv = { case "myVar" => 7 }
>
>        val Env = { case "myOtherVar" => 8 } orElse OuterEnv
>
>        expr match {
>                case Var(Env(x)) => x
>                ...
>        }
>
> somePartialFun.lift would then become somePartialFun.unapply _
>
I think the unapply is very nice. I'd probably leave the lift as well,
because it is easier to understand what it is, and I do not need the
trailing _.

Cheers

Please don't be afraid; my occasional non-constructive comments are
mostly a letting of frustration with necessary exaggeration rather than
anything you should consider.

Note that your function: A => Option[B] is equivalent to an instance of:
case class Kleisli[M[_], A, B](f: A => M[B])
which has a nice and often useful composition function:
def >=>[C](k: Kleisli[M, B, C])(implicit m: Monad[M]): Kleilsi[M, A, C]

This particular data type has become even more useful with the new type
constructor inference.

If you must know, the most appropriate way I know to write this function
is with a monadic find (aka findM). I use this function a lot too, but
not just in its 'Option' form.

def findM[M[_], T[_], A, B](t: T[A], p: A => M[B])(implicit m: Monad[M],
r: Traversable[T]): M[B]

Off the top of my head, I don't know if Traversable is a required
restriction on T (perhaps Foldable is enough?). Also, clearly one may
replace the 'p' argument with Kleisli[M, A, B] or perhaps even define
this method on Kleisli.

If it's not in Scalaz trunk, it will be at release. We generalise these
things :)

Paul Phillips wrote:
> On Sun, Dec 06, 2009 at 06:35:03PM +0100, martin odersky wrote:
>
>> I have come across several times now across the need to define a
>> function over traversables with a signature like this:
>>
>> def findMapped[B](f: A => Option[B]): Option[B]
>>
>
> Note that this is essentially partialMap.headOption. There is an
> equivalence between PartialFunction[A, B] and A => Option[B] which we
> should openly recognize and try to handle consistently.
>
> pfToOpt(f: PartialFunction[A, B]): A => Option[B] =
> x => if (f isDefinedAt x) Some(f(x)) else None
>
> I think partial functions are superior here, and the reverse optToPf is
> not so likely to be a smooth transformation since f has to be evaluated
> even when the result will be None.
>
> (I'm always afraid to comment on this sort of thing because tony is
> going to point out that we're totally blowing it...)
>
>