Automatically and deterministicly testing a function for associativity, commutativity etc

Question

Is it possible to construct a higher order function isAssociative that takes another function of two arguments and determines whether that function is associative?

Similar question but for other properties such as commutativity as well.

If this is impossible, is there any way of automating it in any language? If there is an Agda, Coq or Prolog solution I'm interested.

I can envision a brute force solution that checks every possible combination of arguments and never terminates. But "never terminates" is an undesirable property in this context.

Sneck

That depends: is the search space compact? – Prink

Answer 1

I guess Haskell isn't very suited for such things. Usually you do totally opposite to check. You declare that your object have some properties and thus could be used in some special way (see Data.Foldable). Sometimes you might want to promote your system:

import Control.Parallel
import Data.Monoid

pmconcat :: Monoid a => [a] -> a
pmconcat [x] = x
pmconcat xs = pmconcat (pairs xs) where
    pairs [] = []
    pairs [x] = [x]
    pairs (x0 : x1 : xs') = y `par` (y : ys) where
        y = x0 `mappend` x1
        ys = pairs xs'

data SomeType

associativeSlowFold = undefined :: SomeType -> SomeType -> SomeType

data SlowFold = SlowFoldId
              | SlowFold { getSlowFold :: SomeType }

instance Monoid SlowFold where
    mempty = SlowFoldId
    SlowFoldId `mappend` x = x
    x `mappend` SlowFoldId = x
    x0 `mappend` x1 = SlowFold y where
        y = (getSlowFold x0) `associativeSlowFold` (getSlowFold x1)
    mconcat = pmconcat

If you really want proof systems you might want to look also at those proof assistants you mentioned. Prolog - is logical language and I don't think that it also very suitable for that. But it might be used to write some simple assistant. I.e. to apply associativity rule and see that at lower levels it's impossible to derive equality.

Celestyn

Answer 2

The first solution which comes to my mind is using QuickCheck.

quickCheck $ \(x, y, z) -> f x (f y z) == f (f x y) z
quickCheck $ \(x, y) -> f x y == f y x

where f is a function we're testing. It won't prove neither associativity nor commutativity; it's simply the simplest way to write a brute force solution you've been thinking about. QuickCheck's advantage is it's ability to choose tests' parameteres which will hopefully be corner cases for tested code.

An isAssociative you're asking for could be defined as

isAssociative
  :: (Arbitrary t, Show t, Eq t) => (t -> t -> t) -> IO ()
isAssociative f = quickCheck $ \(x, y, z) -> f x (f y z) == f (f x y) z

It's in IO as QuickCheck chooses test cases by random.

Merryman

I don't want to "test" it heuristically, I want to "prove" it deterministically. That means no random tests. I'm upvoting for introducing me to an awesome function though. That function sounds like a godsend for unit tests. – Sneck