类型的总函数(forall n)可能是(f n) ->可能(forall n)。(f(n))

Is it possible to write an injective function of type

可以写出类型的单射函数吗?

hard :: (forall n . Maybe (f n)) -> Maybe (forall n . (f n))

as a total functional program -- that is, without using error, undefined, unsafeXXX, bottom, inexhaustive patterns, or any functions which don't terminate?

作为一个总的功能程序——也就是说，不使用错误、未定义的、不安全的、底部的、不完整的模式，或者任何不终止的函数?

By parametricity, for any fixed f :: *->* the only total inhabitants of

通过参数城市，对于任何固定的f:: *->*唯一的总居民。

(forall n . Maybe (f n))

will take one of two forms:

将采取以下两种形式之一:

Nothing

Just z
  where
    z :: forall n . f n

Unfortunately any attempt to case on the Maybe will require choosing n first, so the types of the pattern variables inside the case branches will no longer be polymorphic in n. It seems like the language is missing some sort of construct for performing case-discrimination on a polymorphic type without instantiating the type.

不幸的是任何试图案件也许需要先选择n,所以内部的类型模式的变量情况下分支将不再是多态的n。似乎缺少某种语言构建执行case-discrimination多态类型没有实例化类型。

By the way, writing a function in the opposite direction is easy:

顺便说一下，在反方向写函数很简单:

easy :: Maybe (forall n . (f n)) -> (forall n . Maybe (f n))
easy Nothing  = Nothing
easy (Just x) = Just x

4 个解决方案

#1

I coincidentally got it, just by playing trying to create a value that I could pass into your easyf function. I'm in trouble if you need an explanation though!! see comments below.

我碰巧得到了它，只是通过尝试创建一个我可以传入您的easyf函数的值。如果你需要解释，我就麻烦了!!请参见下面的评论。

data A α = A Int
data B f = B (forall α . f α)

a :: forall α . A α
a = A 3

b = B a
f (B (Just -> x)) = x -- f :: B t -> Maybe (forall α. t α)
f' (B x) = Just x -- f' :: B t -> Maybe (t α)

easy :: forall f . Maybe (forall n . (f n)) -> (forall n . Maybe (f n))
easy Nothing = Nothing
easy (Just x) = Just x

easyf :: Maybe (forall n . (A n)) -> (forall n . Maybe (A n))
easyf = easy

-- just a test
g = easyf (f b)



h :: (forall α. t α) -> Maybe (forall α. t α)
h = f . B

unjust :: (forall n . (Maybe (f n))) -> (forall n . f n)
unjust (Just x) = x

hard :: forall f. (forall n . (Maybe (f n))) -> Maybe (forall n . (f n))
hard xj@(Just _) = g (unjust xj) where
    g :: (forall n . f n) -> Maybe (forall n . (f n))
    g = h
hard Nothing = Nothing

edit 1

taking out the junk from above,

从上面取出垃圾，

mkJust :: (forall α. t α) -> Maybe (forall α. t α)
mkJust = Just

unjust :: (forall n . (Maybe (f n))) -> (forall n . f n)
unjust (Just x) = x

hard :: forall f. (forall n . (Maybe (f n))) -> Maybe (forall n . (f n))
hard xj@(Just _) = mkJust (unjust xj)
hard Nothing = Nothing

#2

