A type for partial values

In simplifying my Eros implementation, I came across a use for a type that represents partial information about values. I came up with a very simple implementation, though perhaps not quite ideal. In this post, I’ll present the interface and invite ideas for implementation. In the next post, I’ll give the implementation I use.

First the type:

type Partial a

I require that Partial a be a monoid, for which mempty is the completely undefined value, and in u `mappend` v, v selectively replaces parts of u. (Lattice-wise, mempty is bottom, and mappend is not quite lub, as it lacks commutativity).

Now the programming interface:

-- Treat a full value as a partial one.  Fully overrides any "previous" (earlier
-- argument to mappend) partial value.
valp :: c -> Partial c

-- Force a partial value into a full one, filling in bottom for any missing parts.
pval :: Partial c -> c

-- Inverse to fst, on partial values.  Inject info into the the first half of a pair,
-- and leave the second half alone.
unFst :: Partial a -> Partial (a,b)

-- Inverse to snd.
unSnd :: Partial b -> Partial (a,b)

-- Inverse to "element" access, on all elements.  A way to inject some info about every
-- element.  For f, consider [], (->) a, Event, etc.
unElt :: Functor f => Partial a -> Partial (f a)

That’s it. I’d love to hear ideas for representing Partial a and implementing the functions above. In the next post, I’ll give mine.

4 Comments

  1. augustss:

    What does mappend do when given two arguments with conflicting information? What does it do when given equal information? And how does it know that they are equal?

  2. Conal:

    The second argument wins. mappend doesn’t care whether information gets lost from the first argument, so it doesn’t have to check for conflicts. That’s how mappend disagrees with lub, and in this sense, perhaps my Partial is less than ideal.

  3. Conal Elliott » Blog Archive » Implementing a type for partial values:

    […] « A type for partial values "Tangible Functional Programming" — icfp version […]

  4. Conal Elliott » Blog Archive » Merging partial values:

    […] a simple representation for partial information about values, and wrote about it in two posts, A type for partial values and Implementing a type for partial values. Of particular interest is the ability to combine two […]

Leave a comment