oop - tipos - multiplicar haskell

¿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, una 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 el grupo de tl; dr: ¿Cómo traduzco las clases de tipo (una expresión de Haskell) en el código idiomático de F #?

Para aquellos que aceptan mi larga explicación:

Este código de la versión estándar de Haskell es un ejemplo de lo que trato 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, Deje enlaces

Mi primer intento fue simplemente mapear las cosas directamente usando módulos para la 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: refinar usando firmas y tipos

Una forma de corregir algunos problemas con Attempt 1 es usar un archivo .fsi para definir los métodos (para que los tipos se hagan más fáciles) y usar algunos ajustes de tipo simples 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 reutilizar (para imponer los tipos de las funciones de límite permitido) para otras implementaciones, y el tipo de cambio de nombre / encapsulado es complicado.

Intento 2: modelos de objetos e interfaces

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

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"

Además de la cantidad de dolor que puede ocasionar que los métodos estáticos (como comp y otros operadores) funcionen como métodos de instancia, también existe la necesidad de actualizar los resultados de forma explícita. 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: refinar usando extensiones de tipo

Por lo tanto, un refinamiento potencial más es declarar las interfaces lo más simples posible, luego usar métodos de extensión para agregar funcionalidad a todos los tipos de implementació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? Todavía no he probado este método, pero creo que puedo sombrear el (&&&), o al menos proporcionar una versión más especializada, pero siento que no puedo exigir el uso de la variante correcta.

Ayuadame

Entonces, ¿qué se supone que debo 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 uso para simular Typeclasses (de http://code.google.com/p/fsharp-typeclasses/ ).

En su caso, para Arrows 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: use id''() lugar de id

Actualización: necesita F # 3.0 para compilar este código; de lo contrario, aquí está la versión F # 2.0 .

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 breve respuesta es:

OO no es lo suficientemente potente como para reemplazar las clases de tipo.

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

Foo a => yadda -> yadda -> yadda

a funciones como

Foo -> yadda -> yadda -> yadda

y en cada sitio de llamadas usted conoce la ''instancia'' concreta para aprobar en función del tipo en el sitio de llamadas.

Aquí hay un breve 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