scala - Extracting a constraint from a conjunction -

here's tree of boolean predicates.

data pred = leaf (a -> bool)             | , (pred a) (pred a)             | or (pred a) (pred a)             | not (pred a)  eval :: pred -> -> bool eval (leaf f) = f eval (l `and` r) = \x -> eval l x && eval r x eval (l `or` r) = \x -> eval l x || eval r x eval (not p) = not . eval p 

this implementation simple, problem predicates of different types don't compose. toy example blogging system:

data user = u {     isactive :: bool } data post = p {     ispublic :: bool }  userisactive :: pred user userisactive = leaf isactive  postispublic :: pred post postispublic = leaf ispublic  -- doesn't compile because , requires predicates on same type -- usercancomment = userisactive `and` postispublic 

you around defining data world = w user post, , exclusively using pred world. however, adding new entity system necessitates changing world; , smaller predicates don't require whole thing (postispublic doesn't need use user); client code that's in context without post lying around can't use pred world.

---

it works charm in scala, happily infer subtype constraints of composed traits unification:

sealed trait pred[-a] case class leaf[a](f : => boolean) extends pred[a] case class and[a](l : pred[a], r : pred[a]) extends pred[a] case class or[a](l : pred[a], r : pred[a]) extends pred[a] case class not[a](p : pred[a]) extends pred[a]  def eval[a](p : pred[a], x : a) : boolean = {   p match {     case leaf(f) => f(x)     case and(l, r) => eval(l, x) && eval(r, x)     case or(l, r) => eval(l, x) || eval(r, x)     case not(pred) => ! eval(pred, x)   } }  class user(val isactive : boolean) class post(val ispublic : boolean)  trait hasuser {   val user : user } trait haspost {   val post : post }  val userisactive = leaf[hasuser](x => x.user.isactive) val postispublic = leaf[haspost](x => x.post.ispublic) val usercancommentonpost = and(userisactive, postispublic)  // type inferred and[hasuser haspost] 

(this works because pred declared contravariant - anyway.) when need eval pred, can compose required traits anonymous subclass - new hasuser haspost { val user = new user(true); val post = new post(false); }

---

i figured translate haskell turning traits classes , parameterising pred type classes requires, rather concrete type operates on.

-- conjunction of partially-applied constraints -- (/\) :: (k -> constraint) -> (k -> constraint) -> (k -> constraint) type family (/\) c1 c2 :: constraint     (/\) c1 c2 = (c1 a, c2 a)  data pred c     leaf :: (forall a. c => -> bool) -> pred c     , :: pred c1 -> pred c2 -> pred (c1 /\ c2)     or :: pred c1 -> pred c2 -> pred (c1 /\ c2)     not :: pred c -> pred c  data user = u {     isactive :: bool } data post = p {     ispublic :: bool }  class hasuser     user :: -> user class haspost     post :: -> post  userisactive :: pred hasuser userisactive = leaf (isactive . user)  postispublic :: pred haspost postispublic = leaf (ispublic . post)  usercancomment = userisactive `and` postispublic -- ghci> :t usercancomment -- usercancomment :: pred (hasuser /\ haspost) 

the idea each time use leaf define requirement (such hasuser) on type of whole without specifying type directly. other constructors of tree bubble requirements upwards (using constraint conjuction /\), root of tree knows of requirements of leaves. then, when want eval predicate, can make type containing data predicate needs (or use tuples) , make instance of required classes.

however, can't figure out how write eval:

eval :: c => pred c -> -> bool eval (leaf f) = f eval (l `and` r) = \x -> eval l x && eval r x eval (l `or` r) = \x -> eval l x || eval r x eval (not p) = not . eval p 

it's and , or cases go wrong. ghc seems unwilling expand /\ in recursive calls:

