Обобщенное программирование в F#
От: Jack128  
Дата: 21.05.09 17:18
Оценка:
Имеем квиксорт:

let sort list =
    match list with
        | [] -> []
        | x::xs -> List.concat [(List.filter (fun i -> i <= x) xs) ;  [x] ; (List.filter (fun i -> i > x) xs)]


Этот код прекрасно сортирует и списки строк и списки чисел и даже списки списков

а вот такой банальный
let adder x y = x + y
умеет складывать только целые, но не флоаты
По ходу операция сложения не считается обобщенной, в отличии от сравнения. Есть какое нить объяснение, за что плюс обделили???
... << RSDN@Home 1.2.0 alpha 4 rev. 1218>>
Re: Обобщенное программирование в F#
От: vshabanov http://vshabanov-ru.blogspot.com
Дата: 21.05.09 19:10
Оценка:
Здравствуйте, Jack128, Вы писали:

J>Имеем квиксорт:


J>
J>let sort list =
J>    match list with
J>        | [] -> []
J>        | x::xs -> List.concat [(List.filter (fun i -> i <= x) xs) ;  [x] ; (List.filter (fun i -> i > x) xs)]
J>


J>Этот код прекрасно сортирует и списки строк и списки чисел и даже списки списков


J>а вот такой банальный

J>let adder x y = x + y
J>умеет складывать только целые, но не флоаты
J>По ходу операция сложения не считается обобщенной, в отличии от сравнения. Есть какое нить объяснение, за что плюс обделили???

За F# не скажу. Но в окемле, с которого F# срисован, вообще нет никаких generic-ов. В принципе нет. По этому у него отдельно (+) для int, (+.) для float и (+/) для Num.num. То есть не (+) обделили, а сделали хак для операции сравнения (внутри основан на том, что все значения в окемле имеют одинаковую структуру, позволяющую пробегаться по ним, не зная какого-типа эти значения).

Кстати, у этого хака есть всякие неприятные недостатки:
# type 'a t = First of 'a | Second | Third of 'a;;
type 'a t = First of 'a | Second | Third of 'a
# Second < Third 'x';;
- : bool = true
# First 'x' < Third 'x';;
- : bool = true
# First 'x' < Second;;
- : bool = false   (* опа! *)

Внутри кемла конструктор без аргумента -- просто int. А с аргументом -- уже блок с тегом. Сравнивалка ничего не знает о том, что у нас Second после First идет и говорит, что блок больше чем число.
Re[2]: Обобщенное программирование в F#
От: vshabanov http://vshabanov-ru.blogspot.com
Дата: 21.05.09 19:16
Оценка:
V>Кстати, у этого хака есть всякие неприятные недостатки:

У F# рантайм другой, такого глюка может и не быть.
Re: Обобщенное программирование в F#
От: Аноним  
Дата: 21.05.09 19:18
Оценка: 10 (2)
Здравствуйте, Jack128, Вы писали:

J>а вот такой банальный

J>let adder x y = x + y
J>умеет складывать только целые, но не флоаты
J>По ходу операция сложения не считается обобщенной, в отличии от сравнения. Есть какое нить объяснение, за что плюс обделили???

+ обделен самим дотнетом, в отличии от IComparable.
Но вот так будет работать
let inline adder2 x y = x + y

