Рекурсивные размеченные союзы и карта

Мне нужен тип дерева и карта на них, поэтому я делаю это:

type 'a grouping = 
    G of ('a * 'a grouping) list
    with 
        member g.map f = 
            let (G gs) = g
            gs |> List.map (fun (s, g) -> f s, g.map f) |> G

Но это заставляет меня задуматься:

  1. Участник map является шаблонным. В Haskell GHC реализовал бы для меня fmap (... deriving (Functor)). Я знаю, что в F# нет классов типов, но есть ли другой способ избежать самостоятельного написания карты на F#?
  2. Можно ли как-то избежать строки let (G gs) = g?
  3. Вся эта конструкция как-то неидиоматична? Мне это кажется странным, но, может быть, это просто потому, что размещение членов в типах суммы для меня в новинку.

recursion f# discriminated-union functor
person Søren Debois    schedule 25.03.2014    source источник
comment
Рассматривали ли вы функцию let-bound let rec map f (G gs) = gs |> List.map (fun (s, g) -> f s, map f g) |> G?   -  person kaefer    schedule 26.03.2014
comment
Ага. Однако я хотел избежать этого: казалось, что изящная вещь в использовании member заключается в том, что я избегаю загрязнения своего локального пространства имен вещами с именами mapG и foldG и т.п. И я не могу позволить связать член, верно?   -  person Søren Debois    schedule 26.03.2014
comment
@SørenDebois: Это настолько хорошо, насколько это возможно. Если вы попытаетесь эмулировать Haskell на F#, ваш код окажется намного более запутанным, чем ваше текущее (прямое) решение.   -  person Daniel    schedule 26.03.2014
comment
@SørenDebois - может быть немного более идиоматично сделать это определение с привязкой к лету в модуле Grouping; тогда вы можете просто открыть модуль, если собираетесь его часто использовать, и использовать map безоговорочно.   -  person kvb    schedule 26.03.2014

Ответы (1)


arrow_upward
4
arrow_downward

Я не думаю, что есть способ автоматического получения map, однако есть способ эмулировать классы типов в F# Ваш код можно записать так:

#r @"FsControl.Core.dll"
#r @"FSharpPlus.dll"

open FSharpPlus
open FsControl.Core.TypeMethods

type 'a grouping = 
    G of ('a * 'a grouping) list
    with
        // Add an instance for Functor 
        static member instance (_:Functor.Map, G gs, _) = fun (f:'b->'c) -> 
            map (fun (s, g) -> f s, map f g) gs |> G

// TEST
let a = G [(1, G [2, G[]] )]
let b = map ((+) 10) a        // G [(11, G [12, G[]] )]

Обратите внимание, что map действительно перегружен, первое приложение, которое вы видите, вызывает экземпляр для List<'a>, а второе — экземпляр для grouping<'a>. Так что он ведет себя как fmap в Haskell.

Также обратите внимание, что таким образом вы можете разложить G gs без создания let (G gs) = g

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

В любом случае, я согласен с @kvb в том, что определение map в модуле в F#+ несколько более идиоматично. это соглашение также используется, поэтому у вас есть общий map и конкретный ModuleX.map

person Gus    schedule 26.03.2014
comment
Интригующий. Не могли бы вы объяснить или указать где-нибудь, где я могу прочитать о том, что происходит с instance (_:Functor.Map, G gs, _)? - person Søren Debois; 27.03.2014
comment
Посмотрите файл readme на github.com/gmpl/FsControl/blob/. master/README.md Мне будут интересны ваши отзывы, поэтому, пожалуйста, сообщите мне, если вы считаете, что я могу добавить что-то еще к объяснению. - person Gus; 27.03.2014