This page is no longer maintained — Please continue to the home page at www.scala-lang.org

Initial/Terminal Class associated with Generic class

8 replies
calathus
Joined: 2010-03-22,
User offline. Last seen 2 years 28 weeks ago.
Hi,
I had some problem for defining a single instance for empty node. From Scala's type system constraint, it seem difficult to define such object..
I wonder this may be a quite common problem in Scala.

---

In Scala, it is not easy to define a static object which would behave as null in Java or C.
Of course, to some extent, it is possible to use null in Scala for AnyRef, but it is not so powerful as in Java  since Scala class is not always subclass of AnyRef(like case class).

The typical problem arise when we try to define empty object for generic classes.
Often it is defined as following:
class HashMap[A, B] extends Map[A, B]
                       with MapLike[A, B, HashMap[A, B]]
                       with HashTable[A] {
  override def empty: HashMap[A, B] = HashMap.empty[A, B]
...
}
object HashMap extends MutableMapFactory[HashMap] {
  ...
  def empty[A, B]: HashMap[A, B] = new HashMap[A, B]
}
It is going to create different empty objects each time when empty is invoked.

it cannot use a single shared object like following pseudo code would:
object HashMap extends MutableMapFactory[HashMap] {
  val empty = HashMap[_, _].initial // initial should be defined for the type constructor itself!
  def empty[A, B]: HashMap[A, B] = empty
}
This initial should have similar type behavior as null, namely empty can be assigned to any val/var of type HashMap[A, B]. but it should cause type error when it is assigned to var of other type like List. e.g:
val A:  HashMap[Int, Int] = HashMap[_, _].initial //OK
val A:  HashMap[Float, Int] = HashMap[_, _].initial //OK
val A:  TreeMap[Float, Int] = HashMap[_, _].initial // fail
In TreeMap(RedBlack), this was achieved by introducing variance for Value
abstract class Tree[+B] {...}case object Empty extends Tree[Nothing] {...}
But this approach cannot be used for mutable TreeMap where variance cannot be used.

Are there any thought for this kind of problem??

Cheers,
calathus

http://scalathus.blogspot.com
Archontophoenix
Joined: 2010-02-04,
User offline. Last seen 2 years 35 weeks ago.
RE: Initial/Terminal Class associated with Generic class
I must have misunderstood, because it sounds as if you're saying that for the empty map, you want to construct an immutable mutable map. What happens if you mutate it?

A

Date: Fri, 30 Apr 2010 19:29:16 -0700
Subject: [scala-debate]Initial/Terminal Class associated with Generic class
From: calathus [at] gmail [dot] com
To: scala-debate [at] listes [dot] epfl [dot] ch

Hi,
I had some problem for defining a single instance for empty node. From Scala's type system constraint, it seem difficult to define such object..
I wonder this may be a quite common problem in Scala.

---

In Scala, it is not easy to define a static object which would behave as null in Java or C.
Of course, to some extent, it is possible to use null in Scala for AnyRef, but it is not so powerful as in Java  since Scala class is not always subclass of AnyRef(like case class).

The typical problem arise when we try to define empty object for generic classes.
Often it is defined as following:
class HashMap[A, B] extends Map[A, B]
                       with MapLike[A, B, HashMap[A, B]]
                       with HashTable[A] {
  override def empty: HashMap[A, B] = HashMap.empty[A, B]
...
}
object HashMap extends MutableMapFactory[HashMap] {
  ...
  def empty[A, B]: HashMap[A, B] = new HashMap[A, B]
}
It is going to create different empty objects each time when empty is invoked.

it cannot use a single shared object like following pseudo code would:
object HashMap extends MutableMapFactory[HashMap] {
  val empty = HashMap[_, _].initial // initial should be defined for the type constructor itself!
  def empty[A, B]: HashMap[A, B] = empty
}
This initial should have similar type behavior as null, namely empty can be assigned to any val/var of type HashMap[A, B]. but it should cause type error when it is assigned to var of other type like List. e.g:
val A:  HashMap[Int, Int] = HashMap[_, _].initial //OK
val A:  HashMap[Float, Int] = HashMap[_, _].initial //OK
val A:  TreeMap[Float, Int] = HashMap[_, _].initial // fail
In TreeMap(RedBlack), this was achieved by introducing variance for Value
abstract class Tree[+B] {...}case object Empty extends Tree[Nothing] {...}
But this approach cannot be used for mutable TreeMap where variance cannot be used.

Are there any thought for this kind of problem??

Cheers,
calathus

