广义的"fold"或如何一次执行"fold"和"map" [英] Generalized `fold` or how to perform `fold` and `map` at a time

问题描述

(由标题表示歉意，我做得更好)

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

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

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]

此刻，我必须先做一个明确的结构转换器(典型的fromList，toList)

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

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

是否存在某种通用化to/from结构的方法? (应该) 是否存在该功能(xmap)?

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

谢谢！！ :)

推荐答案

我想添加到电话答案 (我只有在阅读它后才明白我的想法)在许多情况下，您可以进行一般的自然变换，其作用与foldMap类似.如果我们可以使用foldMap，我们知道f是Foldable.然后，我们需要一些方法来构造g a的元素并将它们组合在一起.我们可以为此使用Alternative，它具有我们需要的所有内容(pure，empty和<|>)，尽管我们也可以为此目的构造一些不太通用的类型类(我们不需要<*>任何地方).

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

然后使用电话的xmap

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

我们可以做类似的事情

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

这篇关于广义的"fold"或如何一次执行"fold"和"map"的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！