如何用任意arity函数组合`not`？

Question

当我有类似的功能

f :: (Ord a) => a -> a -> Bool
f a b = a > b

我想用make函数包装这个函数.

例如,使这样的功能

g :: (Ord a) => a -> a -> Bool
g a b = not $ f a b

我可以像组合一样组合

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

但我不知道怎么做.

*Main> let n f = (\a -> \b -> not $ f a b)
n :: (t -> t1 -> Bool) -> t -> t1 -> Bool
Main> :t n f
n f :: (Ord t) => t -> t -> Bool
*Main> let g = n f
g :: () -> () -> Bool

我究竟做错了什么？

并且奖励问题我如何能够通过更多和更少的参数来实现这一功能,例如

t -> Bool
t -> t1 -> Bool
t -> t1 -> t2 -> Bool
t -> t1 -> t2 -> t3 -> Bool

Answer 1

除非你想要使用类型类别进行攻击,这最好留给思想实验和概念证明,否则你只是不要推广到多个参数.别试试.

至于你的主要问题,这是Conal Elliott的语义编辑器组合器最优雅的解决方案.语义编辑器组合器是一种类型如下的函数:

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

F(x)某些表达涉及哪里x.还有"逆变"编辑器组合(b -> a)代替.直观地说,编辑器组合器选择一些较大值的一部分来操作.你需要的是result:

result = (.)

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

a -> a -> Bool

这种类型的结果(值域)是a -> Bool和的结果是类型Bool,这就是你想申请什么not来.所以要应用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]

而且你想申请notBool,你只需要说明实现目标的途径:

(result.left.result.second) not x

哦,如果你还有Functors,你会注意到它fmap是一个编辑组合.事实上,上面的拼写可以拼写:

(fmap.left.fmap.fmap) not x

但我认为使用扩展名称更清楚.

请享用.

Answer 2

实际上,使用类型类做任意arity变得异常简单:

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

谢谢你指出这个很酷的问题.我爱哈斯克尔.

Answer 3

你的n个组合子可以写成:

n = ((not .) .)

至于你的奖金问题,典型的方法是创建其中的几个:

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

等等

Answer 4

回复:我做错了什么？:

我认为你的组合器很好,但是当你把它绑定在顶层时,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

奖金问题:要使用越来越多的类型参数来做这件事,你可以尝试用类型系统玩坏血病技巧.要查阅的两篇论文是Hughes和Claessen 关于 QuickCheck的论文和Ralf Hinze撰写的论文" Geses for the Masses".