Haskell：a类型函数的例子 - > a，除了身份 [英] Haskell: example of function of type a -> a, besides the identity

问题描述

我刚刚开始和Haskell一起玩...我想写一个同一类型身份的函数。显然，不等于它。这就像是，

myfunction :: a - >一个

我不能想出一个例子，其中参数和返回类型是相同的，几乎可以是任何东西（这不包括使用Haskell的Typeclasses的可能性）。

解决方案

如果不使用 undefined 作为另一位评论者提到。让我们通过反例来证明这一点。假设有这样一个函数：

  f :: a  - > a 
  

当你说这与 id ，这意味着你不能定义：



  fx = x 
  

但是，请考虑 a 是类型（）

$ p $ f（）= ...
pre>



唯一可能的结果 f 可能会返回为（），但这与 id 的实现是一样的，因此是矛盾的。

严谨的答案是证明 a - >一个必须与（）同构。当我们说两个类型 a 和 b 是同构的，这意味着我们可以定义两个函数：

  fw :: a  - > b 
 bw :: b  - > a 
  

...例如：

  fw。 bw = id 
 bw。 fw = id 
  

当第一个类型是 a时， >一个，第二个类型是（）：

  fw ::（forall a。a  - > a） - > （）
 fw f = f（）
 
 bw ::（） - > （a a a a a）
 bw（）x = x 
  

我们然后可以证明：

  fw。 bw 
 = \（） - > fw（bw（））
 = \（） - > fw（\ x  - > x）
 = \（） - > （\ x  - > x）（）
 = \（） - > （）
 = id 
 
 bw。 fw 
 = \f  - > bw（fw f）
  - 对于这种类型检查，（fw f）的类型必须是（）
  - 因此，f必须是`id` 
 = \ f  - > id 
 = \f  - > f 
 = id 
  

当你证明两种类型是同构的时，你知道的一件事是如果一种类型有限数量的元素居住，另一种类型必须如此。由于类型（）恰好有一个值：

  data （）=（）
  

这意味着类型（forall a。a - > a）也必须由一个值居住，这恰好是 id 的实现。

编辑：有些人评论说同构的证明不够严格，所以我会调用Yoneda引理，当它翻译成Haskell时，它说任何函数<$ c

$ p $ （b。（a - > b） - > $ c> f ： fb）〜fa


其中〜表示（所有b。（a - > b） - > fb）同构于 fa 。如果您选择 Identity 函子，这简化为：

 （forall b。（a  - > b） - > b）〜a 
  

... if你选择 a =（），这可以进一步简化为：

 （ （） - > b） - > b）〜（）
  

您可以很容易证明（） - > b 同构于 b ：

  fw ::（（） - > b） - > b 
 fw f = f（）
 
 bw :: b  - > （（） - > b）
 bw b = \（） - > b 
 
 fw。 bw 
 = \b  - > fw（bw b）
 = \b  - > fw（\（） - > b）
 = \ b  - > （\（） - > b）（）
 = \ b  - > b 
 = id 
 
 bw。 fw 
 = \f  - > bw（fw f）
 = \f  - > bw（f（））
 = \f  - > \（） - > f（）
 = \f  - > f 
 = id 
  

然后我们可以使用它来最终专门化Yoneda同构：



 （全部b。b  - > b）〜（）
  pre> 
 
 
其中的任何函数都是 forall b。 b  - > b 同构于（）。 Yoneda引理提供了我的证据遗漏的严格性。 
I've just started playing a little with Haskell... I want to write a function of the same type of the identity. Obviously, not equivalent to it. That would be something like,

myfunction :: a -> a

I cannot come up with an example in which the parameter and the return type are the same and can be virtually anything (this excludes the possibility of using Haskell's Typeclasses).
解决方案
This is impossible without using undefined as another commenter mentioned.  Let's prove it by counter-example.  Assume there were such a function:
f :: a -> a
When you say that's it not the same as id, that implies that you cannot define:
f x = x
However, consider the case where a is the type ():
f () = ...
The only possible result f could return would be (), but that would be the same implementation as id, therefore a contradiction.

The more sophisticated and rigorous answer is to show that the type a -> a must be isomorphic to ().  When we say two types a and b are isomorphic, that means that we can define two functions:
fw :: a -> b
bw :: b -> a
... such that:
fw . bw = id
bw . fw = id
We can easily do this when the first type is a -> a and the second type is ():
fw :: (forall a . a -> a) -> ()
fw f = f ()

bw :: () -> (forall a . a -> a)
bw () x = x
We can then prove that:
fw . bw
= \() -> fw (bw ())
= \() -> fw (\x -> x)
= \() -> (\x -> x) ()
= \() -> ()
= id

bw . fw
= \f -> bw (fw f)
-- For this to type-check, the type of (fw f) must be ()
-- Therefore, f must be `id`
= \f -> id
= \f -> f
= id
When you prove two types are isomorphic, one thing you know is that if one type is inhabited by a finite number of elements, so must the other one.  Since the type () is inhabited by exactly one value:
data () = ()
That means that the type (forall a . a -> a) must also be inhabited by exactly one value, which just so happens to be the implementation for id.

Edit: Some people have commented that the proof of the isomorphism is not sufficiently rigorous, so I'll invoke the Yoneda lemma, which when translated into Haskell, says that for any functor f:
(forall b . (a -> b) -> f b) ~ f a
Where ~ means that (forall b . (a -> b) -> f b) is isomorphic to f a.  If you choose the Identity functor, this simplifies to:
(forall b . (a -> b) -> b) ~ a
... and if you choose a = (), this further simplifies to:
(forall b . (() -> b) -> b) ~ ()
You can easily prove that () -> b is isomorphic to b:
fw :: (() -> b) -> b
fw f = f ()

bw :: b -> (() -> b)
bw b = \() -> b

fw . bw
= \b -> fw (bw b)
= \b -> fw (\() -> b)
= \b -> (\() -> b) ()
= \b -> b
= id

bw . fw
= \f -> bw (fw f)
= \f -> bw (f ())
= \f -> \() -> f ()
= \f -> f
= id
So we can then use that to finally specialize the Yoneda isomorphism to:
(forall b . b -> b) ~ ()
Which says that any function of type forall b . b -> b is isomorphic to ().  The Yoneda lemma provides the rigor that my proof was missing.

                        
这篇关于Haskell：a类型函数的例子 - > a，除了身份的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！