Haskell: Comment composer «non» 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 faire une fonction qui enveloppe cette fonction avec pas.

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 mal?

Et la question bonus comment je peux le faire pour fonctionner avec plus de paramètres et de peur par exemple

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

Answer 1

En fait, faire de l'arité arbitraire 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 sympa. J'adore Haskell.

Answer 2

Sauf si vous voulez aller de piratage autour avec typeclasses, ce qui est préférable pour des expériences de pensée et de preuve de concept, vous venez de ne pas généraliser à plusieurs arguments. N'essayez pas.

Quant à votre question principale, c'est le plus élégamment résolu avec Conal Elliott sémantique de l'éditeur combinators. D'une sémantique de l'éditeur du combinator est une fonction avec un type comme:

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

Où F(x) est une expression faisant intervenir x. Il y a aussi "contravariant" éditeur combinators qui prennent un (b -> a) à la place. Intuitivement, un éditeur de combinateur sélectionne une partie de certains des plus grands de la valeur à opérer. Celui dont vous avez besoin est appelée result:

result = (.)

Regardez le type de l'expression que vous essayez de faire fonctionner sur:

a -> a -> Bool

Le résultat (arrivée) de ce type est a -> Bool, et le résultat qui est de type Bool, et c'est ce que vous essayez d'appliquer not de. Alors appliquez not à la suite du résultat d'une fonction f, vous écrivez:

(result.result) not f

Cette belle généralise. Voici un peu plus de 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
...

Donc, si vous avez une valeur x de type:

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

Et vous voulez appliquer l' not de la valeur Bool, vous venez de préciser le chemin d'accès pour vous y rendre:

(result.left.result.second) not x

Oh, et si vous avez obtenu de Foncteurs encore, vous remarquerez qu' fmap est un éditeur combinator. En fait, le ci-dessus peut être orthographié:

(fmap.left.fmap.fmap) not x

Mais je pense que c'est plus clair d'utiliser les noms étendues.

Profitez de.

Answer 3

Votre n combinateur peut s'écrire:

 n = ((not .) .)
 

En ce qui concerne votre question bonus, le moyen typique serait d'en créer plusieurs:

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

etc.

Answer 4

Re: Ce que je fais mal?:

Je pense que votre combinator est bien, mais quand vous les laissez-le lier au plus haut niveau, l'un des Haskell est ennuyeux 'règles par défaut' entre dans le 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 pouvez peut-être obtenir assommé par le "monomorphism restriction" tel qu'il s'applique à des classes de type. Dans tous les cas, si vous sortez de haut-niveau de la boucle et de mettre les choses dans un fichier séparé avec un type explicite signature, tout fonctionne bien:

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 Bonus: pour ce faire, et de plus en plus de paramètres de type, vous pouvez essayer de jouer le scorbut des trucs avec le type de système de classe. Deux documents à consulter sont Hughes et Claessen du papier sur QuickCheck et Ralf Hinze du papier Génériques pour les Masses.