¿Cómo traduciría una clase de tipo Haskell a F #?

Question

Estoy tratando de traducir las Flechas de la biblioteca central de Haskell a F # (creo que es un buen ejercicio entender mejor las Flechas y F #, y podría usarlas en un proyecto en el que estoy trabajando). Sin embargo, la traducción directa no es posible debido a la diferencia en paradigmas. Haskell usa clases de tipos para expresar esto, pero no estoy seguro de qué construcciones F # asignen mejor la funcionalidad de las clases tipo con los modismos de F #. Tengo algunas ideas, pero pensé que sería mejor que apareciera aquí y ver lo que se consideraba lo más cercano a la funcionalidad.

Para la multitud de tl; dr: ¿Cómo se traducen las clases de tipo (una expresión de Haskell) en el código idiomático de F #?

Para aquellos aceptar de mi larga explicación:

Este código de la lib estándar Haskell es un ejemplo de lo que estoy tratando de traducir:

class Category cat where 
    id :: cat a a 
    comp :: cat a b -> cat b c -> cat a c 
class Category a => Arrow a where 
    arr :: (b -> c) -> a b c 
    first :: a b c -> a (b,d) (c,d) 

instance Category (->) where 
    id f = f 
instance Arrow (->) where 
    arr f = f 
    first f = f *** id 

Intento 1: Módulos, tipos simples , que Vinculaciones

Mi primera oportunidad en esto era simplemente mapear cosas sobre el uso directo Módulos de organización, como:

type Arrow<'a,'b> = Arrow of ('a -> 'b) 

let arr f = Arrow f 
let first f = //some code that does the first op 

Eso funciona, pero pierde polimorfismo, ya que no implemento Categorías y no pueda implementar fácilmente Flechas más especializadas.

Intento 1a: Refinación usando firmas y tipos

Una forma de corregir algunos problemas con el intento 1 es utilizar un archivo .fsi para definir los métodos (por lo que los tipos más fácil hacer cumplir) y utilizar algunas simples tipo ajustes para especializarse.

type ListArrow<'a,'b> = Arrow<['a],['b]> 
//or 
type ListArrow<'a,'b> = LA of Arrow<['a],['b]> 

Pero el archivo FSI no se puede volver a utilizar (para hacer cumplir los tipos de las funciones obligado LET) para otras implementaciones, y el tipo de cambio de nombre/encapsular cosas es difícil.

Intento 2: Los modelos de objetos e interfaces

La racionalización que F # está diseñado para ser OO también, tal vez una jerarquía de tipos es la forma correcta de hacer esto.

type IArrow<'a,'b> = 
    abstract member comp : IArrow<'b,'c> -> IArrow<'a,'c> 
type Arrow<'a,'b>(func:'a->'b) = 
    interface IArrow<'a,'b> with 
     member this.comp = //fun code involving "Arrow (fun x-> workOn x) :> IArrow" 

Aparte de la cantidad de un dolor que puede ser conseguir lo que debería ser métodos estáticos (como un borrador y otros operadores) para actuar como métodos de instancia, también existe la necesidad de upcast explícitamente los resultados. Tampoco estoy seguro de que esta metodología todavía esté capturando la expresividad total del polimorfismo de tipo de clase. También hace que sea difícil usar cosas que DEBEN ser métodos estáticos.

Intento 2a: Refinación usando extensiones de tipos de

Así que un mayor refinamiento potencial es declarar las interfaces tan desnudas como sea posible, a continuación, utilizar los métodos de extensión para agregar funcionalidad a todo tipo de aplicación.

type IArrow<'a,'b> with 
    static member (&&&) f = //code to do the fanout operation 

Ah, pero esto me encierra en el uso de un método para todos los tipos de IArrow.Si quisiera un poco diferente (& & &) para ListArrows, ¿qué puedo hacer? No he probado este método todavía, pero creo que puedo sombrear el (& & &), o al menos proporcionar una versión más especializada, pero creo que no puedo exigir el uso de la variante correcta.

Ayúdame

Entonces, ¿qué se supone que voy a hacer aquí? Siento que OO debería ser lo suficientemente potente como para reemplazar las clases de tipo, pero parece que no puedo encontrar la manera de hacerlo en F #. ¿Alguno de mis intentos estuvo cerca? ¿Alguno de ellos es "tan bueno como puede ser" y eso tendrá que ser lo suficientemente bueno?

Answer 1

