如何用任意算术的函数组合'not'?

实际上,对类型类执行任意算术非常简单:

module Pred where

class Predicate a where
  complement :: a -> a

instance Predicate Bool where
  complement = not

instance (Predicate b) => Predicate (a -> b) where
  complement f = \a -> complement (f a)  
  -- if you want to be mysterious, then
  -- complement = (complement .)
  -- also works

ge :: Ord a => a -> a -> Bool
ge = complement (<)

至于你的主要问题,这是用科纳尔·艾略特的最优雅的方式解决的 语义编辑器组合器 . 语义编辑器组合器是一个类型如下的函数:

(a -> b) -> F(a) -> F(b)

哪里 F(x) 有些表达涉及到 x . 还有一些“逆变”编辑器组合器,它们采用 (b -> a) result

result = (.)

查看您试图操作的表达式的类型:

a -> a -> Bool

这种类型的结果(编码域)是 a -> Bool ,以及 那个 Bool ,这就是你想要申请的 not 到所以要申请 不 f ,你写道:

(result.result) not f

argument = flip (.)     -- contravariant

first f (a,b) = (f a, b)
second f (a,b) = (a, f b)

left f (Left x) = Left (f x)
left f (Right x) = Right x
...

x 类型:

Int -> Either (String -> (Int, Bool)) [Int]

你想申请吗 不 对于布尔人,你只需说出到达那里的路径:

(result.left.result.second) not x

fmap 是一个编辑组合器。事实上,上述内容可以拼写为:

(fmap.left.fmap.fmap) not x

但我认为使用扩展名称更为清晰。

您的n组合符可以写为:

n = ((not .) .)

lift2 = (.).(.)
lift3 = (.).(.).(.)
lift4 = (.).(.).(.).(.)
lift5 = (.).(.).(.).(.).(.)

关于 我做错了什么?

我认为您的combinator很好,但当您让它在顶层绑定时,Haskell的一个恼人的“默认规则”开始发挥作用,绑定并不是通用的:

Prelude> :ty (n f)
(n f) :: (Ord t) => t -> t -> Bool
Prelude> let g = n f
Prelude> :ty g
g :: () -> () -> Bool

我想你可能会被“单态限制”搞砸,因为它适用于类型类。在任何情况下,如果您退出顶级循环,并将内容放入具有显式类型签名的单独文件中,那么一切都可以正常工作:

module X where

n f = (\a -> \b -> not $ f a b)
f a b = a > b

g :: Ord a => a -> a -> Bool
g = n f

奖金问题 paper on QuickCheck 还有拉尔夫·辛兹的论文 Generics for the Masses