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

Question

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

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

Для толпы: Как перевести классы типов (идиома 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

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

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

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

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

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

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

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

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

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

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

Помоги мне

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

46

oop haskell functional-programming f# typeclass

Источник

user93221 27 окт '10 в 15:15

2 ответа

Решение

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

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

Самый простой перевод - передать словарь операций, как в одной типичной реализации класса типов. Это если класс типов 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

31

Источник

user19299 27 окт '10 в 15:23

Другие вопросы по тегам oop haskell functional-programming f# typeclass

user446822 08 дек '11 в 23:56 2011-12-08 23:56 · Accepted Answer · 2011-12-08 23:56

Вот подход, который я использую для имитации классов типов (из 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: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]

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

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

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