任意のアリティの関数で「not」を構成する方法は？

Question

次のようなタイプの関数がある場合

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

この関数をラップしないmake関数が必要です。

e.g。このような関数を作成

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-＆gt; a）を使用するエディターコンビネータ。直観的には、エディターのコンビネーターは、より大きな値の一部を選択して操作します。必要なものは result ：

と呼ばれます

result = (.)

操作しようとしている式のタイプを見てください：

a -> a -> Bool

このタイプの結果（コドメイン）は a-＆gt;です。 Bool 、および that 型の結果は Bool であり、それは not を適用しようとしているものです。したがって、関数 f の結果の結果に not を適用するには、次のように記述します。

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

そして、 not をBoolに適用したい場合は、そこにたどり着くためにパスを綴るだけです：

(result.left.result.second) not x

ああ、Functorsにアクセスしたことがあるなら、 fmap がエディターコンビネーターであることに気付くでしょう。実際、上記は綴ることができます：

(fmap.left.fmap.fmap) not x

しかし、拡張名を使用する方が明確だと思います。

お楽しみください。

Answer 2

実際には、型クラスで任意のアリティを実行することは非常に簡単であることがわかりました：

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

このクールな問題を指摘してくれてありがとう。 Haskellが大好きです。

Answer 3

n個のコンビネータを記述できます：

n = ((not .) .)

ボーナスの質問に関しては、一般的な方法はこれらのいくつかを作成することです：

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

etc。

Answer 4

再：何が間違っているのですか？：

コンビネータは問題ないと思いますが、トップレベルでバインドすると、Haskellの厄介な「デフォルトルール」の1つが作用し、バインディングは一般化されません：

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

ボーナス質問：より多くの型パラメーターでこれを行うには、型クラスシステムで壊血病のトリックを試してみてください。相談する2つの論文は、HughesとClaessenの QuickCheckの論文とRalf Hinzeの論文大衆のためのジェネリック。