Tipo per Traversable che esegue il mapping allo stesso tipo di Traversable

Question

Versione corta. La maggior parte delle raccolte generiche in Scala hanno un metodo map che restituirà una raccolta dello stesso tipo. (List[A].map(f:A=>B) restituisce un List[B], ad esempio.) La libreria di raccolta Scala è stata appositamente progettata per raggiungere questo obiettivo. Cosa succede se voglio scrivere codice che è polimorfico su una tale collezione? Può "Traversable la cui mappa si comporta come quella di un funtore" essere espressa come un tipo?

Versione lunga. Ho una situazione in cui sarebbe utile avere un'astrazione che rappresenta una raccolta di oggetti di tipo C urrent, in modo tale che se tali oggetti sono stati convertiti in alcuni tipi esired D, la raccolta potrebbe utilizzare tali oggetti per costruire un oggetto di qualche tipo es. R esult. Posso raggiungere praticamente tutto quello che voglio semplicemente utilizzando il tipo di funzione

(C => D) => R 

ma un difetto di questo approccio è la pigrizia eccessivo (nel contesto mia applicazione) del metodo naturale map, che sarebbe qualcosa di simile

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

Questa ritarda l'applicazione di f agli oggetti di tipo C fino alla R si sta calcolando. Preferirei applicare immediatamente f.

Così, per esempio, potrei implementare qualcosa di simile

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) 
} 

Fin qui tutto bene. Ma ora penso a me stesso, non c'è niente di speciale su List qui; qualsiasi tipo di costruttore che implementava un qualche tipo di funzione map. L'unica cosa è che la funzione finalize potrebbe fare affidamento sulla struttura della raccolta. Forse il primo elemento della lista viene trattato in modo speciale, ad esempio, quindi se lo List.map ha restituito un tipo più generale di raccolta, forse molto astratto che non aveva nemmeno una nozione di "primo elemento", allora finalize potrebbe non riuscire. Allo stesso modo se si aspetta che la lista sia di una certa lunghezza ma io filtro la lista o qualcosa del genere.

Questo tipo di problema non può sorgere se scrivo il codice nella sua generalità naturale, qualcosa di simile a

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

perché allora non posso fare accidentalmente qualcosa di strano con la F (a meno che io ispezionare il suo tipo in fase di esecuzione o qualcosa del genere, nel qual caso mi merito quello che ottengo).

L'unico problema e 'che cs.map(f) ha tipo statico Traversable[D], non F[D], anche se naturalmente ci aspettiamo che in realtà è di tipo F[D] solito, e la biblioteca raccolta Scala è stato esplicitamente progettato per garantire che questo è così.

Quindi la mia domanda è, può questo requisito su F essere espresso nei tipi?

---

In sostanza, voglio la versione Scala del codice Haskell

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 

con più o meno le stesse garanzie e senza pigrizia.

Answer 1

Stai cercando Functor da scalaz?

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

Esso permette di fare astratto su tutto ciò che può soddisfare la definizione del tipo di classe.

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

Ora il mio metodo 'addTwo' non importa ciò che viene mappata, fintanto che esiste un'istanza funtore. Quindi entrambi questi avrebbe funzionato:

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

ecc