In Haskell performing `and` and `or` for boolean f

问题:

I just wrote the following two functions:

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)

They might be used to combined the values of two boolean functions such as:

import Text.ParserCombinators.Parsec
import Data.Char

nameChar = satisfy (isLetter `f_or` isDigit)

After looking at these two functions, I came to the realization that they are very useful. so much so that I now suspect that they are either included in the standard library, or more likely that there is a clean way to do this using existing functions.

What was the "right" way to do this?

回答1:

One simplification,

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

or

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

in the ((->) r) applicative functor.

---

Applicative version

Why? We have:

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

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

(<$>) = fmap

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

So:

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

---

Monad version

Or for liftM2, we have:

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

so:

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

回答2:

It's uglier if you always want two functions, but I think I'd generalize it:

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

回答3:

Totally ripping off of TomMD, I saw the and . map and or . map and couldn't help but want to tweak it:

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

These read nicely I think. fAnd: are all functions in the list True when x is applied to them? fOr: are any functions in the list True when x is applied to them?

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

fOr is an odd name choice, though. Certainly a good one to throw those imperative programmers for a loop. =)

回答4:

On top of what Don said, the liftA2/liftM2 versions may not be lazy enough:

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

*** Exception: Prelude.undefined

Woops!

So instead you might want a slightly different function. Note that this new function requires a Monad constraint -- Applicative is insufficient.

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

False

That's better.

As for the answer that suggests the on function, this is for when the functions are the same but the arguments are different. In your given case, the functions are different but the arguments are the same. Here is your example altered so that on is an appropriate answer:

(f x) && (f y)

which can be written:

on (&&) f x y

PS: the parentheses are unnecessary.

回答5:

This can also be done using Arrows:

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

&&& (not related to &&) splits the input; >>> is arrow/category composition.

Here's an example:

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

This works because functions -- -> -- are instances of Category and Arrow. Comparing the type signatures to Don's liftA2 and liftM2 examples shows the similarities:

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

Besides the currying, note that you can almost convert the first type into the second by substituting cat a ---> f and Arrow ---> Applicative (the other difference is that split_combine isn't limited to taking pure functions in its 1st argument; probably not important though).

回答6:

This has sortof been mentioned but in a more complex way. You could use applicative stuff.

For functions basically what it does is pass the same argument to a number of functions that you can combine at the end.

So you could implement it like this:

(&&) <$> aCheckOnA <*> anotherCheckOnA $ a

For each <*> in the chain then you get another function that applies to a and then you munge all the output together using fmap alternately written as <$>. The reason this works with && is because it takes two arguments and we have 2 functions starred together. If there was an extra star in there and another check you'd have to write something like:

(\a b c -> a && b && c) <$> aCheckOnA <*> anotherCheckOnA <*> ohNoNotAnotherCheckOnA $ a

check this out for more examples

回答7:

If f1 and f2 are the same, then you can use 'on':

on :: (b -> b -> c) -> (a -> b) -> a -> a -> c

in base Data.Function

fand1 f = (&&) `on` f
for1 f = (||) `on` f

Typical usage:

Data.List.sortBy (compare `on` fst)

(from Hoogle)