http://scalathus.blogspot.com

Hotmail is redefining busy with tools for the New Busy. Get more from your inbox. See how.
calathus
Joined: 2010-03-22,
User offline. Last seen 2 years 28 weeks ago.
Re: Initial/Terminal Class associated with Generic class
Yes,
The example of empty map was not appropriate.
I wanted to show some pattern to define generic function which return some constant object.
since Scala does not allow generic constant value since n general it would not make sense.

But even mutable object, it makes sense to have an unique leaf object like Nil of List, empty Node of Tree. they are not modified(immutable).  Problem here is null is not so universally useful construct in Scala.
So we will have some difficulty to define such a constant or efficient implementation to avoid repeated empty object creation.
So it may help if TreeMap.nil may be automatically generated for TreeMap[_, _].
This would have been a common problem when we try to define recursive generic class. So I wonder how people handle  this issue.


On Fri, Apr 30, 2010 at 9:03 PM, adriaN kinG <ceroxylon [at] hotmail [dot] com> wrote:
I must have misunderstood, because it sounds as if you're saying that for the empty map, you want to construct an immutable mutable map. What happens if you mutate it?

A

Date: Fri, 30 Apr 2010 19:29:16 -0700
Subject: [scala-debate]Initial/Terminal Class associated with Generic class
From: calathus [at] gmail [dot] com
To: scala-debate [at] listes [dot] epfl [dot] ch

Hi,
I had some problem for defining a single instance for empty node. From Scala's type system constraint, it seem difficult to define such object..
I wonder this may be a quite common problem in Scala.

---

In Scala, it is not easy to define a static object which would behave as null in Java or C.
Of course, to some extent, it is possible to use null in Scala for AnyRef, but it is not so powerful as in Java  since Scala class is not always subclass of AnyRef(like case class).

The typical problem arise when we try to define empty object for generic classes.
Often it is defined as following:
class HashMap[A, B] extends Map[A, B]
                       with MapLike[A, B, HashMap[A, B]]
                       with HashTable[A] {
  override def empty: HashMap[A, B] = HashMap.empty[A, B]
...
}
object HashMap extends MutableMapFactory[HashMap] {
  ...
  def empty[A, B]: HashMap[A, B] = new HashMap[A, B]
}
It is going to create different empty objects each time when empty is invoked.

it cannot use a single shared object like following pseudo code would:
object HashMap extends MutableMapFactory[HashMap] {
  val empty = HashMap[_, _].initial // initial should be defined for the type constructor itself!
  def empty[A, B]: HashMap[A, B] = empty
}
This initial should have similar type behavior as null, namely empty can be assigned to any val/var of type HashMap[A, B]. but it should cause type error when it is assigned to var of other type like List. e.g:
val A:  HashMap[Int, Int] = HashMap[_, _].initial //OK
val A:  HashMap[Float, Int] = HashMap[_, _].initial //OK
val A:  TreeMap[Float, Int] = HashMap[_, _].initial // fail
In TreeMap(RedBlack), this was achieved by introducing variance for Value
abstract class Tree[+B] {...}case object Empty extends Tree[Nothing] {...}
But this approach cannot be used for mutable TreeMap where variance cannot be used.

Are there any thought for this kind of problem??

Cheers,
calathus

http://scalathus.blogspot.com

Hotmail is redefining busy with tools for the New Busy. Get more from your inbox. See how.



--
Cheers,
calathus

http://scalathus.blogspot.com
H-star Development
Joined: 2010-04-14,
User offline. Last seen 2 years 26 weeks ago.
feature suggestion for traversables

i'm using this thing quite often. it's purpose is to find the highest
rated element of a collection.
i don't want to use max or min because these methods need an ordering
instead of a simple function that returns a comparable value.

my suggestion is: provide another min/max-implementation similar to
sortby/sorted

/**
* Developed with pleasure :)
* User: HoD
* Date: 26.02.2010
* Time: 17:10:27
* todo mark it work with any comparable value, not just double
*/
class RichTraversable[T](t: Traversable[T])
{
def findHighest(f: T => Double, filter: T => Boolean = (T) => true,
ifEqual: (T, T) => T = (t1, t2) => t2) = {
var best: Any = null
var highest = -java.lang.Double.MAX_VALUE
for (e <- t if filter(e)) {
val value = f(e.asInstanceOf[T])
if (value == highest) {
best = ifEqual(e, best.asInstanceOf[T])
} else if (value > highest || best == null) {
best = e
highest = value
}
}
if (best == null) {
None
} else {
Some(best.asInstanceOf[T])
}
}

def findLowest(f: T => Double, filter: T => Boolean = (T) => true,
ifEqual: (T, T) => T = (t1, t2) => t2) = {
findHighest({-f(_)})
}
}

