Jak mogę przetłumaczyć klasę typu Haskell na F #?

Question

Próbuję przetłumaczyć Strzały z biblioteki rdzenia Haskella na F # (Myślę, że jest to dobre ćwiczenie, aby lepiej zrozumieć Arrows i F #, i być może będę mógł je wykorzystać w projekcie, nad którym pracuję.) Jednak bezpośrednie tłumaczenie nie jest możliwe z powodu różnicy w paradygmatach. Haskell używa klas typu do wyrażania tych rzeczy, ale nie jestem pewien, co F # konstruuje najlepiej mapuje funkcjonalność klas typów z idiomami F #. Mam kilka przemyśleń, ale pomyślałem, że najlepiej jest go tu przywołać i zobaczyć, co uważano za najbardziej zbliżone do funkcjonalności.

Dla tłumu tl: Jak mogę przetłumaczyć klasy typów (idiom Haskella) na F # idiomatic?

Dla tych zaakceptowaniem mojego długiego wyjaśnienia:

Ten kod z Haskell standardowych lib jest przykładem tego, co staram się tłumaczyć:

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 

Próba 1: Moduły, Simple Rodzaje Niech Wiązania

Mój pierwszy strzał w tym było po prostu map rzeczy nad bezpośrednio za pomocą modułów dla organizacji, jak:

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

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

To działa, ale traci na polimorfizmie, ponieważ nie wdrażam Kategorii i nie mogę łatwo wprowadzić bardziej wyspecjalizowanych Strzał.

Próba 1a: Refining użyciu podpisów i rodzajów

Jednym ze sposobów, aby poprawić pewne problemy z próba 1 jest użycie .fsi plik zdefiniowanie metod (tak rodzaje egzekwować łatwiej) i korzystać z niektórych proste wpisz ulepszenia, aby specjalizować.

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

ale plik FSI nie mogą być ponownie wykorzystane (aby wymusić rodzaje funkcji let związany) dla innych implementacjach, a typ zmiany nazwy/enkapsulacji rzeczy jest trudne.

Próba 2: Modele obiektowe i interfejsy

Racjonalizacja że F # jest zbudowany tak, aby OO również, może hierarchia typ jest właściwy sposób to zrobić.

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" 

Oprócz ile bólu może być, aby uzyskać to, co powinno być metody statyczne (jak komp i innych operatorów) zachowywać się jak metody instancji, istnieje również potrzeba wyraźnie uskok wyniki. Nie jestem też pewny, czy ta metodologia wciąż oddaje pełną ekspresję polimorfizmu klasy typu. Utrudnia to również używanie rzeczy, które MUSZĄ być statycznymi metodami.

Próba 2a: Refining użyciu rozszerzeń typów

Więc jeszcze jeden potencjalny dystynkcja jest zadeklarować interfejsów jako nagie, jak to możliwe, a następnie użyć metody rozszerzenie dodać funkcję do wszystkich typów wykonawczych.

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

Ach, ale to blokuje mi się za pomocą jednej metody dla wszystkich typów IArrow.Jeśli chciałbym nieco inny (& & &) dla ListArrows, co mogę zrobić? Nie próbowałem jeszcze tej metody, ale przypuszczam, że mogę śledzić (& & &), lub przynajmniej zapewnić bardziej wyspecjalizowaną wersję, ale mam wrażenie, że nie mogę wymusić użycia poprawnego wariantu.

Help me

Więc co mam zrobić tutaj? Czuję, że OO powinien być wystarczająco potężny, aby zastąpić klasy typów, ale nie potrafię wymyślić, jak to zrobić w F #. Czy któraś z moich prób była blisko? Czy któryś z nich jest "tak dobry, jak to tylko możliwe" i który będzie musiał być wystarczająco dobry?

Answer 1

Oto podejście używam do symulacji Typeclasses (z http://code.google.com/p/fsharp-typeclasses/).

W przypadku, o Strzałki może być coś takiego:

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 

Zastosowanie:

> 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] 

Uwaga: Należy używać id'() zamiast id

Aktualizacja: ci potrzebujesz F # 3.0, aby skompilować ten kod, w przeciwnym razie here's the F# 2.0 version.

I szczegółowe wyjaśnienie tej techniki, która jest bezpieczna dla rodzaju, rozszerzalna i jak widać działa nawet w niektórych typach wyższych typów.

Answer 2

Moja krótka odpowiedź brzmi:

OO nie jest wystarczająco silne, aby zastąpić zajęcia typu.

Najprostszym tłumaczeniem jest przekazanie słownika operacji, jak w jednej typowej implementacji typeclass. To jest, jeśli typeclass Foo definiuje trzy sposoby, a następnie zdefiniować typ klasa/zapis nazwie Foo, a następnie zmienić funkcje

Foo a => yadda -> yadda -> yadda 

do funkcji jak

Foo -> yadda -> yadda -> yadda 

i na każdym miejscu połączenia wiesz betonu "instancja" do przekazania na podstawie typu na stronie połączenia.

Oto krótki przykład tego, co mam na myśli:

// 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"] 

Zobacz także

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