Type for Traversable that maps to same kind of Traversable

Question

Short version. Most generic collections in Scala have a map method which will, in fact, return a collection of the same type. (List[A].map(f:A=>B) returns a List[B], for example.) The Scala collection library was explicitly designed to achieve this. What if I want to write code that is polymorphic over any such collection? Can "Traversable whose map behaves like a functor's does" be expressed as a type?

Long version. I have a situation where it would be useful to have an abstraction representing a collection of objects of some Current type, such that if those objects were converted to some Desired type, then the collection could use those objects to construct an object of some Result type. I can achieve pretty much everything I want just by using the function type

(C => D) => R

but one defect of this approach is the excessive laziness (in the context my application) of the natural map method, which would be something like

def map[C2](f: C=>C2): (C2=>D)=>R = (g => this(f andThen g))

This delays the application of f to the objects of type C until the R is being computed. I'd rather apply f immediately.

So, for example, I might implement something like

class Foo[+C,-D,+R](cs: List[C], finalize: List[D]=>R) {
    def apply(f: C=>D): R = finalize(cs.map(f))
    def map[C2](f: C=>C2): Foo[C2,D,R] = Foo(cs.map(f), finalize)
}

So far so good. But now I think to myself, there's nothing special about List here; any type constructor that implemented some kind of map function would do. The only thing is that the function finalize might rely on the structure of the collection. Maybe the first element of the list is treated specially, for example, so if the List.map returned some more general type of collection, perhaps a very abstract one that didn't even have a notion of "first element", then finalize could fail. Likewise if it expects the list to be a certain length but I filter the list or something.

This kind of problem cannot arise if I write the code in its natural generality, something like

class Foo[+C,-D,+R,F[x] <: Traversable[x]](cs: F[C], finalize: F[D]=>R) {
    ...
}

because then I can't accidentally do anything weird with the F (unless I inspect its type at runtime or something, in which case I deserve what I get).

The only remaining problem is that cs.map(f) has static type Traversable[D], not F[D], although of course we expect that it's actually of type F[D] usually, and the Scala collection library was explicitly designed to ensure that that is so.

So my question is, can this requirement on F be expressed in the types?

---

Essentially, I want the Scala version of the Haskell code

data Foo f b r a = Foo (f a) (f b -> r)
instance (Functor f) => Functor (Foo f b r) where
    g `fmap` (Foo fa fbr) = Foo (g `fmap` fa) fbr
dothething :: (Functor f) => Foo f b r a -> (a -> b) -> r
dothething foo g = fbr fb where Foo fb fbr = g `fmap` foo

with more or less the same guarantees and without laziness.

Answer 1

Are you looking for Functor from scalaz?

https://github.com/scalaz/scalaz/blob/scalaz-seven/core/src/main/scala/scalaz/Functor.scala

It allows you to do abstract over anything that can fulfill the type class definition.

def addTwo[F[_]](f: F[Int])(implicit F: Functor[F]): F[Int] = f.map(_+2)

Now my 'addTwo' method does not care what is being mapped, as long as there exists a functor instance. So both of these would work:

addTwo(List(1,2,3))
addTwo(Future { 1 } ) 

etc.