Haskell: Order-Insensitive Functional Application

Question

I want to implement an order-insensitive version of functional application in Haskell. By way of a little background: a prominent tradition in the semantics of natural language (deriving from Richard Montague, among others) assigns lambda functions of various types as the semantic values (sv's) of expressions. The truth-value of a sentence is computed by performing functional application on the sv's of the sentence's constituents. For a simple example, consider:

tl = [1..10]

bill :: Int
bill = 1

tall :: Int -> Bool
tall = \x -> x `elem` tl

Think of the sentence 'Bill is tall' as a tree with the left leaf occupied by 'Bill' and the right leaf occupied by 'tall'. We compute the truth-value of the sentence by applying the sv of the right leaf to the sv of the left leaf. Now consider 'Some man is tall': here the left leaf is occupied by `some man' [the sv of which is of type :: (Int -> Bool) -> Bool] and the right leaf is occupied by 'tall' [the sv of which is of type :: (Int -> Bool)]. We compute the truth-value of the sentence by applying the sv of the left leaf to the sv of the right leaf.

So, in this system, given a tree with left leaf a and right leaf b, we first check which leaf is in the domain of the other, and then apply functional application accordingly: if a is in the domain of b, we do b(a), whereas if b is in the domain of a, we do a(b).

How would I implement this kind of "order-insensitive" functional application in Haskell? I have written some functions that determine which leaf is in the domain of the other by parsing the result of

show (typeOf a)

for a leaf a. However, this seems to me unnecessarily cumbersome. Ghci gives an error if you try to e.g. evaluate

bill tall

So a simple way to check which item is in the domain of the other would be to just try applying one item to the other, and seeing whether an error/exception results. My question, then, is: how do I catch exceptions which result from a type-mismatch? That is, how do I catch non-IO exceptions of this sort?

Answer 1

You can't catch a type mismatch at run time; it's a compile-time error. (At least, not without using ghc-api to compile code at runtime. ghci is a wrapper around ghc-api, which is why it can do this.) You would need to find a way to capture this type distinction in an ADT to do it at runtime, or possibly use a typeclass (this introduces other complications, though).

Answer 2

You may get a long way with some type-class extensions:

{-# LANGUAGE FlexibleInstances     #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE TypeFamilies          #-}

class Copula l r where
  type Sem l r :: *
  is :: l -> r -> Sem l r

instance Copula (a -> b) a where
  type Sem (a -> b) a = b
  is = ($)

instance Copula a (a -> b) where
  type Sem a (a -> b) = b
  is = flip ($)   

For example, if we now define

bill :: Int
bill = 1

tall :: Int -> Bool
tall = \x -> x `elem` tl

someMan :: (Int -> Bool) -> Bool
someMan = flip any [1 .. 20]

allMan :: (Int -> Bool) -> Bool
allMan = flip all [1 .. 20]

we get

> bill `is` tall
True

> someMan `is` tall
True

> allMan `is` tall
False

Straightforwardly, with

are :: Copula l r => l -> r -> Sem l r
are = is

we can do

> someMan `are` tall
True

> allMan `are` tall
False

which may look a bit nicer.

Note: although this looks neat, in general, in polymorphic contexts the type checker needs quite some help figuring out what to do. For example

> [] `is` null

<interactive>:37:4:                                                              
    No instance for (Copula [a0] ([a1] -> Bool))
      arising from a use of `is'
    Possible fix:
      add an instance declaration for (Copula [a0] ([a1] -> Bool))
    In the expression: [] `is` null
    In an equation for `it': it = [] `is` null

while

> ([] :: [Int]) `is` (null :: [Int] -> Bool)
True