Come si può soddisfare un vincolo di classe in un'istanza di una classe che richiede un costruttore di tipi piuttosto che un tipo concreto?

Question

Sono attualmente in Chapter 8 di Learn you a Haskell e ho raggiunto la sezione sulla classe Functor. In questa sezione l'autore fornisce esempi di come tipi diversi possono essere realizzati istanze della classe (ad esempio, un tipo personalizzato Tree, ecc.) Vedendo questo, ho deciso di (per divertimento e pratica) provare ad implementare un'istanza per il tipo Data.Set ; in tutto questo ignorando lo Data.Set.map, ovviamente.

L'istanza vera e propria è abbastanza straight-forward, e ho scritto come:

instance Functor Set.Set where 
    fmap f empty = Set.empty 
    fmap f s = Set.fromList $ map f (Set.elems s) 

Ma, dal momento che mi capita di usare la funzione fromList questo porta a un vincolo di classe chiamando per i tipi utilizzati nel Set di essere Ord, come si spiega con un errore di compilazione:

Error occurred 
ERROR line 4 - Cannot justify constraints in instance member binding 
*** Expression : fmap 
*** Type   : Functor Set => (a -> b) -> Set a -> Set b 
*** Given context : Functor Set 
*** Constraints : Ord b 

See: Live Example

I Tri Ed inserendo un vincolo sull'istanza o aggiungendo una firma di tipo a fmap, ma nessuno dei due ha avuto esito positivo (entrambi erano errori del compilatore.)

Data una situazione come questa, come può essere soddisfatto e soddisfatto un vincolo? C'è qualche modo possibile?

Grazie in anticipo! :)

Answer 1

Sfortunatamente, c'è no un modo semplice per farlo con la classe standard Functor. Questo è il motivo per cui Set non viene fornito con un'istanza Functor per impostazione predefinita: non è possibile scriverne uno.

Questo è un problema e ci sono state alcune soluzioni suggerite (ad esempio la definizione della classe Functor in un modo diverso), ma non so se esiste un consenso su come gestirlo al meglio.

Credo che un approccio sia quello di riscrivere la classe Functor utilizzando constraint kinds per reificare le istanze di vincoli aggiuntivi della nuova classe Functor. Ciò consente di specificare che Set deve contenere tipi dalla classe Ord.

Un altro approccio utilizza solo classi multiparametro. Ho potuto trovare solo l'articolo su come fare questo per la classe Monad, ma fare la parte di Monad affronta gli stessi problemi che lo rendono parte di Functor. Si chiama Restricted Monads.

La sostanza di base di utilizzare classi multi-parametro qui sembra essere qualcosa di simile:

class Functor' f a b where 
    fmap' :: (a -> b) -> f a -> f b 

instance (Ord a, Ord b) => Functor' Data.Set.Set a b where 
    fmap' = Data.Set.map 

In sostanza, tutto quello che stai facendo qui sta facendo i tipi nel il Set anche parte della classe . Questo ti consente di limitare ciò che questi tipi possono essere quando scrivi un'istanza di quella classe.

Questa versione di Functor ha bisogno di due estensioni: MultiParamTypeClasses e FlexibleInstances.(È necessario che la prima estensione sia in grado di definire la classe e la seconda estensione per poter definire un'istanza per Set.)

Haskell : An example of a Foldable which is not a Functor (or not Traversable)? ha una buona discussione a riguardo.

Answer 2

Questo è impossibile. Lo scopo della classe Functor è che se si dispone di Functor f => f a, è possibile sostituire lo a con qualsiasi cosa si desideri. La classe non è autorizzata a costringerti a restituire solo questo o quello. Poiché Set richiede che i suoi elementi soddisfino determinati vincoli (e in realtà non si tratta di un dettaglio di implementazione ma in realtà una proprietà essenziale degli insiemi), non soddisfa i requisiti di Functor.

Ci sono, come accennato in un'altra risposta, modi di sviluppare una classe come Functor che ti limita in questo modo, ma è davvero una classe diversa, perché offre all'utente un numero inferiore di garanzie (non lo fai arrivare a utilizzare questo con qualsiasi parametro di tipo che si desidera), in cambio di diventare applicabile a una gamma più ampia di tipi. Questo è, dopo tutto, il classico compromesso della definizione di una proprietà di tipi: più tipi si vogliono soddisfare, meno devono essere forzati a soddisfare.

(Un altro esempio interessante di dove questo si presenta è la classe MonadPlus. In particolare, per ogni istanza MonadPlus TC si può fare un'istanza Monoid (TC a), ma non si può sempre andare il contrario. Di qui l'istanza Monoid (Maybe a) è diverso dall'istanza MonadPlus Maybe, perché il primo può limitare l'a ma quest'ultimo non è in grado.)

Answer 3

You can do this using a CoYoneda Functor.

{-# LANGUAGE GADTs #-} 

data CYSet a where 
    CYSet :: (Ord a) => Set.Set a -> (a -> b) -> CYSet b 

liftCYSet :: (Ord a) => Set.Set a -> CYSet a 
liftCYSet s = CYSet s id 

lowerCYSet :: (Ord a) => CYSet a -> Set.Set a 
lowerCYSet (CYSet s f) = Set.fromList $ map f $ Set.elems s 

instance Functor CYSet where 
    fmap f (CYSet s g) = CYSet s (f . g) 

main = putStrLn . show 
    $ lowerCYSet 
    $ fmap (\x -> x `mod` 3) 
    $ fmap abs 
    $ fmap (\x -> x - 5) 
    $ liftCYSet $ Set.fromList [1..10] 
-- prints "fromList [0,1,2]"