关键词：
【中文标题】如何编码 Haskell/函数式编程中的选择公理？【英文标题】：How to encode the axiom of choice in Haskell/Functional programming? 【发布时间】：2016-03-10 20:39:56 【问题描述】：> -# LANGUAGE RankNTypes #-
我想知道是否有一种方法可以在 haskell 和/或其他一些函数式编程语言中表示选择公理。
我们知道，false 由没有值的类型表示（Void in haskell）。
> import Data.Void
我们可以这样表示否定
> type Not a = a -> Void
我们可以像这样表达类型a的排中律
> type LEM a = Either a (a -> Void)
这意味着我们可以将建设性逻辑变成Reader monad
> type Constructive a = (forall r. LEM r) -> a
例如，我们可以在其中进行双重否定消除
> doubleneg :: Constructive (((a -> Void) -> Void) -> a)
> doubleneg = \lem nna -> either id (absurd . nna) lem
我们也可以有一个排中律失效的单子
> type AntiConstructive a = ((forall r. LEM r) -> Void) -> a
现在的问题是，我们如何创建一个表示选择公理的类型？选择公理是关于集合的集合。这意味着我们需要类型的类型或其他东西。是否有可以编码的选择公理等价？ （如果您可以对否定进行编码，只需将其与排中律结合即可）。也许诡计可以让我们拥有类型的类型。
注意：理想情况下，它应该是与Diaconescu's theorem 一起使用的选择公理的一个版本。
【问题讨论】：
投了反对票，理由是这个问题没有显示任何研究工作：谷歌搜索“选择公理 agda”对如何做到这一点进行了很多讨论。 @DanielWagner 如果之前在 stackexchange 上没有关于这个话题的讨论，那么不管你在谷歌上还能找到什么，它都是主题。 stackexchange 的创始人已经写过很多次了。整个理念是成为未来人们在搜索谷歌时发现的资源。 @NickAlger 是的；出于这个原因，我没有（也不会）投票结束这个问题，这是对离题的事情采取的行动。 （我认为问题的好投票数和接近投票数的含义不同是完全合理的。） 适用于索引集的公理版本，还是我们试图推理甚至不可数集？ 【参考方案1】：这只是一个提示。
选择公理可以表示为：
如果对于每个
x : A都有一个y : B使得属性P x y成立，那么就有一个选择函数f : A -> B这样对于所有x : A我们都有P x (f x)。
更准确
choice : A B : Set (P : A -> B -> Set) ->
((x : A) -> Σ B (λ y -> P x y)) ->
Σ (A -> B) (λ f -> (x : A) -> P x (f x))
choice P h = ?
给定
data Σ (A : Set) (P : A -> Set) : Set where
_,_ : (x : A) -> P x -> Σ A P
以上，choice 确实是可证明的。实际上，h 为每个x 分配了一个（依赖）对，其第一个组件y 是A 的一个元素，第二个组件是第一个确实满足P x y 的证明。相反，论文中的f必须只分配给xy，无需任何证明。
如您所见，从h 获得选择函数f 只是丢弃该对中的证明组件。
没有必要用 LEM 或任何其他公理扩展 Agda 来证明这一点。上述证明完全是建设性的。
如果我们使用 Coq，请注意 Coq 禁止消除证明（例如 h : ... -> Prop）来构造非证明（f），因此直接将其转换为 Coq 会失败。 （这是为了允许程序提取。）但是，如果我们避免使用Prop这种Coq，直接使用Type，则可以翻译上述内容。
您可能希望在此练习中使用以下预测：
pr1 : ∀ A : Set P -> Σ A P -> A
pr1 (x , _) = x
pr2 : ∀ A : Set P -> (p : Σ A P) -> P (pr1 p)
pr2 (_ , y) = y
【讨论】：
将“为啥函数式编程很重要”翻译成 Haskell
】将“为啥函数式编程很重要”翻译成Haskell【英文标题】：Translating"WhyFunctionalProgrammingMatters"intoHaskell将“为什么函数式编程很重要”翻译成Haskell【发布时间】：2009-06-1608:15:45【问题描述】：为了丰富文化和知识，我决... 查看详情
frege-基于jvm的类haskell纯函数式编程语言
Frege是一门受Haskell语言启示而设计的纯函数式编程语言。Frege程序会被编译为Java，并执行于JVM上。它与Haskell是如此的类似。以至于有人称它为JVM上的Haskell。取Frege这个名字是为了纪念德国数学家、逻辑学家、哲学家GottlobFrege。... 查看详情
函数式编程语言中的自动记忆
...【发布时间】：2011-08-1013:55:07【问题描述】：我一直认为Haskell会进行某种自动智能记忆。例如，朴素的斐波那契实现fib0=0fib1=1fibn=fib(n-2)+fib(n-1)因此会很快。现在我读了this，看来我错了——Haskell似乎没有自动记忆。还是我理解... 查看详情
函数式编程语言
...向对象的Java、C#等结构化程序设计语言。 2. Haskell Haskell是一种标准化的、通用纯函数式编程语言，有非限定性语义和强静态类型。它的命名源自美国逻辑学家HaskellBrooksCurry，他在数学逻辑方面的工作使得函数式... 查看详情
初识haskell
在COMP30026ModelsofComputation中接触了新的编程语言Haskell，一个之前听都没有听过的语言，在此记录关于Haskell的一些最基本概念。1.Haskell是一个函数式编程语言(functionalprogramminglanguage)，函数式编程语言最基本的操作是functionapplication... 查看详情
函数式编程
和Lisp、Haskell不同，javascript并非函数式编程语言，但在javascript中可以操控对象一样操控函数，也就是说可以在javascript中应用函数式编程技术。ES5中的数组方法(如map()和reduce())就可以非常适合用于函数式编程风格。本文将详细介... 查看详情
函数式编程语言中的 CMS [关闭]
...描述】：是否已经有任何CMS，用函数式编程语言（lisp、haskell、f#/nemerle、scala、erlang、clojure、smalltalk）编写？【问题讨论】：我知道，twitter是在Scala上运行的。@fortran很好，它有一 查看详情
与函数式编程中的“折叠”函数等效的“pythonic”是啥？
...是什么？【发布时间】：2012-05-0903:08:35【问题描述】：在Haskell中实现以下目标的最惯用方法是什么：foldl(+)0[1,2,3, 查看详情
一天一门编程语言haskell语言程序设计极简教程(代码片段)
Haskell语言程序设计极简教程一、什么是HaskellHaskell是一种纯函数式编程语言，它把程序设计抽象化到一个更高的层次，简化程序开发工作量，能够更快更容易地完成任务。它是一种函数式编程语言，它采用函数式... 查看详情
这些电子书新上架
关注微信公众号【异步图书】每周送书本周上新Haskell函数式编程入门（第2版）第1卷作者：张淞,刘长生分类：软件开发>编程语言>函数式语言这是一本讲解纯函数式编程语言Haskell的书，同时也是一本通过Haskell来讲解函数式... 查看详情
函数式编程(代码片段)
...com/files/bajdcc/jMiniLang-manual.pdf================================看了Haskell这段代码该如何理解？今天突发奇想，尝试一把函数式编程的感觉~最近把bajdcc/jMiniLang继续修整了一下，修了点bug，界面开了抗锯齿，顿时美观度大增哈哈。依照【游 查看详情
如何在现实世界中使用函数式编程？ [关闭]
...，而不必担心线程数。作为一名Win32开发人员，我可以将Haskell用于我的应用程序的某些dll吗？如果我这样做了，是否会自动为 查看详情
函数式编程
...杂的执行过程。纯函数式编程语言强静态类型ConcurrentCleanHaskellMiranda弱类型LazyK非纯函数式编程语言强静态类型F#MLOCamlScala强动态类型ClojureErlangLispLOGOMathematicaRScheme弱类型Unlambda其他函数式编程语言APL语言XSLT历史函数式编程中最古... 查看详情
Haskell 中的参数化类型
】Haskell中的参数化类型【英文标题】：ParameterizedTypesinHaskell【发布时间】：2021-12-1723:11:34【问题描述】：为什么Haskell中的类型必须在类型构造函数参数中显式参数化？例如：dataMaybea=Nothing|Justa这里a必须指定类型。为什么不能只... 查看详情
#对haskell这门语言的基本认识(代码片段)
Haskell语言的核心特征：1.函数式，而且是纯函数式(purelyfunctional)首先，引用一下维基百科上对“典型的函数式编程语言”的划分： 一：纯函数式 1.强静态类型：Miranda,Haskell 2.弱类型：LazyK ... 查看详情
algebraicdatatype及其在haskell和scala中的表现(代码片段)
http://songkun.me/2018/07/12/2018-07-12-adt-in-haskell-and-scala/函数式编程接触久了以后，我们会发现很多FP语言（这里指静态FP语言）具有不少类似的语言特性，这非常自然，因为语言特性就那么多，好用、实用的特性更少，这一方面造成了... 查看详情
函数式语言（functionlanguage）
... ①强静态类型 ConcurrentClean 简称Clean，它与Haskell有很多相似之处，是由c编写的。Clean程式很容易跨平台，在大部分情况下，要转移到另一个平台只需在那里重新编译一次即可，不用改动源代码。 Haskell 是一... 查看详情
函数式编程和非函数式编程
...615:50:31【问题描述】：在我大学的第二年，我们“教”了Haskell，我对此几乎一无所知，对函数式编程更是一无所知。什么是函数式编程，为什么和/或我想在哪里使用它而不是非函数式编程，我认为C是一种非函数式编程语言是否... 查看详情