In Haskell, how to fmap between distinct Traversables?

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.)

You can create your own type class, and a way to go from one functor to another, this is one example of one way to convert list to Tree, but you can use whatever you consider correct to fit your problem.

{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE FlexibleContexts #-}

class (Functor f, Functor g) => GFunctor f g where
  toG :: f a -> g a
  gmap :: (a -> b) -> (f a) -> (g b)
  gmap fn functor = toG $ fmap fn functor

data Tree a = Leaf | Node (Tree a) a (Tree a) deriving Show

instance Functor Tree where
  fmap f Leaf = Leaf
  fmap f (Node t1 x t2) = Node (fmap f t1) (f x) (fmap f t2)

instance GFunctor [] Tree  where
  toG [] = Leaf 
  toG [x] = Node Leaf x Leaf
  toG (x:xs) = Node (toG $ (takeHalf xs)) x ((toG $ dropHald xs))

takeHalf xs = take ((length xs) `div` 2) xs
dropHald xs = drop ((length xs) `div` 2) xs

res :: Tree Int
res = gmap (+1) [1,2,3,4,5]

output:

   res
=> Node (Node Leaf 3 (Node Leaf 4 Leaf)) 2 (Node Leaf 5 (Node Leaf 6 Leaf))