I proved it impossible [err, no I didn't; see below] in Agda:

我证明了这是不可能的[呃，不，我没有;在Agda见下文):

module Proof where

open import Data.Empty
open import Data.Maybe
open import Data.Bool
open import Data.Product

open import Relation.Nullary
open import Relation.Binary.PropositionalEquality

Type : Set₁
Type = Σ ({A : Set} {F : A → Set} → (∀ n → Maybe (F n)) → Maybe (∀ n → F n)) (λ f → ∀ {A} {F : A → Set} x y → f {F = F} x ≡ f y → (∀ i → x i ≡ y i))

helper : (b : Bool) → Maybe (T b)
helper true = just _
helper false = nothing

proof : ¬ Type
proof (f , pf) with inspect (f helper)
proof (f , pf) | just x with-≡ eq = x false
proof (f , pf) | nothing with-≡ eq with f {F = T} (λ _ → nothing) | pf helper (λ _ → nothing)
proof (f , pf) | nothing with-≡ eq | just x | q = x false
proof (f , pf) | nothing with-≡ eq | nothing | q with q eq true
proof (f , pf) | nothing with-≡ eq | nothing | q | ()

Of course, this isn't a perfect disproof, as it's in a different language, but I think it matches up fairly well.

当然，这并不是一个完美的反驳，因为它是一种不同的语言，但我认为它相当不错。

I started by defining Type as your desired function's type, along with a proof that the function is injective (Σ x P can be seen as an existential saying "there exists an x such that P(x)"). Because we're talking about an injective function that takes a function (haskell's forall can be seen as a type-level function, and that's how it's encoded in Agda), I use point-wise equality (the ∀ i → x i ≡ y i) because Agda's logic won't let me prove that x ≡ y directly.

我开始通过定义类型所需的函数的类型,以及证明函数是单射(Σx P可以被看作是一个存在主义说”存在一个x P(x)”)。因为我们讨论的是一个单射函数接受一个函数(haskell的原则,可以被视为一种类型层次功能,这是它是如何编码在Agda),我使用逐点地平等(∀我→x≡y)因为Agda逻辑不让我直接证明x≡y。

Other than that, I just disproved the type by providing a counterexample on the booleans.

除此之外，我只是通过在布尔值上提供一个反例来证明这一类型。

Edit: it just occurred to me that the type involves a function F from some type A to a type, so my proof doesn't correspond exactly to what you could write in Haskell. I'm busy now but might try to fix that later.

编辑:我刚刚意识到，类型涉及到从某种类型a到类型的函数F，所以我的证明与你在Haskell中所写的不完全一致。我现在很忙，但以后可能要解决这个问题。

Edit 2: my proof is invalid because I'm not taking parametricity into account. I can pattern match on booleans but not on sets, and I can't prove that in Agda. I'll think about the problem some more :)

编辑2:我的证明无效，因为我没有考虑到参数化。我可以在布尔值上进行匹配，但不能在集合上进行匹配，我不能在Agda中证明这一点。我会再考虑这个问题:)

#3

That is easy to understand, if you look at all possible computational dependencies each computed value might have at runtime:

这很容易理解，如果您查看所有可能的计算依赖项，每个计算值可能在运行时都有:

An expression of the type (forall n . Maybe (f n)) could evaluate to a Nothing for one type and a Just for another type. It is therefore a function that takes a type as parameter.

类型的表达式(forall n)。也许(f n)可以对一种类型和另一种类型的任何东西进行评估。因此，它是一个以类型为参数的函数。

hard :: (forall n . Maybe (f n)) -> Maybe (forall n . f n)
-- problem statement rewritten with computational dependencies in mind:
hard' :: (N -> Maybe (fN)) -> Maybe (N -> fN)

The resulting value of that Maybe (N -> fN) type (whether it is Nothing or Just) depends on the value of N (the type of n).

结果的值可能(N -> fN)类型(不管它是零还是仅仅)取决于N的值(N的类型)。

So, the answer is no.

所以答案是否定的。

#4

The question can be reduced to the following one: can we write a function that moves foralls in the following way?

这个问题可以归结为以下一个问题:我们可以用下面的方法来编写一个移动foralls的函数吗?

suicidal :: f (forall n. n) -> forall n. f n

After all, if we can do that, then the rest is easy with a few impredicative types:

毕竟，如果我们能做到这一点，那么剩下的就很容易了，有一些无法预测的类型:

hard' :: Maybe (f (forall n. n)) -> Maybe (forall n. f n)
hard' Nothing = Nothing
hard' (Just x) = Just (suicidal x)

hard :: (forall n. Maybe (f n)) -> Maybe (forall n. f n)
hard x = hard' x -- instantiate 'n' at type 'forall n. n', thank goodness for impredicativity!

(If you want to try this in GHC, be sure to define a newtype like

如果您想在GHC中尝试这个，请确定定义一个新的类型。

newtype Forall f = Forall { unForall :: forall n. f n }

since otherwise GHC likes to float foralls to the front of arrows and screw you over.)

因为不然的话，GHC喜欢在箭头前面浮动，并把你弄得很乱。

But the answer to whether we can write suicidal is clear: No, we can't! At least, not in a way that's parametric over f. The solution would have to look something like this:

但是，我们是否可以写自杀的答案是明确的:不，我们不能!至少，不是在f的参数下，解应该是这样的

suicidal x = /\ n. {- ... -}

...and then we'd have to walk over the "structure" of f, finding "places" where there were type functions, and applying them to the n we now have available. The answer for the original question about hard turns out to be the same: we can write hard for any particular f, but not parametrically over all f.

…然后我们要走f的“结构”，找到有类型函数的“位置”，然后把它们应用到我们现在可用的n中。最初的问题的答案是一样的:我们可以为任何一个特定的f而写，但不能对所有f进行参数化。

By the way, I'm not convinced that what you said about parametricity is quite right:

顺便说一下，我不相信你说的关于参数城市的说法是正确的:

By parametricity, for any fixed f :: *->* the only total inhabitants of (forall n . Maybe (f n)) will take one of two forms: Nothing or Just z where z :: forall n . f n.

对任何固定的f:: *->*唯一的全体居民(forall n)。也许(f n)将采取两种形式中的一种:什么都不做，或者只有z:: forall n。f(n。

Actually, I think what you get is that the inhabitants are (observationally equivalent to) one of two forms:

实际上，我认为你所得到的是，居民是(观察上相当于)两种形式中的一种:

/\ n. Nothing
/\ n. Just z

...where the z above is not polymorphic: it has the particular type f n. (Note: no hidden foralls there.) That is, the possible terms of the latter form depend on f! This is why we can't write the function parametrically with respect to f.

…上面的z不是多态的:它有特定类型的fn(注意:没有隐藏的foralls)。也就是说，后一种形式的可能条件取决于f!这就是为什么我们不能用f来表示函数。

edit: By the way, if we allow ourselves a Functor instance for f, then things are of course easier.

顺便说一下，如果我们给自己一个函数f的例子，那么事情当然就简单多了。

notSuicidal :: (forall a b. (a -> b) -> (f a -> f b)) -> f (forall n. n) -> forall n. f n
notSuicidal fmap structure = /\ n. fmap (\v -> v [n]) structure

...but that's cheating, not least because I have no idea how to translate that to Haskell. ;-)

…但那是作弊，不仅仅是因为我不知道如何把它翻译成Haskell。:-)