The equality of computable functions of a certain type is decidable.

eq.hs

class Finite t where
  allValues :: [t]

eq :: (Eq a, Finite b, Eq c) => ((a -> b) -> c) -> ((a -> b) -> c) -> Bool
eq f g =
  let -- spy :: (Eq a, Finite b) => [(a, b)] -> a -> b
      spy codebook k =
        case lookup k codebook of
          Just v -> v
          Nothing -> head (filter (\v -> not (test ((k, v) : codebook)))
                                  (tail allValues)
                           ++ [head allValues])
      -- test :: [(a, b)] -> Bool
      test codebook = f (spy codebook) == g (spy codebook)
  in test []


-- For example...
instance Finite Bool where
  allValues = [True, False]

f :: (Integer -> Bool) -> Integer
f p = if p 3 then 333 else 444
f' p = if not (p 3) then 444 else 333

main = putStrLn $ show $ eq f f'