Как сделать частичную функцию? - PullRequest
Новая
       35

Как сделать частичную функцию?

4 голосов
/ 12 октября 2019

Я думал о том, как я могу спасти себя от неопределенности, и у меня была одна идея - перечислить все возможные источники пристрастий. По крайней мере, я бы знал, что опасаться. Я нашел еще три:

  1. Неполные совпадения с паттернами или охранники.
  2. Рекурсия. (Необязательно исключая структурную рекурсию для алгебраических типов.)
  3. Если функция небезопасна, любое использование этой функции заражает код пользователя. (Должен ли я сказать «пристрастность транзитивна»?)

Я слышал о других способах получения логического противоречия, например, с помощью с использованием отрицательных типов , но я не уверен, относится ли что-либо подобное к Haskell. Существует много логических парадоксов, и некоторые из них могут быть закодированы в Haskell , но может ли быть так, что любой логический парадокс требует использования рекурсии и поэтому рассматривается в пункте 2 выше?

Например, если было доказано, что выражение Хаскелла, свободное от рекурсии, всегда может быть оценено как нормальная форма, то три пункта, которые я дам, будут полным списком. Я смутно помню, как видел нечто подобное в одной из книг Саймона Пейтона Джонса, но это было написано около 30 лет назад, так что даже если я правильно помню и раньше применялось к прототипу Haskell, это может быть сегодня ложнымВидя, сколько языков у нас есть. Возможно, некоторые из них предоставляют другие способы отмены определения программы?

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

1 Ответ

4 голосов
/ 12 октября 2019

Это частичный ответ (каламбур), где я перечислю лишь несколько, возможно, неочевидных способов достижения не прекращения.

Во-первых, я подтверждаю, что отрицательно-рекурсивные типы действительно могутпричина не прекращения. Действительно, известно, что разрешение рекурсивного типа, такого как 

data R a = R (R a -> a)

, позволяет определять fix и получать от него без завершения. 

{-# LANGUAGE ScopedTypeVariables  #-}
{-# OPTIONS -Wall #-}

data R a = R (R a -> a)

selfApply :: R a -> a
selfApply t@(R x) = x t

-- Church's fixed point combinator Y
-- fix f = (\x. f (x x))(\x. f (x x))
fix :: forall a. (a -> a) -> a
fix f = selfApply (R (\x -> f (selfApply x)))

Всего языков, таких как Coq илиAgda запрещает это, требуя, чтобы рекурсивные типы использовали только строго положительную рекурсию.

Еще один потенциальный источник не-завершения - то, что Haskell допускает Type :: Type. Насколько я могу видеть, это позволяет кодировать System U в Haskell, где парадокс Жирара может быть использован для создания логической несогласованности, создавая термин типа Void. Этот термин (насколько я понимаю) был бы не окончательным.

Парадокс Жирара, к сожалению, довольно сложен для полного описания, и я еще не полностью изучил его. Я только знаю, что это связано с так называемой гиперигрой, игрой, в которой первым ходом является выбор конечной игры для игры. Конечная игра - это игра, в которой каждый матч заканчивается после конечного числа ходов. Следующие ходы после этого будут соответствовать матчу в соответствии с выбранной конечной игрой на первом этапе. Вот парадокс: поскольку выбранная игра должна быть конечной, независимо от того, что это такое, весь гиперигровой матч всегда заканчивается после конечного количества ходов. Это делает гиперигру самой конечной игрой, делая бесконечную последовательность ходов «Я выбираю гиперигру, я выбираю гиперигру ...» действительной игрой, в свою очередь, доказывая, что гиперигра не конечна.

По-видимому, этот аргумент может быть закодирован в достаточно богатой системе чистых типов, такой как System U, а Type :: Type позволяет встраивать тот же аргумент.

...