Причина — в том, что за неимением typeclass-ов F# вынужден такую обобщенность поддерживать вот такими конструкциями:
       let inline (+) (x: ^T) (y: ^U) : ^V = 
             AdditionDynamic<(^T),(^U),(^V)>  x y 
             when ^T : int32       and ^U : int32      = (# "add" x y : int32 #)
             when ^T : float       and ^U : float      = (# "add" x y : float #)
             when ^T : float32     and ^U : float32    = (# "add" x y : float32 #)
...
...
             when ^T : ^T = ((^T or ^U): (static member (+) : ^T * ^U -> ^V) (x,y))

Все это валидно лишь на момент компиляции (через систему типов дотнета такого не передать), от того и inline
Re[2]: Обобщенное программирование в F#
От: Jack128  
Дата: 21.05.09 20:13
Оценка:
Здравствуйте, vshabanov, Вы писали:

V>За F# не скажу. Но в окемле, с которого F# срисован, вообще нет никаких generic-ов. В принципе нет. По этому у него отдельно (+) для int, (+.) для float и (+/) для Num.num.


Нет, в ф шарпе "+" работает для любых чисел, и для флоатов и для интов. Ну и дженерики, конечно в нем есть, иначе как он будет со стандартными классами .NET работать
... << RSDN@Home 1.2.0 alpha 4 rev. 1218>>
Re[2]: Обобщенное программирование в F#
От: Jack128  
Дата: 21.05.09 20:28
Оценка:
Здравствуйте, <Аноним>, Вы писали:

Угу, всё ясно. Спасибо
... << RSDN@Home 1.2.0 alpha 4 rev. 1218>>
Re[2]: Обобщенное программирование в F#
От: vshabanov http://vshabanov-ru.blogspot.com
Дата: 21.05.09 20:29
Оценка:
Здравствуйте, Аноним, Вы писали:

А>+ обделен самим дотнетом, в отличии от IComparable.

А>Но вот так будет работать
А>
А>let inline adder2 x y = x + y
А>

А>Причина — в том, что за неимением typeclass-ов F# вынужден такую обобщенность поддерживать вот такими конструкциями:
А>
А>       let inline (+) (x: ^T) (y: ^U) : ^V = 
А>             AdditionDynamic<(^T),(^U),(^V)>  x y 
А>             when ^T : int32       and ^U : int32      = (# "add" x y : int32 #)
А>             when ^T : float       and ^U : float      = (# "add" x y : float #)
А>             when ^T : float32     and ^U : float32    = (# "add" x y : float32 #)
А>...
А>...
А>             when ^T : ^T = ((^T or ^U): (static member (+) : ^T * ^U -> ^V) (x,y))
А>

А>Все это валидно лишь на момент компиляции (через систему типов дотнета такого не передать), от того и inline

Правильно ли я понял, что let adder3 = adder2 опять будет только int32? Равно как и let sum = fold_left1 adder2. Т.е. настоящего ad hoc полиморфизма нет, только если везде тянуть inline. Который, по сути, как плюсовые темплейты -- набор макросов, с подстановкой в зависимости от типа (и, есть подозрение, что текст ошибки при большом кол-ве может быть похожим по размеру и степени понятности на плюсовый).
Re[3]: Обобщенное программирование в F#
От: Аноним  
Дата: 21.05.09 21:16
Оценка:
Здравствуйте, vshabanov, Вы писали:

V>Правильно ли я понял, что let adder3 = adder2 опять будет только int32?


Да, правильно.

V>Т.е. настоящего ad hoc полиморфизма нет, только если везде тянуть inline.


Тут случай неудобный — оператор + (оператор не может служить generic constraint, интерфейс — может). А так, насколько я понимаю, параметрический полиморфизм в F# основан на дотнетовских generic-ах которые совсем не inline. Хотя хаскельных тайпклассов мне лично в F# очень не хватает (предполагается, что их заменяют интерфейсы). Вот тут кстати можно посмотреть на мучительную попытку симитировать OCaml-овские функторы (которых же в F# тоже нет)..
Re[2]: Обобщенное программирование в F#
От: D. Mon Великобритания http://thedeemon.livejournal.com
Дата: 22.05.09 06:42
Оценка:
Здравствуйте, vshabanov, Вы писали:

V>За F# не скажу. Но в окемле, с которого F# срисован, вообще нет никаких generic-ов. В принципе нет. По этому у него отдельно (+) для int, (+.) для float и (+/) для Num.num. То есть не (+) обделили, а сделали хак для операции сравнения.


Проблема там не в отсутствии генериков (операторы могут быть полиморфными, например let (|>) x f = f x будет отлично работать с самыми разными типами и функциями), а в выводе типов: в выражении a + b тип аргументов выводится из операции, а не операция из типов аргументов.
Re[3]: Обобщенное программирование в F#
От: vshabanov http://vshabanov-ru.blogspot.com
Дата: 22.05.09 10:04
Оценка:
Здравствуйте, D. Mon, Вы писали:

DM>Здравствуйте, vshabanov, Вы писали:


V>>За F# не скажу. Но в окемле, с которого F# срисован, вообще нет никаких generic-ов. В принципе нет. По этому у него отдельно (+) для int, (+.) для float и (+/) для Num.num. То есть не (+) обделили, а сделали хак для операции сравнения.


DM>Проблема там не в отсутствии генериков (операторы могут быть полиморфными, например let (|>) x f = f x будет отлично работать с самыми разными типами и функциями),


Генерики и параметрический полиморфизм -- разные вещи. Генериков (разный код в зависимости от типов аргументов) в окемле нет, параметрический полиморфизм -- когда код один и тот же, но ему все равно какой тип -- есть. В окемле есть функторы, но я не назвал бы их полноценными генериками, т.к. их надо руками вызывать, а не автоматом (они конечно вроде-как изоморфны type class-ам, но дико неудобны).

DM>а в выводе типов: в выражении a + b тип аргументов выводится из операции, а не операция из типов аргументов.


Они, если ничего не путаю, не выводятся друг из друга, они унифицируются (т.е. направление может быть в обе стороны).
Re[2]: Обобщенное программирование в F#
От: gandjustas Россия http://blog.gandjustas.ru/
Дата: 23.05.09 14:52
Оценка:
Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, Jack128, Вы писали:


J>>а вот такой банальный

J>>let adder x y = x + y
J>>умеет складывать только целые, но не флоаты
J>>По ходу операция сложения не считается обобщенной, в отличии от сравнения. Есть какое нить объяснение, за что плюс обделили???

А>+ обделен самим дотнетом, в отличии от IComparable.

А>Но вот так будет работать
А>
А>let inline adder2 x y = x + y
А>

А>Причина — в том, что за неимением typeclass-ов F# вынужден такую обобщенность поддерживать вот такими конструкциями:
А>
А>       let inline (+) (x: ^T) (y: ^U) : ^V = 
А>             AdditionDynamic<(^T),(^U),(^V)>  x y 
А>             when ^T : int32       and ^U : int32      = (# "add" x y : int32 #)
А>             when ^T : float       and ^U : float      = (# "add" x y : float #)
А>             when ^T : float32     and ^U : float32    = (# "add" x y : float32 #)
А>...
А>...
А>             when ^T : ^T = ((^T or ^U): (static member (+) : ^T * ^U -> ^V) (x,y))
А>

А>Все это валидно лишь на момент компиляции (через систему типов дотнета такого не передать), от того и inline

Ну для этого придуман стандартный workaround. Еслить иерархия интерфейсов унаследованных от INumeric<T>, которые задают операции. И есть фнункция Microsoft.FSharp.Math.GlobalAssociations.GetNumericAssociation позволяющая получить экземпляр такого интерфейса по типу.
Re[3]: Обобщенное программирование в F#
От: Jack128  
Дата: 24.05.09 11:42
Оценка:
Здравствуйте, gandjustas, Вы писали:

G>Ну для этого придуман стандартный workaround. Еслить иерархия интерфейсов унаследованных от INumeric<T>, которые задают операции. И есть фнункция Microsoft.FSharp.Math.GlobalAssociations.GetNumericAssociation позволяющая получить экземпляр такого интерфейса по типу.


Великолепно. ТО есть компилятору F# должно быть все равно, для реализации сравнения у него есть IComparable, а для реализации плюсов/минусов — INumeric ?? но практика то другое показывает.
... << RSDN@Home 1.2.0 alpha 4 rev. 1218>>
Re[4]: Обобщенное программирование в F#
От: mryau Россия http://woodland.ru/~wjdogs
Дата: 25.05.09 07:52
Оценка: 2 (1)
Здравствуйте, Jack128, Вы писали:


#light
#r @"FSharp.PowerPack.dll"
open Microsoft.FSharp.Math.GlobalAssociations

module GenAdder =
  let (+) (a:'a) (b:'a) =
    let v = GetNumericAssociation<'a>()
    v.Add(a,b)

  let add3 (a:'a) (b:'a) (c:'a) =
    a + b + c



> GenAdder.add3 1 2 3;;
val it : int = 6
> GenAdder.add3 1.0 2.0 3.0;;
val it : float = 6.0
> GenAdder.add3 1I 2I 3I;;
val it : bigint = 6I


Этот вариант медленней let inline, поэтому его и редко используют.

G>>Ну для этого придуман стандартный workaround. Еслить иерархия интерфейсов унаследованных от INumeric<T>, которые задают операции. И есть фнункция Microsoft.FSharp.Math.GlobalAssociations.GetNumericAssociation позволяющая получить экземпляр такого интерфейса по типу.


J>Великолепно. ТО есть компилятору F# должно быть все равно, для реализации сравнения у него есть IComparable, а для реализации плюсов/минусов — INumeric ?? но практика то другое показывает.
f#
Re[5]: Обобщенное программирование в F#
От: Аноним  
Дата: 26.05.09 10:13
Оценка: 1 (1) :)
Здравствуйте, mryau, Вы писали:

M>
>> GenAdder.add3 1 2 3;;
M>val it : int = 6
>> GenAdder.add3 1.0 2.0 3.0;;
M>val it : float = 6.0
>> GenAdder.add3 1I 2I 3I;;
M>val it : bigint = 6I
M>


M>Этот вариант медленней let inline, поэтому его и редко используют.


Не только медленее, но и еще и спокойно компилирует вот такое:
let r3 = add3 "one" "two" "three"
let r4 = add3 (new obj()) (new obj()) (new obj())

Падает только в рантайме.
Re[6]: Обобщенное программирование в F#
От: Jack128  
Дата: 26.05.09 20:40
Оценка:
Здравствуйте, <Аноним>, Вы писали:


А>Не только медленее, но и еще и спокойно компилирует вот такое:

А>
А>let r3 = add3 "one" "two" "three"
А>let r4 = add3 (new obj()) (new obj()) (new obj())
А>

А>Падает только в рантайме.

Ну например

let comp x y = x > y
let result = comp (new Dictionary<object, object>) (new Dictionary<object, object>)

тоже падает только в рантайм. тем не менее разрабов это не смутило.
Вобщем как я понял у них еще нету единой политики...
... << RSDN@Home 1.2.0 alpha 4 rev. 1218>>
Re[6]: Обобщенное программирование в F#
От: mryau Россия http://woodland.ru/~wjdogs
Дата: 27.05.09 08:14
Оценка:
Здравствуйте, Аноним, Вы писали:
Ага, но никто не мешает вместо GetNumericAssociation<'a>() написать TryGetNumericAssociation<'a>()
и использовать monadic syntax:

type Maybe<'a> = (unit -> 'a option)

let succeed x : Maybe<'a> = fun () -> Some(x)
let fail : Maybe<'a> = fun () -> None
let run (a: Maybe<'a>) = a()
let bind p rest = match run p with None -> fail | Some r -> (rest r)
let delay f = fun () -> run (f ())

type MaybeBuilder() =
  member this.Return(x) = succeed x
  member this.Let(p,rest) = rest p
  member this.Bind(p,rest) = bind p rest
  member this.Delay(f) = delay f

let maybe = new MaybeBuilder()

let add (a:'a) (b:'a) =
  maybe {
    match TryGetNumericAssociation<'a>() with
    | Some v -> return (v.Add(a,b))
    | _ -> return! fail
  }

let add3 (a:'a) (b:'a) (c:'a) =
  maybe {
    let! ab = add a b
    let! abc = add ab c
    return abc
  }



> let r1 = add 1 2;;
val r1 : (unit -> int option)
> r1();;
val it : int option = Some 3
> let r2 = add "1" "2";;
val r2 : (unit -> string option)
> r2();;
val it : string option = None
> let r3 = add3 "one" "two" "three";;
val r3 : (unit -> string option)
> r3();;
val it : string option = None


А>Здравствуйте, mryau, Вы писали:


А>Не только медленее, но и еще и спокойно компилирует вот такое:

А>
А>let r3 = add3 "one" "two" "three"
А>let r4 = add3 (new obj()) (new obj()) (new obj())
А>

А>Падает только в рантайме.
f#
Re[7]: Обобщенное программирование в F#
От: Аноним  
Дата: 27.05.09 09:55
Оценка:
Здравствуйте, mryau, Вы писали:

M>Ага, но никто не мешает вместо GetNumericAssociation<'a>() написать TryGetNumericAssociation<'a>()

M>и использовать monadic syntax:

Кстати, интересно почему в 'стандартной поставке' нет монадной обвязки для Option? Можно кстати упростить до Maybe 'канонического' вида:
type 'a Maybe = 'a option

let succeed = Some
let fail = None
let (>>=) p rest =
    match p with
        |Some r -> rest r
        |None -> fail

type MaybeBuilder() =
  member this.Return(x) = succeed x
  member this.Let(p,rest) = rest p
  member this.Bind(p,rest) = p >>= rest
  member this.Delay(f) = f()

let maybe = new MaybeBuilder()
  
let add a b =
  TryGetNumericAssociation<_>()
    >>= fun v -> Some (v.Add(a,b))

let add3 a b c =
  maybe {
    let! ab = add a b
    let! abc = add ab c
    return abc
  }


Но главное, что проблемы отсутствия проверки на этапе компиляции этот код не решает. В общем по-нормальному Num в F# пока повторить не удастся, как мне кажется.
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.