# 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 `Functor`

s:

```
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 `Functor`

s are not instances of `IsList`

...and many of the actual instances aren't total. So it's not quite usable for most `Functor`

s.

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