Как перевести класс типа Haskell в F #?

Я пытаюсь перевести базовую библиотеку Haskell Arrows в F # (я считаю это хорошим упражнением для понимания стрелок и F # лучше, и я мог бы использовать их в проекте, над которым я работаю.) Однако, прямой перевод невозможен из-за различий в парадигмах. Haskell использует типы классов для выражения этого материала, но я не уверен, что конструкция F # наилучшим образом отображает функциональность классов типов с идиомами F #. У меня есть несколько мыслей, но я решил, что лучше всего поднять его здесь и посмотреть, что считается самым близким по функциональности.

Для толпы tl; dr: Как перевести типы классов (икону Haskell) в идиоматический код F #?

Для тех, кто принимает мое длинное объяснение:

Этот код из стандартной библиотеки Haskell является примером того, что я пытаюсь перевести:

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

Попытка 1: Модули, Простые типы, Ограничения привязки

Мой первый выстрел в этом состоял в том, чтобы просто сопоставить вещи непосредственно с помощью модулей для организации, например:

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

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

Это работает, но оно теряет полиморфизм, поскольку я не реализую Категории и не могу легко реализовать более специализированные стрелки.

Попытка 1a: Очистка с использованием сигнатур и типов

Один из способов исправить некоторые проблемы с попыткой 1 - это использовать файл .fsi для определения методов (чтобы упростить типы) и использовать некоторые простые настройки типа для специализации.

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

Но файл fsi не может быть повторно использован (для принудительного применения типов связанных функций) для других реализаций, а материал переименования типа/инкапсуляции является сложным.

Попытка 2: Объектные модели и интерфейсы

Рационализация того, что F # также построена как OO, возможно, иерархия типов - это правильный способ сделать это.

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"

Помимо того, сколько боли может быть связано с тем, что должно быть статическими методами (такими как comp и другими операторами), чтобы действовать как методы экземпляра, также необходимо явно повысить результаты. Я также не уверен, что эта методология все еще захватывает полную выразительность полиморфизма типового класса. Это также затрудняет использование вещей, которые ДОЛЖНЫ быть статическими методами.

Попытка 2a: Очистка с использованием расширений типов

Таким образом, еще одно потенциальное усовершенствование заключается в том, чтобы объявить интерфейсы как можно более гладкими, а затем использовать методы расширения для добавления функциональности ко всем типам реализации.

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

А, но это заставляет меня использовать один метод для всех типов IArrow. Если бы я хотел немного отличаться (& & &) для ListArrows, что я могу сделать? Я еще не пробовал этот метод, но я бы предположил, что могу затенять (& & &) или, по крайней мере, предоставить более специализированную версию, но я чувствую, что не могу обеспечить использование правильного варианта,

Помогите мне

Так что я должен здесь делать? Я чувствую, что OO должно быть достаточно мощным, чтобы заменить классы типа, но я не могу понять, как это произошло в F #. Были ли какие-либо из моих попыток закрыты? Кто-нибудь из них "так хорош, как он", и это должно быть достаточно хорошим?

Ответы

Ответ 1

Здесь подход, который я использую для моделирования Typeclasses (из http://code.google.com/p/fsharp-typeclasses/).

В вашем случае для Arrows может быть что-то вроде этого:

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

Использование:

> 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:[email protected]>

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

Примечание: используйте id'() вместо id

Обновление: вам нужно F # 3.0 для компиляции этого кода, иначе здесь версия F # 2.0. p >

И здесь подробное объяснение этой техники, которая безопасна по типу, расширяема и, как вы можете видеть, работает даже с некоторыми более крупными типексами.

Ответ 2

Мой короткий ответ:

OO недостаточно мощно, чтобы заменить классы классов.

Самый простой перевод состоит в том, чтобы передать словарь операций, как в одной типичной реализации типа. То есть, если typeclass Foo определяет три метода, затем определите тип класса/записи с именем Foo, а затем измените функции

Foo a => yadda -> yadda -> yadda

для таких функций, как

Foo -> yadda -> yadda -> yadda

и на каждом сайте вызова вы знаете конкретный "экземпляр" для передачи по типу на сайте вызова.

Вот краткий пример того, что я имею в виду:

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

См. также

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