在 Haskell 中，如何在不同的 Traversable 之间进行 fmap？
In Haskell, how to fmap between distinct Traversables?
我们知道，fmap 的签名是 (a -> b) -> f a -> f b 其中 f 是 Functor.
为了尽可能通用并且因子代码更好，人们可能希望将 "list of things" 映射到另一个可能不同的 "list of things"，这似乎很自然。直觉上我不明白为什么它不可能或不可取。
我正在寻找的是一个函数 gmap，其行为与 fmap 相同，但具有签名 gmap :: (a -> b) -> (f a) -> (g b)，我允许到达和离开容器不同。
我不确定这在 f 和 g 是 Functors 的非常普遍的情况下是否有意义，但是 "list of things" 的想法听起来更基本上由 Traversable class 捕获，假设我最感兴趣的是迭代数据。
所以也许签名应该是gmap :: (Traversable f, Traversable g) => (a -> b) -> (f a) -> (g b)。
即使 g 与 f 的性质不同，它仍然是可以从左到右遍历的东西，所以仍然感觉应该能够映射第 k 个访问过的f 的元素到 g.
的第 k 个已访问元素
假设我的思路没有出错，那么Haskell中有这样的功能吗？
本质上，我的问题是，在 Haskell 中，您如何以最分解和最优雅的方式从一个类似列表的东西转换为另一个？
我认为您可以使用 fmap 和自然变换来做到这一点。这是一个使用 natural-transformations 包的例子，只是为了演示这个想法。
我想到的第一个自然变换是safeHead:
safeHead :: [a] -> Maybe a
safeHead [] = Nothing
safeHead (x:_) = Just x
运行 GHCi 与 natural-transformations 软件包：
Prelude Control.Natural> t = wrapNT safeHead
Prelude Control.Natural> t # [1..3]
Just 1
Prelude Control.Natural> t # []
Nothing
Prelude Control.Natural> fmap show (t # [1..3])
Just "1"
Prelude Control.Natural> fmap show (t # [])
Nothing
那么，对于自然变换 t，像 fmap f . (t #) 这样的东西会做你想做的事吗？
（这里，我假设 f 是一个普通函数 a -> b。）
您可以创建自己的类型 class，以及从一个函子到另一个函子的方法，这是将列表转换为树的一种方法的一个示例，但您可以使用您认为正确的任何内容适合你的问题。
{-# 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]
输出：
res
=> Node (Node Leaf 3 (Node Leaf 4 Leaf)) 2 (Node Leaf 5 (Node Leaf 6 Leaf))
我们在 Haskell 中经常使用的一个技巧来证明事情是不可能的，那就是尝试用它生成 "false" -- 也就是生成类型为
的值
data Void
没有构造函数的类型。如果可以使用您的类型签名生成 Void 类型的值，那么您的类型签名将无法实现。这也称为 "reducto ad absurdum" 或 "disproof by contradiction"。如果您的类型签名允许我们生成 Void 类型的值...那么 "obviously" 您的类型签名是废话，无法实现。
在这种情况下，我们是 "returning" 一个 Traversable 实例，所以让我们使用 Traversable，例如 (,) Void:
instance Traversable ((,) w) where
traverse f (x, y) = (x,) <$> f y
现在让我们像使用任何旧的函子一样使用 f。它可以是任何东西...让我们使用 Maybe 因为似乎每个人都已经理解它了。
然后，你可以这样写：
gmap :: (a -> b) -> Maybe a -> (Void, b)
哦不，这不对...看起来使用 gmap 你可以通过传入任何旧东西来创建 Void:
gmap :: (() -> ()) -> Maybe () -> (Void, ())
所以现在我的创建策略 Void:
bad :: Void
bad = fst (gmap id Nothing)
因为 Void 没有构造函数，所以 bad :: Void 类型的值不应该存在（忽略诸如无限循环或部分函数之类的东西）。因此，如果仅存在 if gmap 就可以让我们创建一个类型为 Void 的值...这一定意味着 gmap 不能以您提供的形式存在。
对于您更普遍的问题，Traversable 工作方式中的 "why" 是它只能 修改 结构。它无法 创建 它们。这里，你想创建一个g b的值，但是Traversable不能"create"它，它只能"transform"它。您的误解可能来自于您认为 Traversable 是 "list-like" 类型类：完全不是。使用 [] 作为原型可能会让您误入歧途。
我 "typical" Traversable 想象类型类的属性是 Map k，来自 containers 的 Data.Map： a Map 不是 a，而是与键关联的值。对它的任何操作都必须能够尊重此关联 属性...而不是将其视为没有额外结构的大列表。
那么可能是这样的：
replace :: (Foldable f, Traversable g) => f a -> g b -> g a
其中 g b 的所有值都被 f a 的所有值替换。如果您正在寻找练习，那么写这个实际上很有趣。基本上，replace 会 保持 与 g a 相同的 结构 ，但只是 替换 值。因此，可以这么说，只要您有 "example g b"，就可以从 f a "create" g a。如果您使用类似的东西：
replace :: [a] -> Map k b -> Map k a
然后 replace 会将第二个映射中的所有值替换为列表中的项目，并将它们替换为正确的键值。
那你可以这样写：
gmap :: (Traversable a, Traversable g) => (a -> b) -> f a -> g c -> g b
在其中获取要复制的结构的 "example" g a。
最接近 "construct" 结构的 Haskell 常见类型类是 IsList，来自 https://hackage.haskell.org/package/base-4.12.0.0/docs/GHC-Exts.html#t:IsList
这个类型类给了你两个函数，fromList 和 toList，所以你可以这样写：
throughIsList :: (IsList l, IsList m, Item l ~ Item m) => l -> m
throughIsList = fromList . toList
并让它在 Functor 秒内工作：
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
现在的问题是大多数 Functor 不是 IsList 的实例...而且许多实际实例并不完整。所以它对大多数 Functor 来说不太有用。
所以最后我觉得没有什么满意的答案。如果您正在做的事情依赖于有一个好的答案这一事实（除了 "no" 的答案）...也许我可以问一下您的 "final goal" 是什么？你打算用这种类型做什么？
（例如，在 90% 的情况下，人们会问 "is there a way I can convert monads" 或类似问题，通常他们 不想 在 一般，而是他们有 特定 类型。）
我们知道，fmap 的签名是 (a -> b) -> f a -> f b 其中 f 是 Functor.
为了尽可能通用并且因子代码更好，人们可能希望将 "list of things" 映射到另一个可能不同的 "list of things"，这似乎很自然。直觉上我不明白为什么它不可能或不可取。
我正在寻找的是一个函数 gmap，其行为与 fmap 相同，但具有签名 gmap :: (a -> b) -> (f a) -> (g b)，我允许到达和离开容器不同。
我不确定这在 f 和 g 是 Functors 的非常普遍的情况下是否有意义，但是 "list of things" 的想法听起来更基本上由 Traversable class 捕获，假设我最感兴趣的是迭代数据。
所以也许签名应该是gmap :: (Traversable f, Traversable g) => (a -> b) -> (f a) -> (g b)。
即使 g 与 f 的性质不同，它仍然是可以从左到右遍历的东西，所以仍然感觉应该能够映射第 k 个访问过的f 的元素到 g.
假设我的思路没有出错，那么Haskell中有这样的功能吗？
本质上，我的问题是，在 Haskell 中，您如何以最分解和最优雅的方式从一个类似列表的东西转换为另一个？
我认为您可以使用 fmap 和自然变换来做到这一点。这是一个使用 natural-transformations 包的例子，只是为了演示这个想法。
我想到的第一个自然变换是safeHead:
safeHead :: [a] -> Maybe a
safeHead [] = Nothing
safeHead (x:_) = Just x
运行 GHCi 与 natural-transformations 软件包：
Prelude Control.Natural> t = wrapNT safeHead
Prelude Control.Natural> t # [1..3]
Just 1
Prelude Control.Natural> t # []
Nothing
Prelude Control.Natural> fmap show (t # [1..3])
Just "1"
Prelude Control.Natural> fmap show (t # [])
Nothing
那么，对于自然变换 t，像 fmap f . (t #) 这样的东西会做你想做的事吗？
（这里，我假设 f 是一个普通函数 a -> b。）
您可以创建自己的类型 class，以及从一个函子到另一个函子的方法，这是将列表转换为树的一种方法的一个示例，但您可以使用您认为正确的任何内容适合你的问题。
{-# 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]
输出：
res
=> Node (Node Leaf 3 (Node Leaf 4 Leaf)) 2 (Node Leaf 5 (Node Leaf 6 Leaf))
我们在 Haskell 中经常使用的一个技巧来证明事情是不可能的，那就是尝试用它生成 "false" -- 也就是生成类型为
的值data Void
没有构造函数的类型。如果可以使用您的类型签名生成 Void 类型的值，那么您的类型签名将无法实现。这也称为 "reducto ad absurdum" 或 "disproof by contradiction"。如果您的类型签名允许我们生成 Void 类型的值...那么 "obviously" 您的类型签名是废话，无法实现。
在这种情况下，我们是 "returning" 一个 Traversable 实例，所以让我们使用 Traversable，例如 (,) Void:
instance Traversable ((,) w) where
traverse f (x, y) = (x,) <$> f y
现在让我们像使用任何旧的函子一样使用 f。它可以是任何东西...让我们使用 Maybe 因为似乎每个人都已经理解它了。
然后，你可以这样写：
gmap :: (a -> b) -> Maybe a -> (Void, b)
哦不，这不对...看起来使用 gmap 你可以通过传入任何旧东西来创建 Void:
gmap :: (() -> ()) -> Maybe () -> (Void, ())
所以现在我的创建策略 Void:
bad :: Void
bad = fst (gmap id Nothing)
因为 Void 没有构造函数，所以 bad :: Void 类型的值不应该存在（忽略诸如无限循环或部分函数之类的东西）。因此，如果仅存在 if gmap 就可以让我们创建一个类型为 Void 的值...这一定意味着 gmap 不能以您提供的形式存在。
对于您更普遍的问题，Traversable 工作方式中的 "why" 是它只能 修改 结构。它无法 创建 它们。这里，你想创建一个g b的值，但是Traversable不能"create"它，它只能"transform"它。您的误解可能来自于您认为 Traversable 是 "list-like" 类型类：完全不是。使用 [] 作为原型可能会让您误入歧途。
我 "typical" Traversable 想象类型类的属性是 Map k，来自 containers 的 Data.Map： a Map 不是 a，而是与键关联的值。对它的任何操作都必须能够尊重此关联 属性...而不是将其视为没有额外结构的大列表。
那么可能是这样的：
replace :: (Foldable f, Traversable g) => f a -> g b -> g a
其中 g b 的所有值都被 f a 的所有值替换。如果您正在寻找练习，那么写这个实际上很有趣。基本上，replace 会 保持 与 g a 相同的 结构 ，但只是 替换 值。因此，可以这么说，只要您有 "example g b"，就可以从 f a "create" g a。如果您使用类似的东西：
replace :: [a] -> Map k b -> Map k a
然后 replace 会将第二个映射中的所有值替换为列表中的项目，并将它们替换为正确的键值。
那你可以这样写：
gmap :: (Traversable a, Traversable g) => (a -> b) -> f a -> g c -> g b
在其中获取要复制的结构的 "example" g a。
最接近 "construct" 结构的 Haskell 常见类型类是 IsList，来自 https://hackage.haskell.org/package/base-4.12.0.0/docs/GHC-Exts.html#t:IsList
这个类型类给了你两个函数，fromList 和 toList，所以你可以这样写：
throughIsList :: (IsList l, IsList m, Item l ~ Item m) => l -> m
throughIsList = fromList . toList
并让它在 Functor 秒内工作：
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
现在的问题是大多数 Functor 不是 IsList 的实例...而且许多实际实例并不完整。所以它对大多数 Functor 来说不太有用。
所以最后我觉得没有什么满意的答案。如果您正在做的事情依赖于有一个好的答案这一事实（除了 "no" 的答案）...也许我可以问一下您的 "final goal" 是什么？你打算用这种类型做什么？
（例如，在 90% 的情况下，人们会问 "is there a way I can convert monads" 或类似问题，通常他们 不想 在 一般，而是他们有 特定 类型。）