In Haskell, how to fmap between distinct Traversables?

Question

As we know, fmap's signature is (a -> b) -> f a -> f b where f is a Functor.

It seems natural that to be as general as possible, and factor code better, one might want to map a "list of things" to another possibly distinct "list of things". Intuitively I do not see why it should not be possible, or not desirable.

What I'm looking for is a function gmap with same behavior as fmap but with that signature gmap :: (a -> b) -> (f a) -> (g b) where I'm allowing arrival and departure containers to differ.

I am not sure if this would make sense in the very general case where f and g are Functors, however the idea of a "list of things" sounds more essentially captured by the Traversable class, assuming I'm mostly interested in iterating over data.

So perhaps the signature should be gmap :: (Traversable f, Traversable g) => (a -> b) -> (f a) -> (g b).

Even if g is of different nature as f, it's still something one can traverse from left to right, so it still feels like one should be able to map the k-th visited element of f to the k-th visited element of g.

Assuming my thinking didn't go wrong, is there such a function in Haskell?

Essentially, my question, is how would you convert from one list-like thing to another in Haskell, in the most factored and elegant way?

Answer 1

One trick we often use in Haskell to show that things are not possible is trying to produce "false" with it -- aka, produce a value of type

data Void

the type with no constructors. If it is possible, using your type signature, to produce a value of type Void, then your type signature is not possible to be implemented. This is also known as "reducto ad absurdum", or "disproof by contradiction". If your type signature would allow us to produce a value of type Void...then "obviously" your type signature is bunk and cannot be implemented.

In this case we are "returning" a Traversable instance, so let's use a Traversable like (,) Void:

instance Traversable ((,) w) where
    traverse f (x, y) = (x,) <$> f y

Now let's use f as any old functor. It could be anything...let's use Maybe because it seems like everyone already understands it.

Then, you could write:

gmap :: (a -> b) -> Maybe a -> (Void, b)

Oh no, that can't be right ... it looks like using gmap you can create a Void just by passing in any old thing:

gmap :: (() -> ()) -> Maybe () -> (Void, ())

So now my strategy for creating Void:

bad :: Void
bad = fst (gmap id Nothing)

Because Void has no constructors, a value of type bad :: Void shoudn't exist (disregarding something like an infinite loop or partial function). So, if the mere existence if gmap can allow us to create a value of type Void...it must mean that gmap cannot exist in the form you gave.

---

For your more general problem, the "why" in how Traversable works is that it can only ever modify structures. It cannot create them. Here, you want to create a value of g b, but Traversable cannot "create" it, it can only "transform" it. Your misunderstanding might be coming from you thinking that Traversable is a "list-like" typeclass: it's not, quite. Using [] as a archetype might be leading you astray.

My "typical" Traversable to imagine properties of the typeclass for is Map k, from containers's Data.Map: a Map isn't a, but rather values associated with keys. Any operations on it would have to be able to respect this association property...and not treat it as a big list with no extra structure.

So what would be possible is something like:

replace :: (Foldable f, Traversable g) => f a -> g b -> g a

Where all of the values of the g b are replaced by all the values of the f a. This one is actually sort of fun to write, if you are looking for an exercise. Basically, replace would keep the same structure that the g a had, but just replace the values. So you can "create" a g a from an f a as long as you had an "example g b", so to speak. If you used something like:

replace :: [a] -> Map k b -> Map k a

then replace would replace all the values in the second map with the items in the list, replacing them at the proper key values.

Then you can write:

gmap :: (Traversable a, Traversable g) => (a -> b) -> f a -> g c -> g b

Where you take an "example" g a of the structure you want to copy.

The closest thing to being able to "construct" a structure in Haskell's common typeclasses is IsList, from https://hackage.haskell.org/package/base-4.12.0.0/docs/GHC-Exts.html#t:IsList

This typeclass gives you two functions, fromList and toList, so you could write:

throughIsList :: (IsList l, IsList m, Item l ~ Item m) => l -> m
throughIsList = fromList . toList

And making it work over Functors:

gmap :: (IsList (f a), IsList (g b), Item (f a) ~ a, Item (g b) ~ b) => (a -> b) -> f a -> g b
gmap f = fromList . map f . toList

The problem is now that most Functors are not instances of IsList...and many of the actual instances aren't total. So it's not quite usable for most Functors.

---

So in the end I don't think there is any satisfying answer. If something you were doing relies on the fact that there is a good answer (other than an answer of "no")...maybe can I ask what your "final goal" is? What are you planning on using this type for?

(For example, in 90% of situations where people ask questions like "is there a way I can convert monads" or something like that, usually they don't want to do something in general, but rather they had specific types they had in mind.)