英文:
Haskell : what is the sense in: instance Functor ((->) r)
问题
我承认,我的问题可能源于知识的缺乏,表达也许有些模糊。但我尝试理解,有些疑惑并且无法解决它们。
所以 GHC.Base 有这样的定义,其中的意义是什么:
instance Functor ((->) r) where
fmap = (.)
-
从编程语言的角度来看:
我们真的有一个基本的构造->
,我认为比任何其他东西都更基础,但也许只是术语,你将其描述为非常派生的构造的一部分(instance Functor
)。这有什么意义呢?->
就是->
。只要在 Haskell 中有意义地描述了->
,Functor 就有意义。但反过来并不成立:只有在 Haskell 库中正确描述了 Functor 时,->
才有意义。 -
从 lambda 演算的角度来看:
2.1 如果从“常识”的定义来看,-> r
是围绕着 r 的一个容器(我们称之为Any_f
),那么fmap
函数应该如何工作呢?
fmap
应该将值更改为容器,但不应更改容器的结构,请尝试编写它:
fmap f (Any_f x) <=> Any_f (f x)
(是的,这是非类型化的 lambda 演算)
2.2. 但让我们看看在 Haskell 中如何定义 Functor ((->) r):
instance Functor ((->) r) where
fmap = (.)
-- 或者换句话说(引号是故意的):
-- fmap f (Any_f x) = f (Any_f x)
-- fmap :: forall a, b, c => (b -> c) -> (a -> b) -> (a -> c)
所以:
- “常识”(不改变容器结构)告诉我们写成:
fmap f (Any_f_as_container x) = Any_f_as_container (f x)
- 类型要求告诉我们写成:
fmap f (any_f_as_container x) = f (Any_f_as_container x)
这是否意味着 "instance Functor ((->) r)" 是没有意义的?如果不是的话,当它改变最外层的函数(容器本身,而不是容器的值)时,它具有什么意义呢?
英文:
I admit, that my question may stem from a lack of knowledge and be rather vague.
But I try to understand, have some doubts and can't resolve them.
So GHC.Base have such definition, and what is the sense in it:
instance Functor ((->) r) where
fmap = (.)
-
From the viewpoint of programming language:
We have really base construction (->), I think more base than anything, but maybe terms, and you describe it as a part of very derivative construction (instance Functor). What is the sense? (->) is (->). Functor have any sense as far as (->) described under Haskell hood meaningfully. But not vice versa: (->) have sense while Functor described in Haskell libraries correctly. -
From the viewpoint of lambda calculus:
2.1 If from "common sense" definition "(->) r" is a container around r (let's call it "Any_f"), then how function fmap shoul work?
fmap should change value into container, but do not change container-structure, try to write it.fmap f (Any_f x) <=> Any_f (f x)
(yes, this is non-typed lambda calculus)
2.2. But let's look how Functor ((->) r) defined in Haskell:
instance Functor ((->) r) where
fmap = (.)
-- Or in other words (quotation marks intentionaly):
-- fmap f (Any_f x) = f (Any_f x)
-- fmap :: forall a, b, c => (b -> c) -> (a -> b) -> (a -> c)
So:
-
"common sense" (not change container structure) tells us to write:
fmap f (Any_f_as_container x) = Any_f_as_container (f x)
-
types requirements tell us to write:
fmap f (any_f_as_container x) = f (Any_f_as_container x)
Doesn't this means that "instance Functor ((->) r)" is meaningless? And if not - what sense does it has when it changes outermost function (container itself, not container value)?
答案1
得分: 6
我将为您翻译的部分:
我将尝试说服您,fmap = (.)
真的是一种保持容器形状不变,但将函数应用于容器中所有元素的事情。但在我们为 (->)
这个例子之前,让我们先为一些更简单的类型做一下。具体来说,让我们为具有特定数量元素的容器做一下。也就是说,具有确切两个元素的容器将是 TwoF
,而没有元素的将是 ZeroF
。像这样:
data ZeroF a = ZeroF
data OneF a = OneF a
data TwoF a = TwoF a a
data ThreeF a = ThreeF a a a
这些类型的 Functor
实例应该是什么样的呢?嗯,OneF
的实例看起来恰好与您的问题中描述的一样:
instance Functor OneF where
fmap f (OneF x) = OneF (f x)
其他的看起来相当相似,只是根据元素的数量多少,多次(或少次)应用 f
来保持容器的形状不变。这里它们都在,用一些创造性的空格来突出显示相似性/模式:
instance Functor ZeroF where fmap f (ZeroF ) = ZeroF
instance Functor OneF where fmap f (OneF x0 ) = OneF (f x0)
instance Functor TwoF where fmap f (TwoF x0 x1 ) = TwoF (f x0) (f x1)
instance Functor ThreeF where fmap f (ThreeF x0 x1 x2) = ThreeF (f x0) (f x1) (f x2)
希望您现在同意,这绝对具有您在问题中描述的 Functor
实例的特点:保持容器的形状不变,并将给定的函数 f
应用于容器中的每个元素。
所以,这些是具有给定数量元素的容器。现在,让我们为这些容器编写访问器,也就是说,我们想要类似于列表的 (!!)
的等效物,给定一个数字,我们从容器中提取该字段。由于 ZeroF
中没有元素,我们需要一个具有零值的索引类型;而对于 ThreeF
,我们需要具有三个值的索引类型。
data Zero
data One = One0
data Two = Two0 | Two1
data Three = Three0 | Three1 | Three2
索引函数的类型看起来像这样:
indexZero :: ZeroF a -> Zero -> a
indexOne :: OneF a -> One -> a
indexTwo :: TwoF a -> Two -> a
indexThree :: ThreeF a -> Three -> a
我不会实现它们全部 - 它们非常直观 - 但这里有一个示例,以防不明显的话,希望能给您一个想法。
indexTwo (TwoF x0 x1) Two0 = x0
indexTwo (TwoF x0 x1) Two1 = x1
事实证明,这些索引函数有一个反函数 - 如果您给我一个函数,当给定一个索引时会产生一个值,那么我可以给您一个包含这些值的容器。类型看起来像这样:
tabulateZero :: (Zero -> a) -> ZeroF a
tabulateOne :: (One -> a) -> OneF a
tabulateTwo :: (Two -> a) -> TwoF a
tabulateThree :: (Three -> a) -> ThreeF a
(您能看出这是反函数的正确类型吗?请注意,例如,TwoF a -> Two -> a
与 TwoF a -> (Two -> a)
是相同类型!)为了让您对这些是如何实现的有一个想法,以防不明显,我们只需将索引函数应用于每个索引:
tabulateZero ix = ZeroF
tabulateOne ix = OneF (ix One0 )
tabulateTwo ix = TwoF (ix Two0 ) (ix Two1 )
tabulateThree ix = ThreeF (ix Three0) (ix Three1) (ix Three2)
不难证明 tabulateX . indexX = id
和 indexX . tabulateX = id
对于每个 X
都成立,即制表确实是索引的反函数。
好了,但现在请稍等一下,看看我们刚刚做了什么:我们已经将一个函数(例如 Two -> a
)转换为一个容器(例如 TwoF a
),反之亦然。类型 Two -> a
和 TwoF a
从道义上来说,完全相同。因此,似乎有理由认为我们可以为 Two -> a
实现 fmap
- 例如,通过适当地转换为 TwoF a
,然后再转换回来!
twomap :: (a -> b) -> (Two -> a) -> (Two -> b)
twomap f = indexTwo . fmap f . tabulateTwo
让我们可视化一下这是如何工作的。我们将从一个任意的索引函数开始:
\case Two0 -> x0; Two1 -> x1
现在我们经历整个过程:
\case Two0 -> x0; Two1 -> x1
tabulateTwo
TwoF x0 x1
fmap f
TwoF (f x0) (f x1)
indexTwo
\case Two0 -> f x0; Two1 -> f x1
由于 f
在两个分支中都被应用,我们可以将其
英文:
I will try to convince you that fmap = (.)
really is a thing that leaves a container's shape the same, but applies a function to all the elements in the container. But before we do that for (->)
, let's do it for some simpler types. Specifically, let's do it for types that are containers with a specific number of elements -- i.e., a container with exactly two elements will be TwoF
, while one with no elements will be ZeroF
. Like this:
data ZeroF a = ZeroF
data OneF a = OneF a
data TwoF a = TwoF a a
data ThreeF a = ThreeF a a a
What should the Functor
instances for these look like? Well, the one for OneF
looks exactly like in your question:
instance Functor OneF where
fmap f (OneF x) = OneF (f x)
The other ones look pretty similar -- just applying f
more (or fewer) times to account for the fact that there are more (or fewer) elements. Here they all are, with some creative whitespace to highlight the similarities/pattern:
instance Functor ZeroF where fmap f (ZeroF ) = ZeroF
instance Functor OneF where fmap f (OneF x0 ) = OneF (f x0)
instance Functor TwoF where fmap f (TwoF x0 x1 ) = TwoF (f x0) (f x1)
instance Functor ThreeF where fmap f (ThreeF x0 x1 x2) = ThreeF (f x0) (f x1) (f x2)
Hopefully for now you agree that this definitely has the flavor of Functor
instance that you described in your question: keep the shape of the container the same, and apply the given function f
to each element contained within.
So those are containers with a given number of elements. Now, let's write accessors for these containers -- i.e. we want the equivalent of (!!)
for lists, where given a number, we pull out that field from the container. Since there's zero elements in a ZeroF
, we'll need an indexing type with zero values; while for ThreeF
we need an indexing type with three values.
data Zero
data One = One0
data Two = Two0 | Two1
data Three = Three0 | Three1 | Three2
The indexing functions have types that look like this:
indexZero :: ZeroF a -> Zero -> a
indexOne :: OneF a -> One -> a
indexTwo :: TwoF a -> Two -> a
indexThree :: ThreeF a -> Three -> a
I won't implement them all -- they're pretty straightforward -- but here's one to give you the idea in case it's not immediately obvious.
indexTwo (TwoF x0 x1) Two0 = x0
indexTwo (TwoF x0 x1) Two1 = x1
It turns out that the indexing functions have an inverse -- if you give me a function which, when given an index, produces a value, then I can give you a container with those values in it. The types look like this:
tabulateZero :: (Zero -> a) -> ZeroF a
tabulateOne :: (One -> a) -> OneF a
tabulateTwo :: (Two -> a) -> TwoF a
tabulateThree :: (Three -> a) -> ThreeF a
(Do you see why this is the right type for an inverse? Note that, say, TwoF a -> Two -> a
is the same type as TwoF a -> (Two -> a)
!) Just to give you an idea of how these are implemented, in case it's not immediately obvious, we simply apply the indexing function to each index:
tabulateZero ix = ZeroF
tabulateOne ix = OneF (ix One0 )
tabulateTwo ix = TwoF (ix Two0 ) (ix Two1 )
tabulateThree ix = ThreeF (ix Three0) (ix Three1) (ix Three2)
It's not too hard to prove that tabulateX . indexX = id
and indexX . tabulateX = id
for each X
, i.e. that tabulation really is the inverse of indexing.
Okay, but hold up now and take a look at what we've just done: we have turned a function (like Two -> a
) into a container (like TwoF a
), and vice versa. The types Two -> a
and TwoF a
are, morally speaking, exactly the same thing. So it seems reasonable to think we could implement fmap
for Two -> a
-- for example, just by converting to TwoF a
and back as appropriate!
twomap :: (a -> b) -> (Two -> a) -> (Two -> b)
twomap f = indexTwo . fmap f . tabulateTwo
Let's visualize what that's doing. We'll start with an arbitrary indexing function:
\case Two0 -> x0; Two1 -> x1
Now we go through the process:
\case Two0 -> x0; Two1 -> x1
tabulateTwo
TwoF x0 x1
fmap f
TwoF (f x0) (f x1)
indexTwo
\case Two0 -> f x0; Two1 -> f x1
Since f
gets applied in both branches, we could pull that out of the case
:
f . (\case Two0 -> x0; Two1 -> x1)
That second term is exactly the indexing function we started out with. In other words, we have just determined another, simpler implementation for twomap
:
twomap f ix = f . ix
If you work through similar reasoning for zeromap
, onemap
, and threemap
, you'll discover they actually all have that same implementation! We can do this uniformly for all the various sizes of container just by going polymorphic; instead of having onemap
for changing One -> a
's, etc., let's have an xmap
for changing x -> a
's:
xmap :: (a -> b) -> (x -> a) -> (x -> b)
xmap f ix = f . ix
Of course, we don't have to name f
and ix
:
xmap = (.)
...and this is the Functor
instance for (x -> _)
.
答案2
得分: 1
(->)
不仅仅是语法。它是一个操作符,与其他操作符一样,但是在类型级别而不是术语级别上运行。它具有类型 Type -> Type -> Type
,这意味着如果你将它应用于单一类型,你将得到的不是一个类型,而是另一个具有类型 Type -> Type
的 "函数"。
Type -> Type
是 所有 函子的类型,因此合部分应用的 (->)
操作符可能也是一个函子,这就是
instance Functor ((->) r) where
fmap = (.)
所定义的内容。也就是说,将一个函数映射到另一个函数意味着合成这两个函数。
将一个函数(类型为 r -> a
的东西)看作一个 "容器",其中包含了通过将函数应用于类型为 r
的参数而获得的所有可能的类型 a
的值。fmap
将应用一个函数到另一个函数返回的任何内容上。 (或者从理论上讲,将其应用于其他函数可能返回的 每个 值。)
英文:
(->)
isn't just syntax. It's an operator like any other, but at the type level instead of the term level. It has a kind Type -> Type -> Type
, which means if you apply it to a single type, you get back not a type, but another "function" of kind Type -> Type
.
Type -> Type
is the kind of all functors, so it's reasonable to think the partially applied (->)
operator might be a functor as well, which is what
instance Functor ((->) r) where
fmap = (.)
defines. That is, mapping a function over another function means to compose the two functions.
As a "container", think of a function (something of type r -> a
) as containing all possible values of type a
that you can get by applying the function to an argument of type r
. fmap
will apply a function to whatever the other function returns. (Or in theory, apply it to every value that the other could return.)
答案3
得分: 0
所以答案是:函数可以表示为(a -> b)
或者Map a b
- 对于具有有限可能参数的函数,这两种表示方式都是等效的。
因此,instance Functor (Map r)
是有意义的,它可以像已经实现的instance Functor ((->) r)
一样实现。
上面的答案也得到了instance Functor ((,) r)
的实现的确认。是的,这与Map r
有点不同,但尽可能接近。
附注:
@chepner:我无法将您的回答标记为“最佳答案”,因为我不理解(几乎不同意)一个句子中的一个词:
(->)
不仅仅是语法。它是像其他任何操作符一样的操作符。
函数不是“像任何其他”操作(我使用了“构建”概念)函数是神奇的或底层编译器构建,在所有其他函数都基于它的基础上。
英文:
So the answer is: functions can be represent either as (a -> b)
or as Map a b
- for function with finite count of possible arguments these are literally two equivalent representations.
So instance Functor (Map r)
is meaningful and it would be implemented just as instance Functor ((->) r)
implemented already.
And the answer above is confirmed by the implementation of instance Functor ((,) r)
. Yes this is a bit different than Map r
, but as close as possible.
P.S.
@chepner : I can't mark your answer as "best answer" because I don't understand (and almost don't agree) with one word in one sentense:
> (->) isn't just syntax. It's an operator like any other
Function is not "like any other" operation (I used notion "construction") function is magical- or under-hood-compiler- construction, on which all other fuctions are based.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论