Search code examples
recursionf#functordiscriminated-union

Recursive discriminated unions and map


I need a type of tree and a map on those, so I do this:

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

But this makes me wonder:

  1. The map member is boilerplate. In Haskell, GHC would implement fmap for me (... deriving (Functor)). I know F# doesn't have typeclasses, but is there some other way I can avoid writing map myself in F#?
  2. Can I somehow avoid the line let (G gs) = g?
  3. Is this whole construction somehow non-idiomatic? It looks weird to me, but maybe that's just because putting members on sum types is new to me.

Solution

  • I don't think there is a way to derive automatically map, however there's a way to emulate type classes in F#, your code can be written like this:

    #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[]] )]
    

    Note that map is really overloaded, the first application you see calls the instance for List<'a> and the second one the instance for grouping<'a>. So it behaves like fmap in Haskell.

    Also note this way you can decompose G gs without creating the let (G gs) = g

    Now regarding what is idiomatic I think many people would agree your solution is more F# idiomatic, but to me new idioms should also be developed in order to get more features and overcome current language limitations, that's why I consider using a library which define clear conventions also idiomatic.

    Anyway I agree with @kvb in that it's slightly more idiomatic to define map into a module, in F#+ that convention is also used, so you have the generic map and the specific ModuleX.map