Este es el enfoque que utilizo para simular las clases de tipos (de http://code.google.com/p/fsharp-typeclasses/).

En su caso, para las flechas podría ser algo como esto:

let inline i2 (a:^a,b:^b ) =              
    ((^a or ^b  ) : (static member instance: ^a* ^b  -> _) (a,b )) 
let inline i3 (a:^a,b:^b,c:^c) =               
    ((^a or ^b or ^c) : (static member instance: ^a* ^b* ^c -> _) (a,b,c)) 

type T = T with 
    static member inline instance (a:'a  ) = 
     fun x -> i2(a , Unchecked.defaultof<'r>) x :'r 
    static member inline instance (a:'a, b:'b) = 
     fun x -> i3(a, b, Unchecked.defaultof<'r>) x :'r 


type Return = Return with 
    static member instance (_Monad:Return, _:option<'a>) = fun x -> Some x 
    static member instance (_Monad:Return, _:list<'a> ) = fun x -> [x] 
    static member instance (_Monad:Return, _: 'r -> 'a) = fun x _ -> x 
let inline return' x = T.instance Return x 

type Bind = Bind with 
    static member instance (_Monad:Bind, x:option<_>, _:option<'b>) = fun f -> 
     Option.bind f x 
    static member instance (_Monad:Bind, x:list<_> , _:list<'b> ) = fun f -> 
     List.collect f x 
    static member instance (_Monad:Bind, f:'r->'a, _:'r->'b) = fun k r -> k (f r) r 
let inline (>>=) x (f:_->'R) : 'R = T.instance (Bind, x) f 
let inline (>=>) f g x = f x >>= g 

type Kleisli<'a, 'm> = Kleisli of ('a -> 'm) 
let runKleisli (Kleisli f) = f 

type Id = Id with 
    static member  instance (_Category:Id, _: 'r -> 'r ) = fun() -> id 
    static member inline instance (_Category:Id, _:Kleisli<'a,'b>) = fun() -> 
     Kleisli return' 
let inline id'() = T.instance Id() 

type Comp = Comp with 
    static member  instance (_Category:Comp,   f, _) = (<<) f 
    static member inline instance (_Category:Comp, Kleisli f, _) = 
     fun (Kleisli g) -> Kleisli (g >=> f) 

let inline (<<<) f g = T.instance (Comp, f) g 
let inline (>>>) g f = T.instance (Comp, f) g 

type Arr = Arr with 
    static member  instance (_Arrow:Arr, _: _ -> _) = fun (f:_->_) -> f 
    static member inline instance (_Arrow:Arr, _:Kleisli<_,_>) = 
     fun f -> Kleisli (return' <<< f) 
let inline arr f = T.instance Arr f 

type First = First with 
    static member  instance (_Arrow:First, f, _: 'a -> 'b) = 
     fun() (x,y) -> (f x, y) 
    static member inline instance (_Arrow:First, Kleisli f, _:Kleisli<_,_>) = 
     fun() -> Kleisli (fun (b,d) -> f b >>= fun c -> return' (c,d)) 
let inline first f = T.instance (First, f)() 

let inline second f = let swap (x,y) = (y,x) in arr swap >>> first f >>> arr swap 
let inline (***) f g = first f >>> second g 
let inline (&&&) f g = arr (fun b -> (b,b)) >>> f *** g 

Uso:

> let f = Kleisli (fun y -> [y;y*2;y*3]) <<< Kleisli (fun x -> [ x + 3 ; x * 2 ]) ;; 
val f : Kleisli<int,int list> = Kleisli <fun:f@4-14> 

> runKleisli f <| 5 ;; 
val it : int list = [8; 16; 24; 10; 20; 30] 

> (arr (fun y -> [y;y*2;y*3])) 3 ;; 
val it : int list = [3; 6; 9] 

> let (x:option<_>) = runKleisli (arr (fun y -> [y;y*2;y*3])) 2 ;; 
val x : int list option = Some [2; 4; 6] 

> ((*) 100) *** ((+) 9) <| (5,10) ;; 
val it : int * int = (500, 19) 

> ((*) 100) &&& ((+) 9) <| 5 ;; 
val it : int * int = (500, 14) 

> let x:List<_> = (runKleisli (id'())) 5 ;; 
val x : List<int> = [5] 

Nota: El uso id'() en lugar de id

Actualización: se necesita F # 3.0 para compilar este código, de lo contrario here's the F# 2.0 version.

Y here's una explicación detallada de esta técnica que es segura, extensible y, como puede ver, funciona incluso con algunas clases de tipos superiores.

Answer 2

Mi respuesta breve es:

OO no es lo suficientemente potente como para sustituir las clases de tipos.

La traducción más directa es pasar un diccionario de operaciones, como en una implementación de clase de clase típica. Esto es, si clase de tipos Foo define tres métodos, a continuación, definir un tipo de clase/registro llamado Foo, y luego cambiar las funciones de

Foo a => yadda -> yadda -> yadda 

a funciones como

Foo -> yadda -> yadda -> yadda 

y en cada sitio de llamada que sabe el hormigón 'instancia' para pasar según el tipo en el sitio de llamada.

Aquí hay un pequeño ejemplo de lo que quiero decir:

// typeclass 
type Showable<'a> = { show : 'a -> unit; showPretty : 'a -> unit } //' 

// instances 
let IntShowable = 
    { show = printfn "%d"; showPretty = (fun i -> printfn "pretty %d" i) } 
let StringShowable = 
    { show = printfn "%s"; showPretty = (fun s -> printfn "<<%s>>" s) } 

// function using typeclass constraint 
// Showable a => [a] ->() 
let ShowAllPretty (s:Showable<'a>) l = //' 
    l |> List.iter s.showPretty 

// callsites 
ShowAllPretty IntShowable [1;2;3] 
ShowAllPretty StringShowable ["foo";"bar"] 

Ver también

https://web.archive.org/web/20081017141728/http://blog.matthewdoig.com/?p=112