Subject: Re: comprehensions and Seq[T] - msg#00038

Previous Message by Date: click to view message preview

Re: comprehensions and Seq[T]

Jamie Webb wrote: On Thu, Aug 24, 2006 at 09:19:30AM +0200, martin odersky wrote: Judson, Ross wrote: 1) def flatmap[K](f: T => This[K]): This[K] 2) def flatmap[K](f: T => Seq[K]): This[K] 3) def flatmap[K](f: T => Seq[K]): Seq[K] That's an excellent summary of the design decisions. For the reasons you also give, I would prefer 2). (1) is too restrictive and (3) looses information about the concrete type. What do other people think? I'd have thought it most valuable to have the result type of flatMap be the result type of f, because that gives the most flexibility to maximise efficiency and/or the operations available. OK, so we need the following type: def flatMap[S[a] <: Seq[a], K](f: T => S[K]): S[K] (all this assumes that we can express higher-kinded types, of course. Right now we can't. -- Martin

Next Message by Date: click to view message preview

Re: comprehensions and Seq[T]

Martin Odersky <martin.odersky@xxxxxxx> writes: > Jamie Webb wrote: > > On Thu, Aug 24, 2006 at 09:19:30AM +0200, martin odersky wrote: > > > >>Judson, Ross wrote: > >> > >>>1) def flatmap[K](f: T => This[K]): This[K] > >>> > >>>2) def flatmap[K](f: T => Seq[K]): This[K] > >>> > >>>3) def flatmap[K](f: T => Seq[K]): Seq[K] > >>> > >>> > >> > >> That's an excellent summary of the design decisions. For the > >> reasons you also give, I would prefer 2). (1) is too restrictive > >> and (3) looses information about the concrete type. What do other > >> people think? > > I'd have thought it most valuable to have the result type of flatMap > > be the result type of f, because that gives the most flexibility to > > maximise efficiency and/or the operations available. > > > OK, so we need the following type: > > def flatMap[S[a] <: Seq[a], K](f: T => S[K]): S[K] > > (all this assumes that we can express higher-kinded types, of > course. Right now we can't. There is a gotcha: the result type of these functions is not always the same as the starting type. If you call map on a TreeSet, the result cannot always be a TreeSet because the items might not be comparable. If you call filter on an IntegerInterval, the result cannot always be an Interval because the resulting sequence might include gaps. flatMap has even more degrees of freedom: there is f's return type, and there is the method's return type. The idea of using f's return type for the method's return type sounds nice, except that, yet again, we need to remember that concatenating sequences does not always result in a new sequence of the same kind. IntegerInterval yet again provides a counterexample. Finally, I notice there is a subseq method in Seq. It, too, could use its own specialized result type.... different from all the others, in some cases. For example, in IntegerInterval, subseq is the only method that returns a This! Putting all this together, we get something like: MapResult[K] <: Seq[K] FilterResult <: Seq[T] Concat <: Seq[T] Subseq <: Seq[T] def map[K](f: T=>K): MapResult[K] def filter(f: T=>Boolean): FilterResult def subseq(from: int, to: int): Subseq def flatMap[S <: Seq[K], K](f: T => S): S#Concat // legal? def concat(others: Seq[T]): Concat Five methods and four result type variables. It seems that, in the general case, typing for sequence methods is not all that regular. I really wonder if it isn't worth leaving out most of these type variables and having more methods return unrestricted Seq's? I would axe MapResult the first, and change it to just Seq[T]. But I digress.... -Lex

Previous Message by Thread: click to view message preview

Re: comprehensions and Seq[T]

Jamie Webb wrote: On Thu, Aug 24, 2006 at 09:19:30AM +0200, martin odersky wrote: Judson, Ross wrote: 1) def flatmap[K](f: T => This[K]): This[K] 2) def flatmap[K](f: T => Seq[K]): This[K] 3) def flatmap[K](f: T => Seq[K]): Seq[K] That's an excellent summary of the design decisions. For the reasons you also give, I would prefer 2). (1) is too restrictive and (3) looses information about the concrete type. What do other people think? I'd have thought it most valuable to have the result type of flatMap be the result type of f, because that gives the most flexibility to maximise efficiency and/or the operations available. OK, so we need the following type: def flatMap[S[a] <: Seq[a], K](f: T => S[K]): S[K] (all this assumes that we can express higher-kinded types, of course. Right now we can't. -- Martin

Next Message by Thread: click to view message preview

Re: comprehensions and Seq[T]

Martin Odersky <martin.odersky@xxxxxxx> writes: > Jamie Webb wrote: > > On Thu, Aug 24, 2006 at 09:19:30AM +0200, martin odersky wrote: > > > >>Judson, Ross wrote: > >> > >>>1) def flatmap[K](f: T => This[K]): This[K] > >>> > >>>2) def flatmap[K](f: T => Seq[K]): This[K] > >>> > >>>3) def flatmap[K](f: T => Seq[K]): Seq[K] > >>> > >>> > >> > >> That's an excellent summary of the design decisions. For the > >> reasons you also give, I would prefer 2). (1) is too restrictive > >> and (3) looses information about the concrete type. What do other > >> people think? > > I'd have thought it most valuable to have the result type of flatMap > > be the result type of f, because that gives the most flexibility to > > maximise efficiency and/or the operations available. > > > OK, so we need the following type: > > def flatMap[S[a] <: Seq[a], K](f: T => S[K]): S[K] > > (all this assumes that we can express higher-kinded types, of > course. Right now we can't. There is a gotcha: the result type of these functions is not always the same as the starting type. If you call map on a TreeSet, the result cannot always be a TreeSet because the items might not be comparable. If you call filter on an IntegerInterval, the result cannot always be an Interval because the resulting sequence might include gaps. flatMap has even more degrees of freedom: there is f's return type, and there is the method's return type. The idea of using f's return type for the method's return type sounds nice, except that, yet again, we need to remember that concatenating sequences does not always result in a new sequence of the same kind. IntegerInterval yet again provides a counterexample. Finally, I notice there is a subseq method in Seq. It, too, could use its own specialized result type.... different from all the others, in some cases. For example, in IntegerInterval, subseq is the only method that returns a This! Putting all this together, we get something like: MapResult[K] <: Seq[K] FilterResult <: Seq[T] Concat <: Seq[T] Subseq <: Seq[T] def map[K](f: T=>K): MapResult[K] def filter(f: T=>Boolean): FilterResult def subseq(from: int, to: int): Subseq def flatMap[S <: Seq[K], K](f: T => S): S#Concat // legal? def concat(others: Seq[T]): Concat Five methods and four result type variables. It seems that, in the general case, typing for sequence methods is not all that regular. I really wonder if it isn't worth leaving out most of these type variables and having more methods return unrestricted Seq's? I would axe MapResult the first, and change it to just Seq[T]. But I digress.... -Lex