Come comporre `non` con una funzione di arità arbitraria?

Question

Quando ho una funzione di tipo come

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

Vorrei fare la funzione che avvolge questa funzione con no.

es. far funzionare in questo modo

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

Posso fare il combinatore come

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

Ma non so come.

*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

Cosa sto sbagliando?

E domanda bonus come posso farlo per funzionare con più e meno parametri, ad esempio

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

Answer 1

A meno che tu non voglia andare in giro con le macchine da scrivere, che è meglio lasciare agli esperimenti di pensiero e alla prova del concetto, semplicemente non generalizzi a più argomenti. Non provarci.

Per quanto riguarda la tua domanda principale, questo è elegantemente risolto con i combinatori editor semantici di Conal Elliott . Un combinatore di editor semantici è una funzione con un tipo come:

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

Dove F (x) è un'espressione che coinvolge x . Esistono anche "contravariante" combinatori di editor che prendono invece un (b - > a) . Intuitivamente, un combinatore di editor seleziona una parte di un valore maggiore su cui operare. Quello di cui hai bisogno si chiama risultato :

result = (.)

Guarda il tipo di espressione su cui stai cercando di operare:

a -> a -> Bool

Il risultato (codomain) di questo tipo è a - > Bool e il risultato di quel tipo è Bool , ed è quello a cui stai cercando di applicare non . Quindi per applicare non al risultato del risultato di una funzione f , scrivi:

(result.result) not f

Questo si generalizza magnificamente. Ecco alcuni altri combinatori:

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

Quindi se hai un valore x di tipo:

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

E vuoi applicare non a Bool, devi solo precisare il percorso per arrivarci:

(result.left.result.second) not x

Oh, e se sei già arrivato a Functors, noterai che fmap è un combinatore di editor. In effetti, quanto sopra può essere scritto:

(fmap.left.fmap.fmap) not x

Ma penso che sia più chiaro usare i nomi espansi.

Enjoy.

Answer 2

In realtà, fare arbitrarietà arbitraria con le classi di tipi risulta incredibilmente facile:

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

Grazie per aver segnalato questo fantastico problema. Adoro Haskell.

Answer 3

Il tuo n combinatore può essere scritto:

n = ((not .) .)

Per quanto riguarda la tua domanda bonus, il modo tipico per aggirare sarebbe quello di crearne alcuni:

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

ecc.

Answer 4

Ri: Cosa sto facendo di sbagliato? :

Penso che il tuo combinatore vada bene, ma quando lo lasci legare al livello più alto, entra in gioco una delle fastidiose "regole predefinite" di Haskell e l'associazione non è generalizzata:

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

Penso che potresti essere ostruito dalla "restrizione del monomorfismo" in quanto si applica alle classi di tipi. In ogni caso, se esci dal ciclo di livello superiore e metti le cose in un file separato con una firma di tipo esplicito, tutto funziona bene:

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

Domanda bonus : per fare ciò con sempre più parametri di tipo, puoi provare a giocare brutti scherzi con il sistema di classe di tipo. Due articoli da consultare sono il di Hughes e Claessen su QuickCheck e il documento di Ralf Hinze Generics for the Masses .