En Haskell, exécution de `and` et `or` pour les fonctions booléennes

Question

Je viens d'écrire les deux fonctions suivantes :

fand :: (a -> Bool) -> (a -> Bool) -> a -> Bool
fand f1 f2 x = (f1 x) && (f2 x)

f_or :: (a -> Bool) -> (a -> Bool) -> a -> Bool
f_or f1 f2 x = (f1 x) || (f2 x)

Ils peuvent être utilisés pour combiner les valeurs de deux fonctions booléennes telles que :

import Text.ParserCombinators.Parsec
import Data.Char

nameChar = satisfy (isLetter `f_or` isDigit)

Après avoir examiné ces deux fonctions, je me suis rendu compte qu'elles sont très utiles, à tel point que je soupçonne maintenant qu'elles sont incluses dans la bibliothèque standard, ou plus probablement qu'il existe un moyen propre de faire cela en utilisant des fonctions existantes.

Quelle était la "bonne" façon de faire ?

Answer 1

Une simplification,

f_and = liftM2 (&&)
f_or  = liftM2 (||)

ou

      = liftA2 (&&)         
      = liftA2 (||)

dans le ((->) r) foncteur applicatif.

---

Version applicative

Pourquoi ? Nous l'avons fait :

instance Applicative ((->) a) where
    (<*>) f g x = f x (g x)

liftA2 f a b = f <$> a <*> b

(<$>) = fmap

instance Functor ((->) r) where
    fmap = (.)

Donc :

  \f g -> liftA2 (&&) f g
= \f g -> (&&) <$> f <*> g          -- defn of liftA2
= \f g -> ((&&) . f) <*> g          -- defn of <$>
= \f g x -> (((&&) . f) x) (g x)    -- defn of <*> - (.) f g = \x -> f (g x)
= \f g x -> ((&&) (f x)) (g x)      -- defn of (.)
= \f g x -> (f x) && (g x)          -- infix (&&)

---

Version monade

Ou pour liftM2 nous avons :

instance Monad ((->) r) where
    return = const
    f >>= k = \ r -> k (f r) r

donc :

  \f g -> liftM2 (&&) f g
= \f g -> do { x1 <- f; x2 <- g; return ((&&) x1 x2) }               -- defn of liftM2
= \f g -> f >>= \x1 -> g >>= \x2 -> return ((&&) x1 x2)              -- by do notation
= \f g -> (\r -> (\x1 -> g >>= \x2 -> return ((&&) x1 x2)) (f r) r)  -- defn of (>>=)
= \f g -> (\r -> (\x1 -> g >>= \x2 -> const ((&&) x1 x2)) (f r) r)   -- defn of return
= \f g -> (\r -> (\x1 ->
               (\r -> (\x2 -> const ((&&) x1 x2)) (g r) r)) (f r) r) -- defn of (>>=)
= \f g x -> (\r -> (\x2 -> const ((&&) (f x) x2)) (g r) r) x         -- beta reduce
= \f g x -> (\x2 -> const ((&&) (f x) x2)) (g x) x                   -- beta reduce
= \f g x -> const ((&&) (f x) (g x)) x                               -- beta reduce
= \f g x -> ((&&) (f x) (g x))                                       -- defn of const
= \f g x -> (f x) && (g x)                                           -- inline (&&)

Answer 2

Totalement l'arnaque de TomMD, j'ai vu les and . map y or . map et je n'ai pas pu m'empêcher de vouloir le modifier :

fAnd fs x = all ($x) fs
fOr fs x = any ($x) fs

Ils se lisent bien, je pense. fAnd : sont toutes les fonctions de la liste True quand x leur est appliquée ? fOr : il y a des fonctions dans la liste True quand x leur est appliquée ?

ghci> fAnd [even, odd] 3
False
ghci> fOr [even, odd] 3
True

fOr est un choix de nom étrange, cependant. Il s'agit certainement d'un bon choix pour lancer les programmeurs impératifs pour une boucle . =)

Answer 3

C'est plus moche si vous voulez toujours deux fonctions, mais je pense que je le généraliserais :

mapAp fs x = map ($x) fs

fAnd fs = and . mapAp fs
fOr fs = or . mapAp fs

> fOr [(>2), (<0), (== 1.1)] 1.1
True
> fOr [(>2), (<0), (== 1.1)] 1.2
False
> fOr [(>2), (<0), (== 1.1)] 4
True

Answer 4

En plus de ce que Don a dit, le liftA2/liftM2 les versions ne sont peut-être pas assez paresseuses :

> let a .&&. b = liftA2 (&&) a b in pure False .&&. undefined

*** Exception: Prelude.undefined

Woops !

Vous pouvez donc opter pour une fonction légèrement différente. Notez que cette nouvelle fonction nécessite un Monad contrainte -- Applicative est insuffisante.

> let a *&&* b = a >>= \a' -> if a' then b else return a' in pure False *&&* undefined

False

C'est mieux.

Quant à la réponse qui suggère la on c'est pour les cas où les fonctions sont les mêmes mais les arguments sont différents. Dans votre cas, les fonctions sont différentes mais les arguments sont les mêmes. Voici votre exemple modifié de sorte que on est une réponse appropriée :

(f x) && (f y)

qui peut s'écrire :

on (&&) f x y

PS : les parenthèses sont inutiles.

Answer 5

Cela peut également être fait en utilisant Flèches :

import Control.Arrow ((&&&), (>>>), Arrow(..))

split_combine :: Arrow cat => cat (b, c) d -> cat a b -> cat a c -> cat a d
split_combine h f g = (f &&& g) >>> h

letter_or_digit = split_combine (uncurry (||)) isLetter isDigit

&&& (non lié à && ) divise l'entrée ; >>> est une composition flèche/catégorie.

Voici un exemple :

> map letter_or_digit "aQ_%8"
[True,True,False,False,True]

Cela fonctionne parce que les fonctions -- -> -- sont des instances de Category et Arrow. En comparant les signatures de type à celles de Don liftA2 y liftM2 Les exemples montrent les similitudes :

> :t split_combine 
split_combine :: Arrow cat => cat (b, c) d  -> cat a b -> cat a c -> cat a d

> :t liftA2
liftA2    :: Applicative f => (b -> c -> d) ->     f b ->     f c ->     f d

Outre le curry, notez que vous pouvez presque convertir le premier type en le second en substituant cat a ---> f y Arrow ---> Applicative (l'autre différence est que split_combine n'est pas limité à prendre des fonctions pures dans son 1er argument ; ce n'est probablement pas important cependant).