- About Scala
- Documentation
- Code Examples
- Software
- Scala Developers
Fwd: what it means to contain something
The following mail was accidentally sent to Viktor only.
I have just committed a patch that changes WithDefault.get.
I think it's the right thing and that the previous behavior can be
classified as a bug. So I would argue there are no migration issues --
since `m get k' was the same as `Some(m apply k)', nobody who depended
on that behavior would have called it. They would have called `apply'
directly. And nobody would have used a constant `contains' either.
Cheers
Re: what it means to contain something
What if you don't know what the default behavior of your map is (i.e. you want to abstract the two behaviors)? Needing to know hidden details like whether a default is present seems like a bad idea when one is trying to write safe code.
In particular, there are various mental models of how "get" and "apply" and "contains" are related to each other. For a normal map, we have the behavior
contains get apply
key present true Some(value) value
key absent false None exception
from which we could infer either of the following:
x.get(key) == (if (x contains key) x(key) else None)
x.get(key) == try { Some(x(key)) }
catch { case NoSuchElementException => None }
I'm not going to say which is wrong, but I do think that it's not unreasonable to intuit either case, since they are for all practical purposes equivalent for a map without defaults. Now we add defaults and get
contains get apply
key present true Some(value) value
key absent false ??? default
Clearly, if there's a default then apply had better return it. And it also seems peculiar that if the entry isn't really in the map that contains shouldn't return it. So, what to do about get? If you intuited the first case--get is a shorthand for testing occupancy of the map--then you will probably intuit that you will still get None. If you intuited the second case--get is a shorthand for mapping apply failures into None--then you will probably intuit that you will get Some(default).
I would argue that the latter interpretation is the slightly more natural one, in that it is unexpected that something could be gotten with an apply but not with a get, even if on closer examination there's a good argument to be made that get really shouldn't return the default value since there is nothing really there to return, and all the other methods that query for whether something is there correctly report only those things that are truly there, not those we only asked for.
--Rex
Re: what it means to contain something
On Thu, Feb 10, 2011 at 3:05 PM, Rex Kerr wrote:
> On Thu, Feb 10, 2011 at 8:27 AM, martin odersky
> wrote:
>>
>> So I would argue there are no migration issues --
>>
>> since `m get k' was the same as `Some(m apply k)', nobody who depended
>> on that behavior would have called it. They would have called `apply'
>> directly. And nobody would have used a constant `contains' either.
>
> What if you don't know what the default behavior of your map is (i.e. you
> want to abstract the two behaviors)? Needing to know hidden details like
> whether a default is present seems like a bad idea when one is trying to
> write safe code.
>
> In particular, there are various mental models of how "get" and "apply" and
> "contains" are related to each other. For a normal map, we have the
> behavior
>
> contains get apply
> key present true Some(value) value
> key absent false None exception
>
> from which we could infer either of the following:
>
> x.get(key) == (if (x contains key) x(key) else None)
> x.get(key) == try { Some(x(key)) }
> catch { case NoSuchElementException => None }
>
The problem with that reasoning is that contains and apply are defined
in terms of get and default, not the other way round. And that's not
an implementation detail: get is part of the implementation interface
of a map in that it is an abstract method.
Cheers
Re: what it means to contain something
On 2/10/11 6:56 AM, martin odersky wrote:
> The problem with that reasoning is that contains and apply are defined
> in terms of get and default, not the other way round. And that's not
> an implementation detail: get is part of the implementation interface
> of a map in that it is an abstract method.
Although I fully agree that there is no obviously correct answer when
considered as a black box, I think this is the runaway reasoning winner
when we have to deal with what is. The abstract method from which all
else is derived is get. So get must communicate something meaningful
for the other pieces to fall into place. get is where this distinction
should be drawn.
I also agree with everyone about the impact: that it makes no sense to
have been relying on the behavior of get or contains in the presence of
a default, and that people will have been (unintentionally or otherwise)
anyway. So changing get and adding a migration warning looks the best
to me.
That, and polishing up and better advertising the existence of
migration. It's my fault, but for 2.8.x I think you had to be pretty
plugged in to be aware of it.
Re: what it means to contain something
I'm concerned that the most likely place for something to go wrong is maps with defaults being passed to code that expects maps. The code being called might well use get or contains, because it doesn't rely on map having a default, and the migration warning will be useless to deal with it.
I'd rather the migration warning is also put on WithDefault itself, or perhaps the withDefault/withDefaultValue methods, or wherever it can be seen by anyone using a map with default.
--
Daniel C. Sobral
I travel to the future all the time.
Re: what it means to contain something
Indeed. And more than that: get has always been a safe apply, but now for Map withDefault you have to use apply instead to get default values. How can one write polymorphic code that handles either Map with or without withDefault? get no longer gets, it gets only non-default values, and there's no safe way to get either default or non-default values. That's untenable semantics. It seems to me that you are forced to go with something like Kevin's getNonDefault suggestion, and define apply and contains in terms of that, rather than get.
-- Jim
Re: what it means to contain something
Sorry, only contains needs to be defined in terms of getNonDefault; apply would still be defined in terms of get. OTOH, if get is redefined in withDefault to return None when there's no non-default value, apply must also be redefined there.
Re: what it means to contain something
1) I would recommend against introducing two versions of withDefault.
This automatically means having to define the following 4 methods in the
base collections package: withStrongDefault, withStrongDefaultValue,
withWeakDefault, withWeakDefaultValue.
Then, it means redefining all 4 in the mutable and immutable packages,
and this seems like a lot of logic.
The second reason is the added complexity - it may be hard to pick up
the right with*Default and be aware of what it means - should we have
distinct subtypes for weak and strong defaults as well? I'm not sure
what would be the gains.
2) I agree that once a programmer creates a map with a default, he
should not call a constant `contains` or `get` for that matter. But if
converted to a plain `Map[T]` and fed to existing code which may depend
on the fact that if `contains` is `false`, `apply` will throw, it will
break things.
3) I would recommend against the 3-state return type or using the
exception mechanism to distinguish between the cases. This seems like a
lot of magic. I believe things should be kept simple, but that's just me.
My concerns are - breaking existing code. Places where that could happen
include default maps. The question is how often default maps were used.
I would say not that often, but I don't really know for sure. It might
be safe to make the change with a migration warning.
After reading it carefully, I agree with Martin's proposal. I think it
makes sense, as it could only break the use of default maps in existing
code.
So, I propose the following:
a) deprecate default maps altogether, and define a new type of default
maps, say `DefaultedMap` (or whatever name is appropriate) which are
implemented according to the latest changes which change the semantics
of `get` and `contains`. Then add `withDefaulted*` methods to create
such maps.
[optionally] b) Add a marker method to distinguish a map which has a
default value.
c) Finally, clearly document the contract for the new `DefaultedMap`s,
and use them forever after.
Effects: existing code involving `withDefault` will still work but get a
deprecation warning.
Any new code will use `withDefaulted` (or whatever the name) and rely on
the new contract.
[optionally] And users of maps can programatically check what they're
dealing with.
The only problem may still, however, be with the "legacy" code mentioned
above in 2), which deals with the `Map` interface and may not be
written with awareness of the new well documented connection between
`contains`, `apply` and `get`.
But, we such code would need to be changed anyway.
Cheers,
Alex
P.S. Martin, what did you mean by iterators being defined in terms of
"get+default"? Did you mean that they iterate over the pairs with keys
for which get does not return a `None` (and the same for `keySet`)? This
was my understanding.
Re: what it means to contain something
On 2/10/11 10:29 AM, Daniel Sobral wrote:
> I'm concerned that the most likely place for something to go wrong is
> maps with defaults being passed to code that expects maps. The code
> being called might well use get or contains, because it doesn't rely on
> map having a default, and the migration warning will be useless to deal
> with it.
Really the more I chew on it the more nervous it makes me. I feel good
that it is the right change to make, but I would like to feel a lot
better about the possible impact on existing code.
Re: what it means to contain something
Some observations:a) The scaladoc for `MapLike.contains` says nothing about defaults and how they affect the return value of `contains`.
b) I think that more than a few programmers would consider `get` to be a "safe" version of `apply` (i.e., one that never throws an exception), so it is somewhat non-intuitive that when `get` returns None, `apply` might still return a value. If this this intuition is false, then it is clumsy to uniformly use a map which may or may not have a default value. (Is there a way other than trying to `apply` and then catching the possible exception?)
c) The scaladoc for `get` does not mention default values. Since the implementation of `get` previously did use defaults, then there is probably some code that depends on this. d) A migration warning is insufficient! As Daniel mentioned, a client may pass a map with a default value to library code that is supposed to be agnostic about default values. So, the migration warning would need to be extremely non-local in order to catch all cases (and afaik the current migration warning infrastructure does not even handle such analyses.)
Therefore, I propose two solutions, in order of preference:1) `contains` should stay as it is, as a constant function. a) There could be an additional method to test containment not considering default. (I believe Paul had some pithy suggestion.)
b) Such a method is not added.
2) `contains` returns true iff the map contains an actual binding for the key (i.e., not considering defaults). However, `get` will always return `Some` if a map has a default. One downside is that the implementation of `contains` must change. But, the interface of `contains` is currently not clear on the fact that its behavior is defined in terms of `get`--so this is not a clear interface vs. implementation issue.
I would *strongly* prefer to go back to state (1b) rather than have `get` ignore defaults and potentially break lots of code.
Donna
On Thursday, February 10, 2011 7:50:34 PM UTC+1, Paul Phillips wrote:
Re: what it means to contain something
On Thu, Feb 17, 2011 at 11:55 AM, Donna Malayeri wrote:
> I strongly agree with both Paul and Daniel. I brought up the topic in
> Tuesday's LAMP meeting to see if any others were also concerned with the
> recent commit, and this was indeed the case.
>
> Some observations:
> a) The scaladoc for `MapLike.contains` says nothing about defaults and how
> they affect the return value of `contains`.
> b) I think that more than a few programmers would consider `get` to be a
> "safe" version of `apply` (i.e., one that never throws an exception), so it
> is somewhat non-intuitive that when `get` returns None, `apply` might still
> return a value. If this this intuition is false, then it is clumsy to
> uniformly use a map which may or may not have a default value. (Is there a
> way other than trying to `apply` and then catching the possible exception?)
> c) The scaladoc for `get` does not mention default values. Since the
> implementation of `get` previously did use defaults, then there is probably
> some code that depends on this.
> d) A migration warning is insufficient! As Daniel mentioned, a client may
> pass a map with a default value to library code that is supposed to be
> agnostic about default values. So, the migration warning would need to be
> extremely non-local in order to catch all cases (and afaik the current
> migration warning infrastructure does not even handle such analyses.)
> Therefore, I propose two solutions, in order of preference:
> 1) `contains` should stay as it is, as a constant function.
> a) There could be an additional method to test containment not
> considering default. (I believe Paul had some pithy suggestion.)
> b) Such a method is not added.
> 2) `contains` returns true iff the map contains an actual binding for the
> key (i.e., not considering defaults). However, `get` will always return
> `Some` if a map has a default. One downside is that the implementation of
> `contains` must change. But, the interface of `contains` is currently not
> clear on the fact that its behavior is defined in terms of `get`--so this is
> not a clear interface vs. implementation issue.
>
> I would *strongly* prefer to go back to state (1b) rather than have `get`
> ignore defaults and potentially break lots of code.
+1
> Donna
> On Thursday, February 10, 2011 7:50:34 PM UTC+1, Paul Phillips wrote:
>>
>> On 2/10/11 10:29 AM, Daniel Sobral wrote:
>> > I'm concerned that the most likely place for something to go wrong is
>> > maps with defaults being passed to code that expects maps. The code
>> > being called might well use get or contains, because it doesn't rely on
>> > map having a default, and the migration warning will be useless to deal
>> > with it.
>>
>> Really the more I chew on it the more nervous it makes me. I feel good
>> that it is the right change to make, but I would like to feel a lot
>> better about the possible impact on existing code.
>
Re: what it means to contain something
I believe it's a matter of concenptual simplicity.
In my change proposal
- a map consists of a finite set of key/value pairs, plus a default
expression (which itself is by default { throw new
NoSuchElementException })
- get is the characteristic function of a map: it gives you Some(v)
where v is the value associated with a key if present, None otherwise.
- apply, contains, keySet, iterator are all defined by simple
operations over this model, which is given by get + default.
- withDefault is the same as creating a new map and overriding the
default method.
I have not seen a proposal that accounts for all of
get/apply/keySet/iterator/withDefault/override default without
complicating matters greatly.
Complicated is bad, so we should simplify.
The problem is obviously backwards compatibility. But the time window
where we had withDefault was fairly small, AFAIK it was introduced in
2.8.
So I really hope it is possible to correct now, without being caught
in the legacy tarpit.
Cheers
Re: what it means to contain something
>>>>> "martin" == martin odersky writes:
martin> The problem is obviously backwards compatibility. But the time
martin> window where we had withDefault was fairly small, AFAIK it was
martin> introduced in 2.8.
2.7 didn't have withDefault, but it did have withDefaultValue:
Welcome to Scala version 2.7.7.final (Java HotSpot(TM) 64-Bit Server VM, Java 1.6.0_22).
scala> Map(1 -> 2).withDefaultValue(5).apply(3)
res0: Int = 5
scala> Map(1 -> 2).withDefaultValue(5).contains(3)
res2: Boolean = false
scala> Map(1 -> 2).withDefaultValue(5).get(3)
res1: Option[Int] = None
On 2.8 the last answer is instead Some(3).
Re: what it means to contain something
And the second is true:
Welcome to Scala version 2.8.1.final (Java HotSpot(TM) 64-Bit Server VM, Java 1.6.0_22).
Type in expressions to have them evaluated.
Type :help for more information.
scala> Map(1 -> 2).withDefaultValue(5).apply(3)
res3: Int = 5
scala> Map(1 -> 2).withDefaultValue(5).contains(3)
res4: Boolean = true
scala> Map(1 -> 2).withDefaultValue(5).get(3)
res5: Option[Int] = Some(5)
--
Daniel C. Sobral
I travel to the future all the time.
Re: what it means to contain something
Perhaps we should think about what a Map is on a higher level first.
Looking at the ScalaDocs of MapLike a Map is both:
1. something which associates keys with values (manifested by
inheriting PartialFunction[A, B])
2. a list of (key, value) bindings (manifested by inheriting
IterableLike[(A, B)])
Classifying the methods in questions two one of those two traits of a
Map by their current Scaladoc descriptions:
apply => 1 "Retrieves the value which is associated with the given
key." (Function1)
get => 1 "Optionally returns the value associated with a key" (MapLike)
contains => 2 "Tests whether this map contains a binding for a key." (MapLike)
isDefinedAt => 2 "Tests whether this map contains a binding for a key.
This method [...] is equivalent to contains" (PartialFunction)
filter => 2 "Selects all elements of this map which satisfy a predicate"
keySet => 2 "Collects all keys of this map in a set."
Just by looking at this list, you can see one possible conflict in the
definition of apply and isDefinedAt, which are both methods of
PartialFunction and which only work correctly if the relation between
Traits A and B is fixed, so that there exists a binding for each
possible association. IMO, implicitly, that's a promise which the
trait MapLike makes (and as I understood Martin, which should be kept
by refering to MapLike being defined in terms of `get`).
Obviously, a map with default values can't fulfill this promise and as
such shouldn't inherit from MapLike in its current form.
I have no constructive suggestion yet, but I don't think this problem
is solvable solely by focusing on fixing singular points which may
fail without thinking generally about the things that can fail when
one uses a Map as one of the things it represents by inheritance. IMO
multiple inheritance gone wrong is at the heart of this issue.
Johannes
On Thu, Feb 17, 2011 at 7:22 PM, Daniel Sobral wrote:
> On Thu, Feb 17, 2011 at 16:09, Seth Tisue wrote:
>>
>> >>>>> "martin" == martin odersky writes:
>>
>> martin> The problem is obviously backwards compatibility. But the time
>> martin> window where we had withDefault was fairly small, AFAIK it was
>> martin> introduced in 2.8.
>>
>> 2.7 didn't have withDefault, but it did have withDefaultValue:
>>
>> Welcome to Scala version 2.7.7.final (Java HotSpot(TM) 64-Bit Server VM,
>> Java 1.6.0_22).
>> scala> Map(1 -> 2).withDefaultValue(5).apply(3)
>> res0: Int = 5
>> scala> Map(1 -> 2).withDefaultValue(5).contains(3)
>> res2: Boolean = false
>> scala> Map(1 -> 2).withDefaultValue(5).get(3)
>> res1: Option[Int] = None
>>
>> On 2.8 the last answer is instead Some(3).
>
> And the second is true:
>
> Welcome to Scala version 2.8.1.final (Java HotSpot(TM) 64-Bit Server VM,
> Java 1.6.0_22).
> Type in expressions to have them evaluated.
> Type :help for more information.
>
> scala> Map(1 -> 2).withDefaultValue(5).apply(3)
> res3: Int = 5
>
> scala> Map(1 -> 2).withDefaultValue(5).contains(3)
> res4: Boolean = true
>
> scala> Map(1 -> 2).withDefaultValue(5).get(3)
> res5: Option[Int] = Some(5)
>
> --
> Daniel C. Sobral
>
> I travel to the future all the time.
>
Re: what it means to contain something
I've also had this line of thinking.
First of all. The fact that this thread hasn't reached an obvious
conclusion yet is evidence that a map with default doesn't really make
sense.
Lets say that the difference between Map and a Function is the
cardinality of the underlying sets. As Martin said: a Map is a
_finite_ Set. A Map with default puts the map in infinite territory so
it can't really be a Map.
If we turn it around and instead focus on the default we get a
Function (infinite set) with a finite set of overrides (the Map).
I would guess that the usefulness of a Map, compared to a Function,
comes from the fact that it's definition can be inspected (iterated
even).
So maybe the solution is to create a notion of FunctionWithOverrides
from which the overrides can be inspected?
But then again. I can imagine that the original use case for a Map
with default actually had nothing to do with the infinite properties
of the default function. I assume that the actual use case was
concerned with a very limited (finite) subset of keys that just hadn't
been defined yet.
I can imagine few other approaches to this problem, (than to define a
default value on the Map as such).
a) Extract all relevant keys from the problem and make the initial
state of the map complete.
b) Don't read values from a map at all. Collect the update operations
per key, and reduce them using a fold in a second step.
c) Optimize b whit a combined map and reduce step.
So maybe the fix to this problem is to just remove the default thing
from map, and instead focus on the surrounding API to supply other
building blocks for the problem to be solved.
BR,
John
On Fri, Feb 18, 2011 at 11:29 AM, Johannes Rudolph
wrote:
> Perhaps we should think about what a Map is on a higher level first.
>
> Looking at the ScalaDocs of MapLike a Map is both:
> 1. something which associates keys with values (manifested by
> inheriting PartialFunction[A, B])
> 2. a list of (key, value) bindings (manifested by inheriting
> IterableLike[(A, B)])
>
> Classifying the methods in questions two one of those two traits of a
> Map by their current Scaladoc descriptions:
>
> apply => 1 "Retrieves the value which is associated with the given
> key." (Function1)
> get => 1 "Optionally returns the value associated with a key" (MapLike)
> contains => 2 "Tests whether this map contains a binding for a key." (MapLike)
> isDefinedAt => 2 "Tests whether this map contains a binding for a key.
> This method [...] is equivalent to contains" (PartialFunction)
> filter => 2 "Selects all elements of this map which satisfy a predicate"
> keySet => 2 "Collects all keys of this map in a set."
>
> Just by looking at this list, you can see one possible conflict in the
> definition of apply and isDefinedAt, which are both methods of
> PartialFunction and which only work correctly if the relation between
> Traits A and B is fixed, so that there exists a binding for each
> possible association. IMO, implicitly, that's a promise which the
> trait MapLike makes (and as I understood Martin, which should be kept
> by refering to MapLike being defined in terms of `get`).
>
> Obviously, a map with default values can't fulfill this promise and as
> such shouldn't inherit from MapLike in its current form.
>
> I have no constructive suggestion yet, but I don't think this problem
> is solvable solely by focusing on fixing singular points which may
> fail without thinking generally about the things that can fail when
> one uses a Map as one of the things it represents by inheritance. IMO
> multiple inheritance gone wrong is at the heart of this issue.
>
> Johannes
>
> On Thu, Feb 17, 2011 at 7:22 PM, Daniel Sobral wrote:
>> On Thu, Feb 17, 2011 at 16:09, Seth Tisue wrote:
>>>
>>> >>>>> "martin" == martin odersky writes:
>>>
>>> martin> The problem is obviously backwards compatibility. But the time
>>> martin> window where we had withDefault was fairly small, AFAIK it was
>>> martin> introduced in 2.8.
>>>
>>> 2.7 didn't have withDefault, but it did have withDefaultValue:
>>>
>>> Welcome to Scala version 2.7.7.final (Java HotSpot(TM) 64-Bit Server VM,
>>> Java 1.6.0_22).
>>> scala> Map(1 -> 2).withDefaultValue(5).apply(3)
>>> res0: Int = 5
>>> scala> Map(1 -> 2).withDefaultValue(5).contains(3)
>>> res2: Boolean = false
>>> scala> Map(1 -> 2).withDefaultValue(5).get(3)
>>> res1: Option[Int] = None
>>>
>>> On 2.8 the last answer is instead Some(3).
>>
>> And the second is true:
>>
>> Welcome to Scala version 2.8.1.final (Java HotSpot(TM) 64-Bit Server VM,
>> Java 1.6.0_22).
>> Type in expressions to have them evaluated.
>> Type :help for more information.
>>
>> scala> Map(1 -> 2).withDefaultValue(5).apply(3)
>> res3: Int = 5
>>
>> scala> Map(1 -> 2).withDefaultValue(5).contains(3)
>> res4: Boolean = true
>>
>> scala> Map(1 -> 2).withDefaultValue(5).get(3)
>> res5: Option[Int] = Some(5)
>>
>> --
>> Daniel C. Sobral
>>
>> I travel to the future all the time.
>>
>
>
>
> --
> Johannes
>
> -----------------------------------------------
> Johannes Rudolph
> http://virtual-void.net
>
Re: what it means to contain something
The fact that this thread hasn't reach an obvious conclusion is evidence that API changes have practical consequences and that people have different needs for maps, as evidenced by two common objections: it is hard to put sensible migration warnings for this change (practical consequence), and changing both "get" and "contains" remove Map's safe lookup (different needs).
On Sat, Feb 19, 2011 at 16:18, John Nilsson <john [at] milsson [dot] nu> wrote:
--
Daniel C. Sobral
I travel to the future all the time.
Re: what it means to contain something
On Sat, Feb 19, 2011 at 10:23 PM, Daniel Sobral wrote:
> A map with default is a way to abstract away initialization
> of not previously defined relationships as well as remove the need to handle
> relationship-not-present exceptions in certain algorithms.
Which is also what the other half of the mail you responded too concluded.
BR,
John
Re: what it means to contain something
I fully agree. Unfortunately, the solution where apply(x) != get(x).get is complicated. That, I think, is one of the more complicated things to do because it requires a new mental rule where there was previously an equivalence. I don't think the fact that the overridable default method worked this way argues that it's any simpler.
The two invariants that are in conflict are
forall(x) { m.get(x) === m.filter(_._1 == x).headOption }
forall(x) { m.get(x).get === m(x) }
(where "===" is an imaginary operator that tests equality in the case of normal termination, and otherwise returns true if both sides threw an exception).
If we maintain the former, we declare that "get" is intrinsically a collectiony not an elementy type of thing to do, that defaults are elements, and that there exists no safe abstracted way within collections to deal with elements.
If we maintain the latter, we declare that "get" is intrinsically an elementy type of operation, except that it is safe, but that get and collections methods may return different answers.
So really the question is: what is the point of default? Is its sole role to avoid throwing an exception upon a misdirected apply (that is, it's basically a type of error condition)? If yes, this should be documented very clearly, since violating the second invariant I listed is quite a surprise. And even then it's not so useful, because there's no trait that goes along with it, so you just have to try it and find out whether you'll be bitten or not--which is something that I would advise that people avoid as much as possible (reserve for special cases, or defensively against badly-written code that is throwing too many exceptions and thus slowing things down too much).
On Thu, Feb 17, 2011 at 11:26 AM, Paul Phillips <paul [dot] phillips [at] gmail [dot] com> wrote:
That would work, not least because it would be the best documentation possible that this issue exists and that one had better make one's assumptions explicit. I hate to make the API larger, but if it was worth going from one to three methods to make things easier but confusing, it's worth going from three to four or five to make them clear again.
--Rex
Re: what it means to contain something
On Thu, Feb 17, 2011 at 6:22 PM, Rex Kerr wrote:
> On Thu, Feb 17, 2011 at 10:38 AM, martin odersky
> wrote:
>>
>> I believe it's a matter of concenptual simplicity.
>>
>> In my change proposal
>>
>> - a map consists of a finite set of key/value pairs, plus a default
>> expression (which itself is by default { throw new
>> NoSuchElementException })
>>
>> - get is the characteristic function of a map: it gives you Some(v)
>> where v is the value associated with a key if present, None otherwise.
>>
>> - apply, contains, keySet, iterator are all defined by simple
>> operations over this model, which is given by get + default.
>>
>> - withDefault is the same as creating a new map and overriding the
>> default method.
>>
>> I have not seen a proposal that accounts for all of
>> get/apply/keySet/iterator/withDefault/override default without
>> complicating matters greatly.
>>
>> Complicated is bad, so we should simplify.
>
> I fully agree. Unfortunately, the solution where apply(x) != get(x).get is
> complicated. That, I think, is one of the more complicated things to do
> because it requires a new mental rule where there was previously an
> equivalence. I don't think the fact that the overridable default method
> worked this way argues that it's any simpler.
>
Just to clarify:
> The two invariants that are in conflict are
>
> forall(x) { m.get(x) === m.filter(_._1 == x).headOption }
That one does not hold in 2.8.1, but would hold in my proposal.
Another equality like this which does not hold now but would hold in
my proposal is:
m.keySet contains x === m.iterator map (_._1) contains x
> forall(x) { m.get(x).get === m(x) }
>
That one does not hold (either now or in the past), because you can
override default.
> So really the question is: what is the point of default? Is its sole role
> to avoid throwing an exception upon a misdirected apply (that is, it's
> basically a type of error condition)? If yes, this should be documented
> very clearly, since violating the second invariant I listed is quite a
> surprise. And even then it's not so useful, because there's no trait that
> goes along with it, so you just have to try it and find out whether you'll
> be bitten or not--which is something that I would advise that people avoid
> as much as possible (reserve for special cases, or defensively against
> badly-written code that is throwing too many exceptions and thus slowing
> things down too much).
I use default a lot, and think it's very useful. It's precisely if you
do not want to deal with the boilerplate of dealing with missing
elements because keys you
know a good default value. An example is any map of keys to sets of
values. It makes perfect sense to associate the empty set with every
missing key. Dealing with such a much is much smoother than having to
deal with missing keys explicitly.
Cheers
Re: what it means to contain something
Well, get is defined like this:
def get(key: A) = underlying.get(key) orElse Some(default(key))
So I don't see how overriding default would change that equation.
In any case, I have two main concerns:
1. There must be a "safe apply" method on Map which can be fed a Map.WithDefault, otherwise the usefulness of Map decreases a lot.
To me, "contains" and "get", as they are today, are just right. That an iterable will not contain all keys is unfortunate, but I'd rather solve this in some other fashion (ie, introducing methods that ignore defaults). Still, if a safe-get and defaulted-contains gets introduced in Map, I can live with that.
2. As the change currently stands, not everyone who needs them will get the migration warnings. For example:
val m: Map[Int, Int] = Map(1 -> 2).withDefault(_+1)
m.get(0)
On the other hand, the same change _already_ happened from 2.7 to 2.8, as Seth Tisue just pointed out, and neither of these two points (in reverse) were addressed then.
--
Daniel C. Sobral
I travel to the future all the time.
Re: what it means to contain something
`get` would still ignore defaults and `contains` would still recognise them. There's then no need to change any existing methods, and we won't have to rely on exceptions as an expected return value.
keySet and iterator should also be ignorant to default values. Given some Map[Int,T], where would such an iterator start? The only possibility would have to be Int.MinValue, for a Map keyed on an unbounded Ref type there's no valid answer.
On 17 February 2011 15:38, martin odersky <martin [dot] odersky [at] epfl [dot] ch> wrote:
Re: what it means to contain something
It seems to me that the semantics of a "default map" are confusing and
inconsistent, no matter what compromises are being discussed on the
list. That probably stems from the fact that the current
implementation changes the behavior of existing methods, instead of
only adding new methods. I think the Liskov substitution principle
applies here.
Therefore I am in favor of changing the default map trait so that it
only adds additional methods with default semantics, instead of
changing any of the preexisting methods.
Regards,
Ruediger
Re: what it means to contain something
That said, adding one of your proposed methods might be a good option, say `getOrDefault` (i.e., your `defaultAwareGet`). This would be like a safe `apply`, which would return None if no default were set.
Martin, I have changed my mind and I now agree with you--I had thought that withDefault had been introduced prior to 2.8. However, it would be nice to add support for defaults somewhere in the Map interface, such as by adding `getOrDefault.` (Obviously anyone can write such a method in a subclass, but having it in the interface allows all clients to use consider a map's default value if they wish to, without having to use `apply` and providing an exception handler.)
Donna
On Feb 17, 2011, at 4:58 PM, Kevin Wright wrote:
Re: what it means to contain something
On 17 February 2011 16:12, Donna Malayeri <lindydonna [at] gmail [dot] com> wrote:
I was building on Martin's proposal that `get` should be ignorant of defaults while everything else uses them. (though I believe it's an oversight to suggest that keySet and iterator could be default-aware). Originally I suggested `getNotDefault` and `containsNotDefault` to work alongside the current 2.8.1 behaviour (where `get` does use default values).
Personally, I could live with either the current or Martin's proposed `get` behaviour, just so long as a method exists with the corresponding alternative.
I ruled out `getOrDefault` as a name, it sounds far too much like `getOrElse` - implying that the supplied parameter is the default value to use if get fails.
--
Kevin Wright
gtalk / msn : kev [dot] lee [dot] wright [at] gmail [dot] com kev [dot] lee [dot] wright [at] gmail [dot] commail: kevin [dot] wright [at] scalatechnology [dot] com
vibe / skype: kev.lee.wrightquora: http://www.quora.com/Kevin-Wright
twitter: @thecoda
"My point today is that, if we wish to count lines of code, we should not regard them as "lines produced" but as "lines spent": the current conventional wisdom is so foolish as to book that count on the wrong side of the ledger" ~ Dijkstra
Re: what it means to contain something
No time to write much, but I suggest neither contains nor get should be
aware of defaults, and that the methods we can use to make everyone
happy are
withWeakDefault
withStrongDefault
If it's not obvious, a weak default doesn't register with get and other
non-applies, and a strong default does.
The reason I say neither get nor contains should be aware of defaults is
that the creator of a map is the one who should decide the semantics.
The creator is the one anyway, because if they don't like these methods
they'll just override get, contains, apply, etc.
Re: what it means to contain something
Wouldn't it be possible to drop support for maps with defaults? It seems
that no really convincing solution exists that behaves consistently in
all situations.
Cheer
Stefan
On 02/10/2011 07:50 PM, Paul Phillips wrote:
> On 2/10/11 10:29 AM, Daniel Sobral wrote:
>> I'm concerned that the most likely place for something to go wrong is
>> maps with defaults being passed to code that expects maps. The code
>> being called might well use get or contains, because it doesn't rely on
>> map having a default, and the migration warning will be useless to deal
>> with it.
>
> Really the more I chew on it the more nervous it makes me. I feel
> good that it is the right change to make, but I would like to feel a
> lot better about the possible impact on existing code.
>
Re: what it means to contain something
DOnna
On Feb 10, 2011, at 3:05 PM, Rex Kerr wrote:
Re: what it means to contain something
Something like:
sealed trait GetResult case class Contains extends GetResult case class Default extends GetResult case class Absent extends GetResult
It seems something that would be useful in a few other situations too.
On 10 February 2011 14:38, Donna Malayeri <lindydonna [at] gmail [dot] com> wrote:
--
Kevin Wright
gtalk / msn : kev [dot] lee [dot] wright [at] gmail [dot] comkev [dot] lee [dot] wright [at] gmail [dot] commail: kevin [dot] wright [at] scalatechnology [dot] com
vibe / skype: kev.lee.wrightquora: http://www.quora.com/Kevin-Wright
twitter: @thecoda
READ CAREFULLY. By reading this email, you agree, on behalf of your employer, to release me from all obligations and waivers arising from any and all NON-NEGOTIATED agreements, licenses, terms-of-service, shrinkwrap, clickwrap, browsewrap, confidentiality, non-disclosure, non-compete and acceptable use policies ("BOGUS AGREEMENTS") that I have entered into with your employer, its partners, licensors, agents and assigns, in perpetuity, without prejudice to my ongoing rights and privileges. You further represent that you have the authority to release me from any BOGUS AGREEMENTS on behalf of your employer.
Re: what it means to contain something
On Thu, Feb 10, 2011 at 4:06 PM, Kevin Wright wrote:
> How about a new tri-state return type for Map#get?
> Presumably with an implicit conversion to Option for compatibility...
> Something like:
> sealed trait GetResult
> case class Contains extends GetResult
> case class Default extends GetResult
> case class Absent extends GetResult
> It seems something that would be useful in a few other situations too.
>
Please! Let's not over-design here. Besides get is part of the
implementation contract of map, we can't simply redefine it without
forcing a rewrite of implementations.
Cheers
Re: what it means to contain something
On 10 February 2011 15:13, martin odersky <martin [dot] odersky [at] epfl [dot] ch> wrote:
Re: what it means to contain something
On 2/10/11 8:18 AM, Kevin Wright wrote:
> If we can't split Some(x) as returned from get into two distinct types,
> then how about two distinct methods? 'get' and 'getNonDefault'
> `contains` could undergo the same treatment, producing `containsNonDefault`
>
> That would preserve existing code, keep binary compatibility, not
> over-engineer a new tri-value type, and still allow Map users to
> disambiguate default values if required.
If I'm following the proposed change, you can already write a tri-state
map wrapper.
(map get key) match {
case Some(v) => NotDefault(v)
case _ =>
try DefaultValue(map(v))
catch { case _: NoSuchElementException => Absent }
}
So it throws the occasional slow exception. In a billion years, who's
going to care.
Re: what it means to contain something
On Thu, Feb 10, 2011 at 4:06 PM, Kevin Wright <kev [dot] lee [dot] wright [at] gmail [dot] com> wrote:
Something like this?
http://scala-tools.org/mvnsites-snapshots/liftweb/lift-common/scaladocs/net/liftweb/common/Box.html
--
Viktor Klang,
Code Connoisseur
Work: Scalable Solutions
Code: github.com/viktorklang
Follow: twitter.com/viktorklang
Read: klangism.tumblr.com
Re: Fwd: what it means to contain something
Ooops, this should have gone to the mailing list ....
--------------------------------------------
Hi Martin,
> I have just committed a patch that changes WithDefault.get.
> I think it's the right thing and that the previous behavior can be
> classified as a bug. So I would argue there are no migration issues --
> since `m get k' was the same as `Some(m apply k)', nobody who depended
> on that behavior would have called it. They would have called `apply'
> directly. And nobody would have used a constant `contains' either.
I agree, but I'm not really sure if it wouldn't be reasonable to add a
@migration
annotation to the method describing the change and saying that most
people won't be
affected by it.
Bye,
Simon
Re: Fwd: what it means to contain something
Yes, I agree. Migration warning is good. Paul, can you have a look at it?
Thanks