43 votos

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

Estoy tratando de traducir la Haskell núcleo de la biblioteca Flechas en F# (creo que es un buen ejercicio para la comprensión de Flechas y F# mejor, y yo podría ser capaz de utilizarlos en un proyecto en el que estoy trabajando.) Sin embargo, una traducción directa no es posible debido a la diferencia en los paradigmas. Haskell utiliza el tipo-clases para expresar estas cosas, pero no estoy seguro de lo F# construcciones de mejor mapa de la funcionalidad de las clases con los modismos de F#. Tengo un par de ideas, pero pensé que era mejor llevarlo hasta aquí y ver lo que se consideraba el más cercano en la funcionalidad.

Para el tl;dr multitud: ¿Cómo puedo traducir tipo de clases (un lenguaje Haskell) en F# idiomáticas código?

Para aquellos que la aceptación de mi larga explicación:

Este código de la Haskell estándar lib 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, Vamos A Enlaces

Mi primer intento en esto era simplemente el mapa de las cosas más directamente mediante el uso de 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

Que funciona, pero se pierde en el polimorfismo, ya que yo no aplicar Categorías y no se puede implementar fácilmente más especializados Flechas.

Intento 1a: Refinar el uso de las Firmas y los tipos de

Una manera de corregir algunos problemas con el Intento 1 es el uso de una .fsi de archivo para definir los métodos (para los tipos de exigir más fácil) y el uso de algún tipo simple ajustes a especializarse.

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

Pero el fsi archivo no puede ser reutilizado (para aplicar los tipos de permitir que las funciones enlazadas) para otras implementaciones, y el tipo de cambio de nombre/encapsular las cosas es difícil.

Intento 2: modelos de Objetos e interfaces

La racionalización de que F# es construido para ser OO también, tal vez un tipo de jerarquía es la manera 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"

Aparte de cómo mucho de un dolor que puede ser conseguir lo que deben ser los métodos estáticos (como comp y otros operadores) actuar como instancia de métodos, hay también la necesidad explícita de upcast los resultados. Tampoco estoy seguro de que esta metodología es la captura de la expresividad total de tipo de clase polimorfismo. También hace que sea difícil de utilizar las cosas que DEBEN ser métodos estáticos.

Intento 2a: Refinación utilizando el tipo de extensiones

Así que una más potencial de refinamiento es declarar las interfaces como desnudo como sea posible, a continuación, utilice los métodos de extensión para añadir funcionalidad a la aplicación de todos los tipos.

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 yo quería algo un poco diferente (&&&) para ListArrows, ¿qué puedo hacer? No he probado este método aún, pero me imagino que puedo sombra (&&&), o al menos ofrecer una versión especializada, pero me siento como que no se puede exigir el uso de la variante correcta.

Me ayudan

Entonces, ¿qué se supone que voy a hacer aquí? Me siento como OO debe ser lo suficientemente potente como para reemplazar el tipo de clases, pero me parece que no puede averiguar cómo hacer que eso suceda en F#. Ninguno de mis intentos de cerrar? Ninguna de ellas "as good as it gets" y que tendrá que ser lo suficientemente bueno?

30voto

Brian Puntos 82719

Mi respuesta breve es:

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

La mayoría de traducción sencilla es pasar un diccionario de operaciones, como en una típica typeclass aplicación. Es que si typeclass Foo define tres métodos, a continuación, definir una clase/tipo de registro de nombre Foo, y, a continuación, cambiar las funciones de

Foo a => yadda -> yadda -> yadda

funciones como

Foo -> yadda -> yadda -> yadda

y en cada sitio de llamada usted sabe que el hormigón 'instancia' pasar basado en el tipo de la llamada-sitio.

He aquí 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

21voto

Gustavo Puntos 5670

Aquí es el enfoque que yo uso para simular Typeclasses (de http://code.google.com/p/fsharp-typeclasses/ ).

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

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

Y he aquí una explicación detallada de esta técnica que es de tipo seguro, extensible y como se puede ver funciona incluso con algún Tipo Superior, Typeclasses.

Iteramos.com

Iteramos es una comunidad de desarrolladores que busca expandir el conocimiento de la programación mas allá del inglés.
Tenemos una gran cantidad de contenido, y también puedes hacer tus propias preguntas o resolver las de los demás.

Powered by:

X