"Pattern-matching" on Products of Variants?

Help
#1

I’ve been experimenting lately with purescript-variants and I’m really excited about them. As I understand, polymorphic variants can be used similarly to sum types, but can be built upi n a compositional way, unlike sum types that must be completely defined and handled all at once.

With sum types I frequently find myself pattern matching on product of sums, so I can succinctly describe a function over a combination of multiple inputs, and have the compiler check that I have exhaustively handled all combinations. For example, here is a function that resolves dietary restrictions.

data DietSum
  = Kosher
  | Catholic
  | Vegetarian
  
data DaySum
  = Friday
  | NotFriday

data FoodSum
  = Pork
  | Chicken
  | Veggie

canEatSum :: FoodSum → DietSum → DaySum → Boolean

canEatSum Veggie  _          _      = true
canEatSum _       Vegetarian _      = false

canEatSum Pork    Kosher     _      = false
canEatSum _       Kosher     _      = true

canEatSum Pork    Catholic   Friday = false
canEatSum Chicken Catholic   Friday = false
canEatSum _       Catholic    _     = true

This is nice because

  1. I can succinctly describe the function as a series of pattern-match rules.
  2. The compiler will make sure that my rules exhaustively cover the entire space of combinations which helps me make sure I am not missing any rules. I try and avoid having a global default at the bottom like canEat _ _ _ = false for this reason.

I’m trying to accomplish something similar using variants, but I’m having trouble getting my code to compile in certain situations without providing a global default.

It’s quite straightforward to “pattern match” on a single variant.

type Diet = Variant
  ( "Kosher" :: Unit
  , "Catholic" :: Unit
  , "Vegetarian" :: Unit
  )

_Kosher     = SProxy :: SProxy "Kosher"
_Catholic   = SProxy :: SProxy "Catholic"
_Vegetarian = SProxy :: SProxy "Vegetarian"

type Day = Variant
  ( "Friday" :: Unit
  , "NotFriday" :: Unit
  )

_Friday    = SProxy :: SProxy "Friday"
_NotFriday = SProxy :: SProxy "NotFriday"

type Food = Variant
  ( "Veggie" :: Unit
  , "Chicken" :: Unit
  , "Pork" :: Unit
  )

_Pork = SProxy :: SProxy "Pork"
_Veggie = SProxy :: SProxy "Veggie"
_Chicken = SProxy :: SProxy "Chicken"

canEatChickenOnFriday =
  default true
    # on _Vegetarian (const false)
    # on _Catholic (const false)

And I’ve been able to make some progress pattern matching on a product of variants.

For example, I can get the equivalent of this

canEatPorkSum :: DietSum → DaySum → Boolean
canEatPorkSum Kosher     _      = false
canEatPorkSum Vegetarian _      = false
canEatPorkSum Catholic   Friday = false
canEatPorkSum Catholic   _      = true

quite straightforwardly

canEatPork :: Diet → Day → Boolean
canEatPork =
  case_
    # on _Kosher     (const (default false))
    # on _Vegetarian (const (default false))
    # on _Catholic   (const (default true
                               # on _Friday (const false)
                            )
                     )

Where I run into trouble is when I want to start putting wildcards in the first position instead of the second position.

What I can do is something like this:

canEatChicken :: Diet → Day → Boolean
canEatChicken =
  default (default true)
    # on _Vegetarian ( const ( default false ) )
    # flip
    # on _NotFriday  ( const ( default true  ) )
    # on _Friday     ( const ( default true # on _Catholic (const false)))
    # flip

which I judge to be the equivalent of

canEatChickenSum :: DietSum -> DaySum -> Boolean
canEatChickenSum Vegetarian _         = false
canEatChickenSum _          NotFriday = true
canEatChickenSum Catholic   Friday    = false
canEatChickenSum _          Friday    = true 
canEatChickenSum _          _         = true -- Unnecessary

Whereas I’d rather write something like

canEatChicken :: Diet → Day → Boolean
canEatChicken =
  case_
    # on _Vegetarian ( const ( default false ) )
    # flip
    # on _NotFriday  ( const ( default true  ) )
    # on _Friday     ( const ( default true # on _Catholic (const false)))
    # flip

But that won’t compile. I understand why – basically, doing
flip >>> on _Friday ... on _Catholic ... >>> flip only adds _Catholic to the cases handled within the ‘_Friday’ branch.

Anyway, I’m going to be searching github for usages to see if I can find something like this for inspiration, or otherwise I’m going to continue to experiment to find a way of doing what I want. I’ll post here if I figure something out, but if anybody else has some insight or advice about a good way to go about this or whether the sort of thing I’m trying to do is impossible, it would be much appreciated!

#2

The best answer I can provide right now is to look at how a case statement like that could be written by casing on one parameter at a time. It can always be done, though it will likely result in duplication of branches, and in a less aesthetic order (though with equivalent semantics).

If we take your original example:

canEatSum Veggie  _          _      = true
canEatSum _       Vegetarian _      = false

canEatSum Pork    Kosher     _      = false
canEatSum _       Kosher     _      = true

canEatSum Pork    Catholic   Friday = false
canEatSum Chicken Catholic   Friday = false
canEatSum _       Catholic    _     = true

You can turn it into

canEatSum food diet day =
  case food of
    Pork ->
      case diet of
        Vegetarian -> false
        Kosher -> false
        Catholic ->
          case day of
            Friday -> false
            _ -> true
        _ -> true
    Chicken ->
      case diet of
        Vegetarian -> false
        Catholic ->
          case day of
            Friday -> false
            _ -> true
        _ -> true
    _ -> true

Where we encode the exceptions, and all the defaults are true. We’ve had to duplicate the Catholic cases. We can encode this with variant:

canEatSum food diet day =
  default true
    # on _Pork pork
    # on _Chicken chicken
    $ food
  where
  pork _ =
    default true
      # on _Vegetarian (const false)
      # on _Kosher (const false)
      # on _Catholic meatCatholic)
      $ diet

  chicken _ =
    default true
      # on _Vegetarian (const false)
      # on _Catholic meatCatholic)
      $ diet

  meatCatholic _ =
    default true
      # on _Friday (const false)
      $ day

Or you can use onMatch to make it more terse.

canEatSum food diet day =
  food # onMatch { pork, chicken } _true
  where
  pork _ =
    diet # onMatch { vegetarian: _false, kosher: _false, catholic } _true

  chicken _ =
    diet # onMatch { vegetarian: _false, catholic } _true

  catholic _ =
    day # onMatch { friday: _false } _true

  _false _ = false
  _true  _ = true

It’s not perfect, because the language syntax allows you express it in a more maintainable way, but with variant it’s easy enough to pull out the redundant cases.