Comment composer `not` avec une fonction d'arité arbitraire?

Question

Quand j'ai une fonction de type comme

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

Je voudrais créer une fonction qui n'englobe pas cette fonction.

par exemple. faire fonctionner comme ça

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

Je peux faire un combinateur comme

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

Mais je ne sais pas comment.

*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

Qu'est-ce que je fais de travers?

Et la question de prime comment je peux le faire pour fonctionner avec plus et moins de paramètres, par exemple.

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

Answer 1

À moins que vous ne vouliez vous lancer dans des classes de types, qu'il vaut mieux laisser pour des expériences de pensée et des preuves de concept, vous ne devez pas généraliser à plusieurs arguments. N'essayez pas.

En ce qui concerne votre question principale, elle est résolue avec élégance avec les combinateurs d'éditeur sémantique de Conal Elliott . Un combinateur d'éditeur sémantique est une fonction de type:

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

Où F (x) est une expression impliquant x . Il y a aussi " contravariant " des combinateurs d'éditeurs qui prennent à la place un (b - > a) . Intuitivement, un combinateur d'éditeurs sélectionne une partie d'une valeur plus grande sur laquelle opérer. Celui dont vous avez besoin s'appelle result :

result = (.)

Regardez le type de l'expression que vous essayez d'utiliser:

a -> a -> Bool

Le résultat (codomaine) de ce type est a - > Bool , et le résultat de ce type est Bool , et c'est ce à quoi vous essayez d'appliquer et non . Donc, pour appliquer pas au résultat du résultat d'une fonction f , vous écrivez:

(result.result) not f

Cela se généralise magnifiquement. Voici quelques autres combinateurs:

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

Donc, si vous avez une valeur x de type:

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

Et vous voulez appliquer pas au Bool, vous devez épeler le chemin pour y arriver:

(result.left.result.second) not x

Oh, et si vous avez déjà contacté Functors, vous remarquerez que fmap est un combinateur d’éditeur. En fait, ce qui précède peut s’épeler:

(fmap.left.fmap.fmap) not x

Mais je pense qu'il est plus clair d'utiliser les noms développés.

Profitez.

Answer 2

En fait, faire des arities arbitraires avec des classes de types s'avère incroyablement 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 (<)

Merci d'avoir signalé ce problème intéressant. J'aime Haskell.

Answer 3

Votre combinateur n peut s’écrire:

n = ((not .) .)

En ce qui concerne votre question sur les bonus, la solution classique consiste à en créer plusieurs:

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

etc.

Answer 4

Re: Qu'est-ce que je fais mal? :

Je pense que votre combinateur va bien, mais lorsque vous le liez au niveau supérieur, l'une des "règles par défaut" ennuyeuses de Haskell entre en jeu et la liaison n'est pas généralisée:

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

Je pense que vous êtes peut-être en train de vous faire avoir par la "restriction de monomorphisme" appliquée aux classes de types. Dans tous les cas, si vous sortez de la boucle de niveau supérieur et placez les éléments dans un fichier séparé avec une signature de type explicite, tout fonctionne correctement:

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

Question sur les bonus : pour ce faire, avec de plus en plus de paramètres de type, vous pouvez essayer de jouer aux tours avec le scorbut avec le système de classes de types. Les deux documents à consulter sont le article sur QuickCheck de Hughes et Claessen et l'article de Ralf Hinze Génériques pour les masses .