CODEWITHSUNDEEP
recursionf#functordiscriminated-union
Søren Debois
Søren Debois

Reputation: 5688

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.

Upvotes: 2

Views: 176

Answers (1)

Gus
Gus

Reputation: 26174

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

Upvotes: 4

Related Questions