Generalized `fold` or how to perform `fold` and `map` at a time

Question

(Apology by the title, I can't do better)

My question is to find some generalized struct or "standard" function to perform the next thing:

xmap :: (a -> b) -> f a -> g b

then, we can map not only elements, by also the entire struct.

Some (not real) example

xmap id myBinaryTree :: [a]

at the moment, I must to do a explicit structure conversor (typical fromList, toList) then

toList . fmap id   -- if source struct has map
fmap id . fromList -- if destination struct has map

(to perform toStruct, fromStruct I use fold).

Exists some way to generalize to/from structs? (should be) Exists that function (xmap)?

Thank you!! :)

Answer 1

As f and g are functors, a natural transformation is what you're looking for (see also You Could Have Defined Natural Transformations). So a transformation like

f :~> g = forall a. f a -> g a 

is needed to create xmap which is then just

xmap :: (a -> b) -> (f :~> g) -> (f a -> g b)
xmap f n = map f . n

You still need to define types of (f :~> g), but there' not a general way of doing that.

Answer 2

I'd like to add to tel's answer (I got my idea only after reading it) that in many cases you can make general natural transformation that will work similarly to foldMap. If we can use foldMap, we know that f is Foldable. Then we need some way how to constructs elements of g a and combine them together. We can use Alternative for that, it has all we need (pure, empty and <|>), although we could also construct some less general type class for this purpose (we don't need <*> anywhere).

{-# LANGUAGE TypeOperators, RankNTypes #-}
import Prelude hiding (foldr)
import Control.Applicative
import Data.Foldable

type f :~> g = forall a. f a -> g a

nt :: (Functor f, Foldable f, Alternative g) => f :~> g
nt = foldr ((<|>) . pure) empty

Then using tel's xmap

xmap :: (a -> b) -> (f :~> g) -> (f a -> g b)
xmap f n = map f . n

we can do things like

> xmap (+1) nt (Just 1) :: [Int]
[2]