13

Is there any way to compare two functions in Haskell?

My thought is that the answer is no since functions would not derive the Eq type class. However I'm trying to write a pretty trivial function and it seems like a normal sort of thing to do:

search :: ((Enum a) => a -> a) -> Card -> [Card]
search op x list = if (op == succ && rank x == King) || 
                      (op == pred && rank x == Ace)
                   then []
                   else let c = [ n | n <- list, rank n == op (rank x)]
                     in if length c == 1
                     then x : search op (head c) list
                     else []

Error message:

No instance for (Eq (Rank -> Rank))
      arising from a use of `=='

Basically it either searches up or down a list of cards looking for a match with either the next or previous ranked card from x, building a list. By taking the 'pred' or 'succ' function as an operator it works both forwards and backwards. However, I need to check that it doesn't go out of bounds on the enum otherwise it throws an exception.

So I'm looking for a way to prevent the exception or solve this problem!

Any other pointers on improving the code would also be appreciated :)

Thanks for all the great tips, this is the solution I have come up with (taken bits from every answer really!):

EDIT: Correct solution below:

 maybeSucc x | x == maxBound = Nothing
             | otherwise = Just (succ x)
 maybePred x | x == minBound = Nothing  
             | otherwise = Just (pred x)

-- takes a list of cards which have a rank one op than x
-- only if there is exactly one is it sequential, otherwise end matching
search :: (Rank -> Maybe Rank) -> Rank -> [Card] -> [Card]
search op x list = case filter (\n -> Just (rank n) == op x) list of
                    [y] -> y : search op (rank y) list
                     _ -> []

Test:

*Main> let cards = [Card Ace Heart, Card Two Club, Card Three Spade, Card Five Club, Card Four Diamond]

*Main> search maybeSucc Two cards

[Three of Spades,Four of Diamonds,Five of Clubs]

*Main> search maybePred Three cards

[Two of Clubs,Ace of Hearts]
Improve this question
4
  • What happens if something other than succ or pred is passed for op, that may eventually use succ or pred? What about succ' = succ? Commented Dec 1, 2010 at 20:29
  • The use of 'length c == 1' is very suspect - use 'not . null $ c' or a case statement - assuming you really meant 'length c > 0' Commented Dec 1, 2010 at 20:44
  • I think it needs to check whether there are any matches to x in list, assuming x is IN the list (not clear from the question) Commented Dec 1, 2010 at 20:52
  • Your code actually finds (and uses) a single match. If you wanted to check for any matches existing you could just use any (\n -> rank n == op (rank x)) list, or if you wanted to use the first of one or more matches you could use a pattern like (y:_) -> .... instead of [y]. Commented Dec 1, 2010 at 21:12

5 Answers 5

Reset to default
23

Unhelpful Answer

There is not, and will never be, a way to compare two functions for equality. There is a mathematical proof that it is not possible in general.

"Pragmatic" approaches will either depend on the internal workings of your compiler (e.g. if two functions are equal if they are represented by the same memory address internally), or be less helpful than expected. What is the expected result of succ == (+1)? How about let a == 1 in succ == (+a)?

I can't think of a way to define (==) for functions that always makes sense, and I believe neither can anyone else.

Things Irrelevant to the Question

The type signature is missing a return type.

Your function has a rank 2 type, which is not standard Haskell 98, and, more importantly, is not necessary in this case. You don't care if the passed-in function can deal with any Enum type, you only care that it works for Rank:

search :: (Rank -> Rank) -> Card -> [Card] -> [Card]   -- much simpler.

I'd try to use case more often, and if/then less often. In particular, I'd write:

case [ n | n <- list, rank n == op (rank x)] of
    [y] -> x : search op y list   -- length == 1
    _ -> []                       -- otherwise

My Real Answer

Your function basically only works with two different values for op, but its type doesn't say so; that doesn't feel right for me.

You could do it the old-fashioned way:

data Direction = Succ | Pred deriving(Eq)

search :: Direction -> Card -> [Card] -> [Card]
search dir x list = if (dir == Succ && rank x == King) ...
    ... let op = case Direction of Succ -> succ ; Pred -> pred
        in ...

Or you could make the parameter more general, and pass a function that may fail gracefully (by returning Nothing) instead:

maybeSucc x | x == maxBound = Nothing
            | otherwise = Just (succ x)

search :: (Rank -> Maybe Rank) -> Card -> [Card] -> [Card]
search op x list = case op (rank x) of
    Nothing -> []
    Just theRank -> case [ n | n <- list, rank n == theRank ] of ...
Improve this answer
Sign up to request clarification or add additional context in comments.

9 Comments

"There is not, and will never be, a way to compare two functions for equality" is a bit too general. Mathematically, a function is just a relation between the domain and the range - the method of getting from one to another isn't important. That means that if we can enumerate all the possible inputs and compare the of each function for equality, then we can compare two functions for equality. Now, if we have an infinite domain, we won't be able to determine equality in finite time, but for a finite domain (like Bool or Card), then deciding equality in finite time should be easy.
In Haskell instance (Enum a, Bounded a, Eq b) => Eq (a -> b) where f == g = all ((==) <$> f <*> g) [minBound .. maxBound]
Of course, this (==) function will return bottom whenever f or g are not total on [minBound .. maxBound].
@rampion On a more serious note, I stand by what I have said. The range of every function in Haskell includes bottom, which is the value that the function is said to have if the computation does not terminate. Checking for function equality involves solving the halting problem, even when the domains are finite.
As irrelevant as it may be, I should point out that there are (somewhat amazingly) some infinite domains on which any total functions can be compared for equality in finite time. See: math.andrej.com/2007/09/28/…
|
8

Well, there's no concept of "reference equality" in Haskell, and "behavioral equality" of functions isn't possible to check in the general case. Although it is possible to do it for functions operating only on small, finite types (as Rank would be), it's usually unwise because it leads to combinatorial explosion if you're not careful.

There are various ways you could accomplish your immediate goal, such as:

  • Instead of using succ and pred directly, use self-guarding functions with type Enum a => a -> Maybe a that produce Nothing rather than an exception.

  • Pass in a "stop" value to check against, e.g. search op end x list = if x == end then [] ....

  • Forget about succ and pred entirely and just pass in a list of values to compare against, e.g. search :: [Rank] -> Card -> [Card] -> [Card], and end the search if the list of ranks is empty.

A couple other remarks on your code:

  • Your list comprehension is reinventing the wheel--look for standard library functions, such as filter, that will do what you want.

  • Don't compare the length of a list to a small constant--use pattern matching instead.

Improve this answer

3 Comments

thanks for taking the time to answer. I was under the impression list comprehension was interpreted by the compiler to be the same as using filter (syntactic sugar)? Could I use pattern matching on an intermediate value (c)?
The list comprehension in this case is desugared to: [ n | n <- list, rank n == op (rank x)] ---> list >>= \n -> if rank n == op (rank x) then [n] else [] or something along those lines.
@Guy: The result is the same, but using standard library functions produces more readable code than reimplementing them. And pattern matching on intermediate values is done with a case expression, e.g. case filter ((== op (rank x)) . rank) list of [c] -> .....
7

1) Your op is overly general. You'll only be using it for Card whatever type rank (undefined :: Card) is, so just make it RankThing -> RankThing. Also, your function type signature is missing a return value type.

2) An example intended use looks like it would be search succ Ace xs, but that's rather clumsy, how about two auxillary functions that handle the bounds:

searchUp King _ = []
searchUp x ys = search succ x ys

searchDown Ace _ = []
searchDown x ys = search pred x ys

This might read better for your users and avoid the need to check the operation

3) if you really want to check what operation is performed, and know the operation will be one of two possibilities, then you can either name the operation or test it with a known answer test (KAT). For example:

data Operation = Succ | Pred

search :: Operation -> Card -> [Card] -> []
search Succ King _ = []
search Succ x ys = search' succ x ys
search Pred Ace _ = []
search Pred x ys = search' pred x ys

And the KAT solution (rather lame, imo):

search op x ys
    | op Five == Four && rank x == Ace = []
    | op Five == Six && rank x == King = []
    | otherwise = ...
Improve this answer

2 Comments

using two functions was my intial thought (before adding the op parameter) but it seemed like it was repeating code. The way you have done it is much better though because it doesnt repeat the whole function. This is actually a sub function of another, which is why the definition is wrong (I only added it to clarify for the question).
I realize now why I couldnt do the two function option- the recursive calls to search need to check the bounds of the array as well as the initial one! Also, the pattern matching doesnt work on the searchUp searchDown since x is of type Card not type Rank. I think I have the details to make it work now though...
5

As long as the functions are over appropriate domains and ranges (Enum, Bounded, Eq, etc., in slightly different combination for domain and range), you can compare finite functions, even higher-order ones, in a straight-forward way and then automate the process using type classes.

I wrote up the idea in a post to the one of the Haskell mailing lists and then (more properly) in a paper I presented at one of the FDPE conferences (Victoria, BC). I've never seen it done before, but I wouldn't be surprised if others have also done it: it's a pretty simple idea, once you get over the bugaboo that "functions can't be compared for equality". Of course, the usual caveats about partiality and strictness apply: e.g., you can't return True for two functions that both fail to terminate for some common argument.

But for finite domains this technique works and provides a lot of practical use. (Plus it's really just fun to use :) ).

Edit: I added the code to hpaste here; it works in Hugs, but needs some tweaks for GHC.

Edit 2: I added a pragma and comment to the hpaste-d code so that it works in both GHC and Hugs. I also added this example as test3 (it returns True, as expected, and in short order):

(\x -> [(&&x), (||x), not]) == (\y -> [(y&&), (y||), not . not . not])
Improve this answer

Comments

1

The code below may not compile, but hopefully you get the idea:

data Op = Succ | Pred deriving Eq

fromOp :: Enum a => Op -> a -> a
fromOp Succ = succ
fromOp Pred = pred

search :: Op -> Card -> [Card] -> [Card]
search op x list = if (op == Succ && rank x == King) || 
                      (op == Pred && rank x == Ace)
                   then []
                   else let c = [ n | n <- list, rank n == (fromOp op) (rank x)]
                     in if length c == 1
                     then x : search op (head c) list
                     else []
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.