Tricks with high-order type parameters and collections

[Daniel Sobral]

Can anyone make the following definition work?

 

def perm[CC[T] <: Iterable[T], T](k: Int, a: CC[T]): CC[T] = {
  val s = Array.range(0, a.size);
  val v = a.toVector
  var kk = k
  for (j <- 2 to s.length) {
    swap(kk % j, j - 1, s)
    kk = kk / j
  }
  a.zipWithIndex map { case (_, index) => v(s(index)) }
}

 

Basically, I'd like the following to return a List[List[Int]]:

 

for(i <- 0 until 24toList) yield perm(i, List(1,2,3,4))

--
Daniel C. Sobral

Veni, vidi, veterni.

[David Hall-17]

On Fri, Nov 6, 2009 at 9:30 AM, Daniel Sobral <dcsobral@...> wrote:
> Can anyone make the following definition work?

I don't seem to have swap or toVector, but this should basically work:

import scala.collection._;
import scala.collection.generic._;
def perm[CC[X] <: Iterable[X] with IterableLike[X,CC[X]], T](k: Int,
a: CC[T])(implicit cbf: CanBuildFrom[CC[(T,Int)],T,CC[T]],
                                                    cbf2:
CanBuildFrom[CC[T],(T,Int),CC[(T,Int)]]): CC[T] = {
  val s = Array.range(0, a.size);
  val v = a.toSeq
  var kk = k
  for (j <- 2 to s.length) {
    //swap(kk % j, j - 1, s)
    kk = kk / j
  }
  a.zipWithIndex map { case (_, index) => v(s(index)) }
}


New collections make what was once impossible merely ugly... and
possibly confusing.

-- David

[Daniel Sobral]

Why is X used with CC and its constraints, instead of T?

On Fri, Nov 6, 2009 at 4:05 PM, David Hall <dlwh@...> wrote:

On Fri, Nov 6, 2009 at 9:30 AM, Daniel Sobral <dcsobral@...> wrote:
> Can anyone make the following definition work?

I don't seem to have swap or toVector, but this should basically work:

import scala.collection._;
import scala.collection.generic._;
def perm[CC[X] <: Iterable[X] with IterableLike[X,CC[X]], T](k: Int,
a: CC[T])(implicit cbf: CanBuildFrom[CC[(T,Int)],T,CC[T]],
                                                   cbf2:
CanBuildFrom[CC[T],(T,Int),CC[(T,Int)]]): CC[T] = {

 val s = Array.range(0, a.size);

 val v = a.toSeq

 var kk = k
 for (j <- 2 to s.length) {
   //swap(kk % j, j - 1, s)
   kk = kk / j
 }
 a.zipWithIndex map { case (_, index) => v(s(index)) }
}

New collections make what was once impossible merely ugly... and
possibly confusing.

-- David

--
Daniel C. Sobral

Veni, vidi, veterni.

[Daniel Sobral]

In fact, why can't I do this:

 

def quicksort[T <% Ordered[T], CC[X] <: Traversable[X] with TraversableLike[X, CC[X]]](coll: CC[T]): CC[T] =
  if (coll.isEmpty) {
    coll
  } else {
    val (smaller, bigger) = coll partition (_ < coll.head)
    quicksort(smaller) ++ quicksort(bigger)
  }

 

?

On Fri, Nov 13, 2009 at 2:39 PM, Daniel Sobral <dcsobral@...> wrote:

Why is X used with CC and its constraints, instead of T?

On Fri, Nov 6, 2009 at 4:05 PM, David Hall <dlwh@...> wrote:

On Fri, Nov 6, 2009 at 9:30 AM, Daniel Sobral <dcsobral@...> wrote:
> Can anyone make the following definition work?

I don't seem to have swap or toVector, but this should basically work:

import scala.collection._;
import scala.collection.generic._;
def perm[CC[X] <: Iterable[X] with IterableLike[X,CC[X]], T](k: Int,
a: CC[T])(implicit cbf: CanBuildFrom[CC[(T,Int)],T,CC[T]],
                                                   cbf2:
CanBuildFrom[CC[T],(T,Int),CC[(T,Int)]]): CC[T] = {

 val s = Array.range(0, a.size);

 val v = a.toSeq

 var kk = k
 for (j <- 2 to s.length) {
   //swap(kk % j, j - 1, s)
   kk = kk / j
 }
 a.zipWithIndex map { case (_, index) => v(s(index)) }
}

New collections make what was once impossible merely ugly... and
possibly confusing.

-- David

--
Daniel C. Sobral

Veni, vidi, veterni.

--
Daniel C. Sobral

Veni, vidi, veterni.

[Daniel Sobral]

Because I don't have a builder, among other things. Here, this works:

 

def quicksort
  [T, CC[X] <: Traversable[X] with TraversableLike[X, CC[X]]]       // My type parameters
  (coll: CC[T])                                                     // My explicit parameter
  (implicit o: T => Ordered[T], cbf: CanBuildFrom[CC[T], T, CC[T]]) // My implicit parameters

  : CC[T] =                                                         // My return type
  if (coll.isEmpty) {
    coll
  } else {
    val (smaller, bigger) = coll.tail partition (_ < coll.head)
    quicksort(smaller) ++ coll.companion(coll.head) ++ quicksort(bigger)
  }

On Fri, Nov 13, 2009 at 2:47 PM, Daniel Sobral <dcsobral@...> wrote:

In fact, why can't I do this:

 

def quicksort[T <% Ordered[T], CC[X] <: Traversable[X] with TraversableLike[X, CC[X]]](coll: CC[T]): CC[T] =
  if (coll.isEmpty) {
    coll
  } else {
    val (smaller, bigger) = coll partition (_ < coll.head)
    quicksort(smaller) ++ quicksort(bigger)
  }

 

?

On Fri, Nov 13, 2009 at 2:39 PM, Daniel Sobral <dcsobral@...> wrote:

Why is X used with CC and its constraints, instead of T?

On Fri, Nov 6, 2009 at 4:05 PM, David Hall <dlwh@...> wrote:

On Fri, Nov 6, 2009 at 9:30 AM, Daniel Sobral <dcsobral@...> wrote:
> Can anyone make the following definition work?

I don't seem to have swap or toVector, but this should basically work:

import scala.collection._;
import scala.collection.generic._;
def perm[CC[X] <: Iterable[X] with IterableLike[X,CC[X]], T](k: Int,
a: CC[T])(implicit cbf: CanBuildFrom[CC[(T,Int)],T,CC[T]],
                                                   cbf2:
CanBuildFrom[CC[T],(T,Int),CC[(T,Int)]]): CC[T] = {

 val s = Array.range(0, a.size);

 val v = a.toSeq

 var kk = k
 for (j <- 2 to s.length) {
   //swap(kk % j, j - 1, s)
   kk = kk / j
 }
 a.zipWithIndex map { case (_, index) => v(s(index)) }
}

New collections make what was once impossible merely ugly... and
possibly confusing.

-- David

--
Daniel C. Sobral

Veni, vidi, veterni.

--
Daniel C. Sobral

Veni, vidi, veterni.

--
Daniel C. Sobral

Veni, vidi, veterni.