Haskell 中的德摩根定律,来自 Curry-Howard 通信
De Morgan's Laws in Haskell via the Curry-Howard Correspondence
我在 Haskell 中实施了四个德摩根定律中的三个:
notAandNotB :: (a -> c, b -> c) -> Either a b -> c
notAandNotB (f, g) (Left x) = f x
notAandNotB (f, g) (Right y) = g y
notAorB :: (Either a b -> c) -> (a -> c, b -> c)
notAorB f = (f . Left, f . Right)
notAorNotB :: Either (a -> c) (b -> c) -> (a, b) -> c
notAorNotB (Left f) (x, y) = f x
notAorNotB (Right g) (x, y) = g y
但是,我不认为有可能实施最后的法律(有两个居民):
notAandBLeft :: ((a, b) -> c) -> Either (a -> c) (b -> c)
notAandBLeft f = Left (\a -> f (a, ?))
notAandBRight :: ((a, b) -> c) -> Either (a -> c) (b -> c)
notAandBRight f = Right (\b -> f (?, b))
在我看来,有两种可能的解决方案:
- 使用
undefined
代替 ?
。这不是一个好的解决方案,因为它在作弊。
使用单态类型或有界多态类型来编码默认值。
notAandBLeft :: Monoid b => ((a, b) -> c) -> Either (a -> c) (b -> c)
notAandBLeft f = Left (\a -> f (a, mempty))
notAandBRight :: Monoid a => ((a, b) -> c) -> Either (a -> c) (b -> c)
notAandBRight f = Right (\b -> f (mempty, b))
这不是一个好的解决方案,因为它是比德摩根定律更弱的定律。
我们知道德摩根定律是正确的,但我假设最后一条定律不能用 Haskell 编码是否正确?这说明了 Curry-Howard 同构是什么?如果每个证明都不能转换成等价的计算机程序,那不是真正的同构,对吗?
对我来说突出的一件事是你似乎没有在任何地方使用定义或任何 属性 否定。
读完 Haskell Wikibooks article on the CHI 这里有一个证明,假设你有一个定理的排中律:
exc_middle :: Either a (a -> Void)
notAandB
德摩根定律的证明如下:
notAandB' :: Either a (a -> Void) -> ((a,b) -> Void) -> Either (a -> Void) (b -> Void)
notAandB' (Right notA) _ = Left notA
notAandB' (Left a) f = Right (\b -> f (a,b))
notAandB = notAandB' exc_middle
第四定律是not intuitionistic。您将需要排中公理:
lem :: Either a (a -> c)
或皮尔斯定律:
pierce :: ((a -> c) -> c) -> a
证明一下。
我在 Haskell 中实施了四个德摩根定律中的三个:
notAandNotB :: (a -> c, b -> c) -> Either a b -> c
notAandNotB (f, g) (Left x) = f x
notAandNotB (f, g) (Right y) = g y
notAorB :: (Either a b -> c) -> (a -> c, b -> c)
notAorB f = (f . Left, f . Right)
notAorNotB :: Either (a -> c) (b -> c) -> (a, b) -> c
notAorNotB (Left f) (x, y) = f x
notAorNotB (Right g) (x, y) = g y
但是,我不认为有可能实施最后的法律(有两个居民):
notAandBLeft :: ((a, b) -> c) -> Either (a -> c) (b -> c)
notAandBLeft f = Left (\a -> f (a, ?))
notAandBRight :: ((a, b) -> c) -> Either (a -> c) (b -> c)
notAandBRight f = Right (\b -> f (?, b))
在我看来,有两种可能的解决方案:
- 使用
undefined
代替?
。这不是一个好的解决方案,因为它在作弊。 使用单态类型或有界多态类型来编码默认值。
notAandBLeft :: Monoid b => ((a, b) -> c) -> Either (a -> c) (b -> c) notAandBLeft f = Left (\a -> f (a, mempty)) notAandBRight :: Monoid a => ((a, b) -> c) -> Either (a -> c) (b -> c) notAandBRight f = Right (\b -> f (mempty, b))
这不是一个好的解决方案,因为它是比德摩根定律更弱的定律。
我们知道德摩根定律是正确的,但我假设最后一条定律不能用 Haskell 编码是否正确?这说明了 Curry-Howard 同构是什么?如果每个证明都不能转换成等价的计算机程序,那不是真正的同构,对吗?
对我来说突出的一件事是你似乎没有在任何地方使用定义或任何 属性 否定。
读完 Haskell Wikibooks article on the CHI 这里有一个证明,假设你有一个定理的排中律:
exc_middle :: Either a (a -> Void)
notAandB
德摩根定律的证明如下:
notAandB' :: Either a (a -> Void) -> ((a,b) -> Void) -> Either (a -> Void) (b -> Void)
notAandB' (Right notA) _ = Left notA
notAandB' (Left a) f = Right (\b -> f (a,b))
notAandB = notAandB' exc_middle
第四定律是not intuitionistic。您将需要排中公理:
lem :: Either a (a -> c)
或皮尔斯定律:
pierce :: ((a -> c) -> c) -> a
证明一下。