OCaml: più alto il polimorfismo kinded (astrazione su moduli?)

Question

Diciamo che ho una lista di opzioni:

let opts = [Some 1; None; Some 4] 

mi piacerebbe convertirli in un'opzione di lista, in modo tale che:

• Se l'elenco contiene None, il risultato è None
• In caso contrario, i vari int sono raccolti.

E 'relativamente semplice di scrivere questo per questo caso specifico (utilizzando Core e il modulo Monad):

let sequence foo = 
let open Option in 
let open Monad_infix in 
    List.fold ~init:(return []) ~f:(fun acc x -> 
    acc >>= fun acc' -> 
    x >>= fun x' -> 
    return (x' :: acc') 
    ) foo;; 

Tuttavia, come suggerisce il titolo della domanda, mi piacerebbe davvero astratta sopra il tipo costruttore piuttosto che specializzarsi a Option. Il core sembra utilizzare un funtore per dare l'effetto di un tipo più alto, ma non sono chiaro in che modo posso scrivere la funzione da astrarre sul modulo. In Scala, utilizzerei un contesto implicito per richiedere la disponibilità di alcuni Monad[M[_]]. Mi aspetto che non ci sia modo di passare implicitamente nel modulo, ma come lo farei esplicitamente? In altre parole, posso scrivere qualcosa di simile a questo:

let sequence (module M : Monad.S) foo = 
let open M in 
let open M.Monad_infix in 
    List.fold ~init:(return []) ~f:(fun acc x -> 
    acc >>= fun acc' -> 
    x >>= fun x' -> 
    return (x' :: acc') 
    ) foo;; 

È qualcosa che può essere fatto con moduli di prima classe?

Modifica: Ok, quindi non mi è venuto in mente di provare a utilizzare quel codice specifico, e sembra che sia più vicino al lavoro di quanto mi aspettassi! Sembra la sintassi è infatti valida, ma ottengo questo risultato:

Error: This expression has type 'a M.t but an expression was expected of type 'a M.t 
The type constructor M.t would escape its scope  

La prima parte del errore sembra confusa, in quanto essi corrispondono, quindi sto cercando di indovinare il problema è con il secondo - è il problema qui che il tipo di ritorno non sembra essere determinato? Suppongo che dipenda dal modulo che è passato - è un problema? C'è un modo per risolvere questa implementazione?

Answer 1

primo luogo, qui è una versione autonoma del codice (utilizzando l'eredità List.fold_left della libreria standard) per le persone che non hanno Nucleo sotto la mano e ancora voglia di provare a compilare il vostro esempio.

module type MonadSig = sig 
    type 'a t 
    val bind : 'a t -> ('a -> 'b t) -> 'b t 
    val return : 'a -> 'a t 
end 

let sequence (module M : MonadSig) foo = 
    let open M in 
    let (>>=) = bind in 
    List.fold_left (fun acc x -> 
    acc >>= fun acc' -> 
    x >>= fun x' -> 
    return (x' :: acc') 
) (return []) foo;; 

Il messaggio di errore che si ottiene mezzo (la prima linea di confusione può essere ignorato) che la definizione Mt è locale al modulo M, e non deve poter uscire la sua portata, che sarebbe fare con quello che Stai cercando per scrivere.

Questo perché si sta utilizzando i moduli di prima classe, che permettono di astratto su moduli, ma non di avere tipi dipendenti dall'aspetto, come il tipo di ritorno dipende dal valore del modulo della discussione, o almeno percorso (qui M).

Considerate questo esempio:

module type Type = sig 
    type t 
end 

let identity (module T : Type) (x : T.t) = x 

Questo è sbagliato.I messaggi di errore punti (x : T.t) e dice:

Error: This pattern matches values of type T.t 
     but a pattern was expected which matches values of type T.t 
     The type constructor T.t would escape its scope 

Che cosa si può fare è astratta del tipo desiderato prima astratto sul modulo di prima classe T, in modo che non v'è più alcuna via di fuga.

let identity (type a) (module T : Type with type t = a) (x : a) = x 

Questa si basa sulla capacità di esplicitamente astratto sul tipo di variabile a. Sfortunatamente, questa caratteristica non è stata estesa all'astrazione rispetto alle variabili di tipo superiore. Al momento non è possibile scrittura:

let sequence (type 'a m) (module M : MonadSig with 'a t = 'a m) (foo : 'a m list) = 
    ... 

La soluzione è quella di utilizzare un funtore: invece di lavorare a livello di valore, si lavora a livello di modulo, che ha un linguaggio più ricco genere.

module MonadOps (M : MonadSig) = struct 
    open M 
    let (>>=) = bind 

    let sequence foo = 
    List.fold_left (fun acc x -> 
     acc >>= fun acc' -> 
     x >>= fun x' -> 
     return (x' :: acc') 
    ) (return []) foo;; 
end 

Invece di avere ogni operazione monadica (sequence, map, etc.) astratta su monade, si fa un'astrazione a livello di modulo.