Jason Zaugg
Joined: 2009-05-18,
User offline. Last seen 38 weeks 5 days ago.
Re: feature suggestion for traversables

You can create an Ordering based on a function as follows:

scala> Ordering.by((a: Any) => a.hashCode)
res2: scala.math.Ordering[Any] = scala.math.Ordering$$anon$4@61e481c1

scala> res2.compare(new {}, new {})
res3: Int = 1

-jason

On Sat, May 1, 2010 at 4:44 PM, HamsterofDeath wrote:
> i don't want to use max or min because these methods need an ordering
> instead of a simple function that returns a comparable value.

David Flemström
Joined: 2009-08-10,
User offline. Last seen 42 years 45 weeks ago.
Re: feature suggestion for traversables
On Sat, May 1, 2010 at 5:01 PM, Jason Zaugg <jzaugg [at] gmail [dot] com> wrote:
You can create an Ordering based on a function as follows:

 scala> Ordering.by((a: Any) => a.hashCode)
 res2: scala.math.Ordering[Any] = scala.math.Ordering$$anon$4@61e481c1

 scala> res2.compare(new {}, new {})
 res3: Int = 1

Also, this should hopefully work in the future (when the type inferencer improves):
case class Foo(x: Int, y: Int)

object Main {
  def random: Stream[Int] = Stream.cons(util.Random.nextInt(1000), random)

  val foos = random take 100 map (Foo(_, 0)) toList

  implicit def easyOrdering[A, B: Ordering](f: A => B): Ordering[A] = new Ordering[A] {
    def compare(x: A, y: A) = implicitly[Ordering[B]].compare(f(x), f(y))
  }

