CODEWITHSUNDEEP
gogenericsfunctional-programming
cstml
cstml

Reputation: 390

How can I emulate `fmap` in Go?

I would like to emulate fmap in Go. A trivial example:

type S [A any] struct {
  contents A
}

type Functor [A any, B any] interface{
  fmap(f func(A)B) B
}

func (x S[A]) fmap (f func(A)B) S[B] {
  x.contents = f(x.contents)
  return x
}

This fails with: undefined: B with regards to the interface implementation. Is there a common workaround for this?

Upvotes: 1

Views: 472

Answers (3)

David Reynolds
David Reynolds

Reputation: 61

While it is true that Go's generics + interface methods aren't as expressive as Haskell's type-classes or Scala's generics + implicits + trait extension methods, it is still expressive enough to do the trick.

The key ingredient is to include a "phantom" type in your generic data-type, in order to avoid the undefined: B error that you were getting. Thus, a slightly altered version of your struct is:

type S[A any, B any] struct {
    contents A
} // B is our phantom type here

Also, since Go doesn't support higher kinded types (HKTs), the Functor interface you create has to be more general than a true Functor would be. You then enforce the proper type constraints via an embedding with your implementations of the interface. Here the slightly modified interface declaration would be:

type Functor[A any, B any, C any] interface{
  fmap(f func(A)B) C
} // C is technically more general than it "should" be

Now for implementing the interface ...

func (x S[A,B]) fmap (f func(A)B) S[B,A] {
  return S[B,A]{ contents: f(x.contents) }
} // notice the constraint on the C-type

Finally, to test it out ...

func main(){
  a := S[int,string]{contents: 7}
  h := func(t int)string {return "the answer is 42, duh!"}
  fmt.Println(a.fmap(h)) // {the answer is 42, duh!}
}

In order to get it to work with simple Go slices, I found that I needed to package the slice in a named type. Whenever you want to use a receiver-type that wasn't defined in your package, you need to wrap your type accordingly. For that, you'd do the following ...

type GhostArray[A any, B any] []A
// notice that you can add a phantom type to the generics

An implementation for slices could look like ... (apologies in advance b/c it is an imperative implementation ... do it with a tail-recursion if you'd rather)

func (xs GhostArray[A,B]) fmap(f func(A) B) GhostArray[B,A] {
  y := make([]B,len(xs))
  for i := 0; i < len(xs); i++ {
    y[i] = f(xs[i])
  }
  return y
}

Note that you could replace the return type with []B in this case. Go is only picky about the receiver being a named type.

The construction above has mostly erred on the side of simplicity. I'm curious about how it might be extended to better account for embedded types. I'm pretty new to Go, so I'm still learning things myself.

Upvotes: 1

Mulan
Mulan

Reputation: 135406

I would add that some of the issue you are having is that you started with an incorrect definition. There should be some immediate red flags in the proposed Functor -

type Functor [A any, B any] interface{
                  // ^ Functor should wrap a single type ⚠️
  fmap(f func(A)B) B
                // ^ should return Functor-wrapped B ⚠️
}

Fixing the issue you have above, this is what we'd like to write -

type Functor[A any] interface{
  fmap[B any](f func(A)B) Functor[B]
}

However Go warns us giving us direct feedback on the issue you are facing -

interface method must have no type parameters
undefined: B

As @jub0bs points out in the linked answer, methods may not take additional type arguments.

Upvotes: 0

jub0bs
jub0bs

Reputation: 66394

The combination of Go's generics and methods isn't as expressive as Haskell's typeclasses are; not yet, at least. In particular, as pointed out by kostix in his comment,

Go permits a generic type to have methods, but, other than the receiver, the arguments to those methods cannot use parameterized types.

(source)

Since Go methods cannot introduce new type parameters, the only way to have access to B in your fmap method is to introduce it in the declaration of your Functor type, as you did. But that doesn't make sense because, according to category theory, a functor takes one type parameter, not two.

This example may be enough to convince you that using generics and methods to emulate Haskell typeclasses in Go is a fool's errand.

One thing you can do, though, is implement fmap, not as a method, but as a top-level function:

package main

import "fmt"

type S[A any] struct {
    contents A
}

func Fmap[A, B any](sa S[A], f func(A) B) S[B] {
    return S[B]{contents: f(sa.contents)}
}

func main() {
    ss := S[string]{"foo"}
    f := func(s string) int { return len(s) }
    fmt.Println(Fmap(ss, f)) // {3}
}

(Playground)

But just because you can doesn't mean that you should. Always ask yourself whether transposing an approach from some other language to Go feels right.

Upvotes: 3

Related Questions