could not deduce (c1 a) arising use of ‘eval’ context (c a)   bound type signature              eval :: (c a) => pred c -> -> bool   @ spec.hs:55:9-34 or (c ~ (c1 /\ c2))   bound pattern constructor              , :: forall (c1 :: * -> constraint) (c2 :: * -> constraint).                     pred c1 -> pred c2 -> pred (c1 /\ c2),            in equation ‘eval’   @ spec.hs:57:7-15 relevant bindings include   x :: (bound @ spec.hs:57:21)   l :: pred c1 (bound @ spec.hs:57:7)   eval :: pred c -> -> bool (bound @ spec.hs:56:1) in first argument of ‘(&&)’, namely ‘eval l x’ in expression: eval l x && eval r x in expression: \ x -> eval l x && eval r x 

ghc knows c a , c ~ (c1 /\ c2) (and therefore (c1 /\ c2) a) can't deduce c1 a, require expanding definition of /\. have feeling work if /\ type synonym, not family, haskell doesn't permit partial application of type synonyms (which required in definition of pred).

---

i attempted patch using constraints:

conjl :: (c1 /\ c2) :- c1 conjl = sub dict conjr :: (c1 /\ c2) :- c1 conjr = sub dict  eval :: c => pred c -> -> bool eval (leaf f) = f eval (l `and` r) = \x -> (eval l x \\ conjl) && (eval r x \\ conjr) eval (l `or` r) = \x -> (eval l x \\ conjl) || (eval r x \\ conjr) eval (not p) = not . eval p 

not only...

could not deduce (c3 a) arising use of ‘eval’ context (c a)   bound type signature              eval :: (c a) => pred c -> -> bool   @ spec.hs:57:9-34 or (c ~ (c3 /\ c4))   bound pattern constructor              , :: forall (c1 :: * -> constraint) (c2 :: * -> constraint).                     pred c1 -> pred c2 -> pred (c1 /\ c2),            in equation ‘eval’   @ spec.hs:59:7-15 or (c10 a0)   bound type expected context: (c10 a0) => bool   @ spec.hs:59:27-43 relevant bindings include   x :: (bound @ spec.hs:59:21)   l :: pred c3 (bound @ spec.hs:59:7)   eval :: pred c -> -> bool (bound @ spec.hs:58:1) in first argument of ‘(\\)’, namely ‘eval l x’ in first argument of ‘(&&)’, namely ‘(eval l x \\ conjl)’ in expression: (eval l x \\ conjl) && (eval r x \\ conjr) 

but also...

could not deduce (c10 a0, c20 a0) arising use of ‘\\’ context (c a)   bound type signature              eval :: (c a) => pred c -> -> bool   @ spec.hs:57:9-34 or (c ~ (c3 /\ c4))   bound pattern constructor              , :: forall (c1 :: * -> constraint) (c2 :: * -> constraint).                     pred c1 -> pred c2 -> pred (c1 /\ c2),            in equation ‘eval’   @ spec.hs:59:7-15 in first argument of ‘(&&)’, namely ‘(eval l x \\ conjl)’ in expression: (eval l x \\ conjl) && (eval r x \\ conjr) in expression:   \ x -> (eval l x \\ conjl) && (eval r x \\ conjr) 

it's more or less same story, except ghc seems unwilling unify variables brought in gadt required conjl. looks this time /\ in type of conjl has been expanded (c10 a0, c20 a0). (i think because /\ appears fully-applied in conjl, not in curried form in and.)

needless say, it's surprising me scala better haskell. how can fiddle body of eval until typechecks? can cajole ghc expanding /\? going wrong way? want possible?

the data constructors and :: pred c1 -> pred c2 -> pred (c1 /\ c2) , or :: ... not formed because type families cannot partially applied. however, ghc earlier 7.10 erroneously accept definition - give errors see when try it.

you should use class instead of type family; example

class (c1 a, c2 a) => (/\) (c1 :: k -> constraint) (c2 :: k -> constraint) (a :: k) instance (c1 a, c2 a) => (c1 /\ c2)  

and straightforward implementation of eval work.