  def main(args: Array[String]) {
    foos.max(_.x)
  }
}
It does not work at the moment, though, because of the chained implicit (but it's not a double implicit which should make it possible to infer the types).
H-star Development
Joined: 2010-04-14,
User offline. Last seen 2 years 26 weeks ago.
Re: feature suggestion for traversables

should be done inside max and min. call me lazy, but that's what i think :)

David Flemström schrieb:
> On Sat, May 1, 2010 at 5:01 PM, Jason Zaugg > wrote:
>
> You can create an Ordering based on a function as follows:
>
> scala> Ordering.by((a: Any) => a.hashCode)
> res2: scala.math.Ordering[Any] = scala.math.Ordering$$anon$4@61e481c1
>
> scala> res2.compare(new {}, new {})
> res3: Int = 1
>
>
> Also, this should hopefully work in the future (when the type
> inferencer improves):
> case class Foo(x: Int, y: Int)
>
> object Main {
> def random: Stream[Int] = Stream.cons(util.Random.nextInt(1000), random)
>
> val foos = random take 100 map (Foo(_, 0)) toList
>
> implicit def easyOrdering[A, B: Ordering](f: A => B): Ordering[A] = new Ordering[A] {
> def compare(x: A, y: A) = implicitly[Ordering[B]].compare(f(x), f(y))
> }
>
> def main(args: Array[String]) {
> foos.max(_.x)
> }
> }
> It does not work at the moment, though, because of the chained
> implicit (but it's *not* a *double* implicit which should make it
> possible to infer the types).

dcsobral
Joined: 2009-04-23,
User offline. Last seen 38 weeks 5 days ago.
Re: feature suggestion for traversables
scala> List("abc", "de", "f")res0: List[java.lang.String] = List(abc, de, f)
scala> res0.minres1: java.lang.String = abc
scala> res0.min(Ordering.by((_: String).length))res2: java.lang.String = f
On Sat, May 1, 2010 at 1:26 PM, HamsterofDeath <h-star [at] gmx [dot] de> wrote:
this:
Ordering.by((a: Any) => a.hashCode)

should be done inside max and min. call me lazy, but that's what i think :)

David Flemström schrieb:
> On Sat, May 1, 2010 at 5:01 PM, Jason Zaugg <jzaugg [at] gmail [dot] com
> <mailto:jzaugg [at] gmail [dot] com>> wrote:
>
>     You can create an Ordering based on a function as follows:
>
>      scala> Ordering.by((a: Any) => a.hashCode)
>      res2: scala.math.Ordering[Any] = scala.math.Ordering$$anon$4@61e481c1
>
>      scala> res2.compare(new {}, new {})
>      res3: Int = 1
>
>
> Also, this should hopefully work in the future (when the type
> inferencer improves):
> case class Foo(x: Int, y: Int)
>
> object Main {
>   def random: Stream[Int] = Stream.cons(util.Random.nextInt(1000), random)
>
>   val foos = random take 100 map (Foo(_, 0)) toList
>
>   implicit def easyOrdering[A, B: Ordering](f: A => B): Ordering[A] = new Ordering[A] {
>     def compare(x: A, y: A) = implicitly[Ordering[B]].compare(f(x), f(y))
>   }
>
>   def main(args: Array[String]) {
>     foos.max(_.x)
>   }
> }
> It does not work at the moment, though, because of the chained
> implicit (but it's *not* a *double* implicit which should make it
> possible to infer the types).




--
Daniel C. Sobral

I travel to the future all the time.
calathus
Joined: 2010-03-22,
User offline. Last seen 2 years 28 weeks ago.
Re: Initial/Terminal Class associated with Generic class
Looks like I was overlooking an inner object declaration to define static object in the generic class.


On Fri, Apr 30, 2010 at 11:14 PM, calathus <calathus [at] gmail [dot] com> wrote:
Yes,
The example of empty map was not appropriate.
I wanted to show some pattern to define generic function which return some constant object.
since Scala does not allow generic constant value since n general it would not make sense.

But even mutable object, it makes sense to have an unique leaf object like Nil of List, empty Node of Tree. they are not modified(immutable).  Problem here is null is not so universally useful construct in Scala.
So we will have some difficulty to define such a constant or efficient implementation to avoid repeated empty object creation.
So it may help if TreeMap.nil may be automatically generated for TreeMap[_, _].
This would have been a common problem when we try to define recursive generic class. So I wonder how people handle  this issue.


On Fri, Apr 30, 2010 at 9:03 PM, adriaN kinG <ceroxylon [at] hotmail [dot] com> wrote:
I must have misunderstood, because it sounds as if you're saying that for the empty map, you want to construct an immutable mutable map. What happens if you mutate it?

A

Date: Fri, 30 Apr 2010 19:29:16 -0700
Subject: [scala-debate]Initial/Terminal Class associated with Generic class
From: calathus [at] gmail [dot] com
To: scala-debate [at] listes [dot] epfl [dot] ch

Hi,
I had some problem for defining a single instance for empty node. From Scala's type system constraint, it seem difficult to define such object..
I wonder this may be a quite common problem in Scala.

---

In Scala, it is not easy to define a static object which would behave as null in Java or C.
Of course, to some extent, it is possible to use null in Scala for AnyRef, but it is not so powerful as in Java  since Scala class is not always subclass of AnyRef(like case class).

The typical problem arise when we try to define empty object for generic classes.
Often it is defined as following:
class HashMap[A, B] extends Map[A, B]
                       with MapLike[A, B, HashMap[A, B]]
                       with HashTable[A] {
  override def empty: HashMap[A, B] = HashMap.empty[A, B]
...
}
object HashMap extends MutableMapFactory[HashMap] {
  ...
  def empty[A, B]: HashMap[A, B] = new HashMap[A, B]
}
It is going to create different empty objects each time when empty is invoked.

it cannot use a single shared object like following pseudo code would:
object HashMap extends MutableMapFactory[HashMap] {
  val empty = HashMap[_, _].initial // initial should be defined for the type constructor itself!
  def empty[A, B]: HashMap[A, B] = empty
}
This initial should have similar type behavior as null, namely empty can be assigned to any val/var of type HashMap[A, B]. but it should cause type error when it is assigned to var of other type like List. e.g:
val A:  HashMap[Int, Int] = HashMap[_, _].initial //OK
val A:  HashMap[Float, Int] = HashMap[_, _].initial //OK
val A:  TreeMap[Float, Int] = HashMap[_, _].initial // fail
In TreeMap(RedBlack), this was achieved by introducing variance for Value
abstract class Tree[+B] {...}case object Empty extends Tree[Nothing] {...}
But this approach cannot be used for mutable TreeMap where variance cannot be used.

Are there any thought for this kind of problem??

Cheers,
calathus

http://scalathus.blogspot.com

Hotmail is redefining busy with tools for the New Busy. Get more from your inbox. See how.



--
Cheers,
calathus

http://scalathus.blogspot.com



--
Cheers,
calathus

http://scalathus.blogspot.com

Copyright © 2012 École Polytechnique Fédérale de Lausanne (EPFL), Lausanne, Switzerland