广义的"折叠"或如何一次执行"折叠"和"地图"

Question

(通过标题道歉,我不能做得更好)

我的问题是找到一些通用的结构或"标准"函数来执行下一件事:

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

那么,我们不仅可以映射元素,还可以映射整个结构.

一些(不是真实的)例子

xmap id myBinaryTree :: [a]

此刻,我必须做一个明确的结构conversor(典型fromList,toList)然后

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

(执行toStruct,fromStruct我使用fold).

存在某种推广to/ from结构的方式？(应该)存在函数(xmap)？

谢谢!!:)

Answer 1

由于f和g是仿函数,一个自然转化是你要找的(见什么你可以这样来定义自然变换).所以转型就好

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

需要创建xmap然后才是

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

你仍然需要定义类型(f :~> g),但没有一般的方法.

Answer 2

我想补充一下tel 的答案（我只是在阅读后才得到我的想法），在许多情况下，您可以进行一般的自然转换，其工作方式与foldMap. 如果我们可以使用foldMap，我们就知道f是Foldable。然后我们需要某种方法来构造元素g a并将它们组合在一起。我们可以使用Alternative它，它具有我们需要的一切（pure，empty和<|>），尽管我们也可以为此目的构造一些不太通用的类型类（我们不需要<*>任何地方）。

{-# 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

然后使用电话xmap

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

我们可以做类似的事情

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