Is it possible to pattern match on a function type?

Question

I'm writing a mini-language, and I have a situation where I'm trying to process an abstract syntax tree such that it either returns an exception, or a function which will resolve to a bool. Here's a minimal example:

data MyException = Can'tResolveToBool

data InputToBeAddedLater =
    InputToBeAddedLater String

data Exp a =
    ReturnsBoolFunc String (Exp a)
    | IsBool Bool
    | ReturnsExpFunc String (Exp a)

resolveToExp :: String -> Exp a -> (InputToBeAddedLater -> Exp a)
resolveToExp funcName arg
    | funcName == "patently_false" = (\_ -> IsBool False)

resolveToBool :: Exp a -> Either MyException Bool
resolveToBool (ReturnsBoolFunc funcName (ReturnsExpFunc fn arg)) =
    let resolved = resolveToExp fn arg
    in case resolved of
        ((InputToBeAddedLater _) -> (IsBool bool)) -> Right bool
        ((InputToBeAddedLater _) -> (ReturnsExpFunc _ _)) -> Left Can'tResolveToBool

The last line is my (sadly, non-functional) attempt to pattern match on a function type. GHC recommends I try the ViewPatterns extension, but looking briefly at this, I'm not sure that it's what I need. Is it conceptually impossible to do what I'm trying to do here?

Thanks!

Answer 1

Let's simplify the question dramatically. This is the core of your question: can I implement desired?

desired :: (String -> Bool) -> Bool
desired f = case f of
    (_ -> True ) -> True
    (_ -> False) -> False

Hopefully with all of the chaff winnowed away it's clear that there's no way this can be done: there is not necessarily a fact of the matter about whether f returns True or False. The value it returns is allowed to depend on what input you pass it!

Answer 2

What, as I understand it, you try to express with the pattern

  case resolved of
    ((InputToBeAddedLater _) -> (IsBool bool)) -> ...

is to check whether resolved returns for any input something with the outer constructor IsBool. I.e. whether it is of the form

resolved (InputToBeAddedLater i) = IsBool (...)

This you can at least validate without needing to provide a concrete i, thanks to non-strictness:

  case resolved (InputToBeAddedLater undefined) of
    (IsBool bool) -> Right bool
    (ReturnsExpFunc _ _) -> Left Can'tResolveToBool

The problem with this is that it blows up if resolved actually evaluates its argument before providing an outer constructor, for example

resolved (InputToBeAddedLater "") = IsBool False
resolved (InputToBeAddedLater s) = ReturnsExpFunc "" (IsBool True)

You could now add some error-catching mechanism on top of this, but that can only really be done in IO and is anyways hacky.

Really, I think this is an XY question, and what you should actually do is give resolved a way to signal its result's outer constructor without having any input at all. This can be achieved by generalising Exp so it includes the InputToBeAddedLater, but only after revealing the outermost constructor:

data ExpH m a
  = ReturnsBoolFunc (m (String, Exp a))
  | IsBool (m Bool)
  | ReturnsExpFunc (m (String, Exp a))

type Exp = ExpH Identity

resolveToExp :: String -> Exp a -> ExpH ((->) InputToBeAddedLater) a
resolveToExp funcName arg
    | funcName == "patently_false" = IsBool (const False)

resolveToBool :: Exp a -> Either MyException Bool
resolveToBool (ReturnsBoolFunc funcName (Identity (ReturnsExpFunc fn arg)))
   = case resolveToExp fn arg of
        IsBool b -> Right (b undefined) -- here you would actually provide an argument
        ReturnsExpFunc _ -> Left Can'tResolveToBool