Общая функция типа (для n. Maybe (f n)) -> Maybe (для n (f n))

Question

Можно ли написать инъективную функцию типа

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

в виде общей функциональной программы - то есть без использования error, undefined, unsafeXXX, bottom, неисчерпаемые шаблоны или какие-либо функции, которые не завершаются?

По параметричность , для любого фиксированного f :: *->* единственного всего населения

(forall n . Maybe (f n))

примет одну из двух форм:

Nothing

Just z
  where
    z :: forall n . f n

К сожалению, любая попытка case на Maybe потребует выбора n first , поэтому типыпеременные шаблона внутри ветвей case больше не будут полиморфными в n.Кажется, что в языке отсутствует какая-то конструкция для выполнения case -дискриминации для полиморфного типа без создания экземпляра типа .

Кстати, написание функции в противоположном направленииэто просто:

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

Answer 1

По совпадению я получил его, просто пытаясь создать значение, которое я мог бы передать вашей функции 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

вывоз мусора сверху

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

Answer 2

Я доказал, что это невозможно [нет, нет;см. ниже] в Агде:

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 | ()

Конечно, это не идеальное опровержение, так как оно написано на другом языке, но я думаю, что оно вполне соответствует.

Я началопределяя Type как тип желаемой функции, вместе с доказательством того, что функция инъективна (Σ x P можно рассматривать как экзистенциальное высказывание «существует такой x, что P (x)»).Поскольку мы говорим об инъективной функции, которая принимает функцию (формула haskell можно рассматривать как функцию уровня типа, и именно так она кодируется в Agda), я использую точечное равенство (∀ i → x i ≡ y i), потому что логика Agdaне позволит мне доказать, что x ≡ y напрямую.

Кроме этого, я просто опроверг тип, предоставив контрпример к логическим значениям.

Редактировать: мне просто пришло в голову, чтоtype включает в себя функцию F из некоторого типа A в тип, поэтому мое доказательство не совсем соответствует тому, что вы могли бы написать в Haskell.Сейчас я занят, но могу попытаться исправить это позже.

Редактировать 2: мои доказательства недействительны, потому что я не принимаю во внимание параметричность.Я могу сопоставлять паттерны с логическими значениями, но не с сетами, и я не могу доказать это в Agda.Я подумаю над проблемой еще немного:)

Answer 3

Это легко понять, если вы посмотрите на все возможные вычислительные зависимости каждое вычисленное значение может иметь во время выполнения:

Выражение типа (forall n . Maybe (f n)) может иметь значение Nothing для одного типа и Just для другого типа. Поэтому это функция, которая принимает тип в качестве параметра.

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)

Полученное значение этого типа Maybe (N -> fN) (будь то Nothing или Just) зависит от значения N (тип n).

Итак, ответ нет .

Answer 4

Вопрос может быть сведен к следующему: можем ли мы написать функцию, которая перемещает поля следующим образом?

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

В конце концов, если мы сможем это сделать, то все остальное легко снесколько непредсказуемых типов:

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!

(Если вы хотите попробовать это в GHC, обязательно определите новый тип, например

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

, поскольку в противном случае GHC любит плавать forall sвпереди стрелок и переверните.)

Но ответ на вопрос, можем ли мы написать suicidal, ясен: нет, мы не можем!По крайней мере, не в параметрическом смысле над f.Решение должно выглядеть примерно так:

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

... и тогда нам придется пройтись по «структуре» f, найдя «места», где есть функции типа,и применить их к n, который у нас теперь есть в наличии.Ответ на оригинальный вопрос о hard оказывается таким же: мы можем написать hard для любого конкретного f, но не параметрически для всех f.

Кстати, яЯ не уверен, что то, что вы сказали о параметричности, совершенно верно:

По параметризации для любого фиксированного f :: *->* единственное общее число жителей (forall n . Maybe (f n)) примет одну из двух форм: Nothingили Just z, где z :: forall n . f n.

На самом деле, я думаю, что вы получаете то, что жители (обсервационно эквивалентны) одной из двух форм:

/\ n. Nothing
/\ n. Just z

... где z выше не полиморфный: он имеет особый тип f n.(Примечание: нет скрытых forall s.) То есть возможные условия последней формы зависят от f!Вот почему мы не можем написать функцию параметрически в отношении f.

edit: Кстати, если мы позволим себе экземпляр Functor для 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

... но это обман, не в последнюю очередь потому, что я понятия не имею, как перевести это на Хаскелл.; -)