Wie zu komponieren `not` mit einer Funktion von beliebiger arity?

Question

Wenn ich eine Funktion vom Typ wie

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

Ich sollte Schliesser welche wickeln diese Funktion mit nicht mögen.

z. Schliesser wie diese

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

Ich kann machen combinator wie

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

Aber ich weiß nicht, wie.

*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

Was mache ich falsch?

Und Bonus-Frage, wie ich dies mit mehr für die Funktion tun kann, und damit Parameter z.

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

Answer 1

Wenn Sie nicht mit typeclasses Hacking um gehen wollen, was für Gedankenexperimente und Proof of Concept besser links, Sie verallgemeinern einfach nicht auf mehrere Argumente. Versuchen Sie nicht.

Wie für Ihre Hauptfrage, das die meisten ist elegant mit Conal Elliott semantischem Editor combinators gelöst. Ein semantischer Editor combinator ist eine Funktion mit einem Typ wie:

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

Wo F(x) ist einiger Ausdruck, der x. Es gibt auch „kontra“ Editor Kombinatoren, die stattdessen eine (b -> a) nehmen. Intuitiv wählt ein Editor Kombinator einen Teil eines größeren Wertes für den Betrieb auf. Das benötigen Sie heißt result:

result = (.)

Sehen Sie sich die Art des Ausdrucks Sie versuchen zu arbeiten auf:

a -> a -> Bool

Das Ergebnis (codomain) dieser Art ist a -> Bool, und das Ergebnis der , die Typ Bool ist, und das ist, was Sie versuchen not zu bewerben. So not auf das Ergebnis des Ergebnisses einer Funktion f anzuwenden, schreiben Sie:

(result.result) not f

Dieses schön verallgemeinert. Hier sind ein paar mehr combinators:

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
...

Wenn Sie also einen Wert x vom Typ:

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

Und Sie wollen not auf die Bool anzuwenden, buchstabieren Sie nur den Weg dorthin zu gelangen:

(result.left.result.second) not x

Ach ja, und wenn Sie noch zu bekommen Funktoren haben, werden Sie, dass fmap bemerken ist ein Editor combinator. In der Tat kann die oben geschrieben werden:

(fmap.left.fmap.fmap) not x

Aber ich denke, es klarer ist die erweiterten Namen zu verwenden.

Genießen.

Answer 2

Eigentlich dreht sich dabei willkürlich arity mit Typ-Klassen, um sein unglaublich einfach:

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

Danke für dieses kühle Problem hingewiesen. Ich liebe Haskell.

Answer 3

Ihre n combinator kann geschrieben werden:

n = ((not .) .)

Wie für Ihre Bonus-Frage, die typische Art und Weise um würde mehr von diesen zu erstellen:

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

etc.

Answer 4

Re: Was mache ich falsch :

Ich denke, Ihr combinator in Ordnung ist, aber wenn man let-bind es auf der obersten Ebene, von Haskell ist ärgerlich ‚Standardregeln‘ ins Spiel kommt und die Bindung ist nicht verallgemeinert:

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

Ich glaube, Sie können durch die ‚Monomorphie Beschränkung‘ verprügelt werden immer wie es Klassen zu geben gilt. Auf jedem Fall, wenn Sie aus der Top-Level-Schleife bekommen und Dinge in eine separate Datei mit einer expliziten Art Unterschrift setzen, alles funktioniert gut:

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

Bonus Frage : Dieser Parameter des Typs mit mehr und mehr zu tun, können Sie Skorbut Tricks mit dem Typ-Klassen-System versuchen zu spielen. Zwei Papiere zu konsultieren sind Hughes und Claessen Papier auf Quick Check und Ralf Hinze Papier Generics für die Massen .