"Tangible Functional Programming" -- icfp version

I just submitted the camera-ready version of "Tangible Functional Programming", for ICFP '07. I'm happy with this version. It's improved drastically since my first submission to ICFP '06, thanks to many helpful comments. I've also been recreating the implementation on top of DeepArrow, Phooey, and TV, in preparation for a software release. It's getting simpler, but it's not as simple as I want.

Implementing a type for partial values

(Edit 2008-01-14: updated formatting.)

In my previous post, I gave an interface for a type of "partial values" and invited implementations. Here's mine, which surprised me in its simplicity. The whole module is online.

The trick is to represent Partial a as a -> a, i.e., a way to selectively replace parts of a value. Typically the replaced parts are bottom/undefined. I want Partial a to be a monoid, and Data.Monoid provides an instance:

-- | The monoid of endomorphisms under composition.
newtype Endo a = Endo { appEndo :: a -> a }

instance Monoid (Endo a) where
 mempty = Endo id
 Endo f `mappend` Endo g = Endo (f . g)

So my definition is simply a synonym:

type Partial = Endo

Note that mempty and mappend do exactly what I want. mempty adds no information at all, while u `mappend` v adds (overrides) information with u and then with v.

The implementation of functions on Partial is trivial.

-- | Convenience for partial-manipulating functions
inPartial :: ((a->a) -> (a'->a')) -> (Partial a -> Partial a')
inPartial f = Endo . f . appEndo

valp :: c -> Partial c
valp c = Endo (const c)

pval :: Partial c -> c
pval (Endo f) = f undefined
unFst :: Partial a -> Partial (a,b)
unFst = inPartial first

unSnd :: Partial b -> Partial (a,b)
unSnd = inPartial second

unElt :: Functor f => Partial a -> Partial (f a)
unElt = inPartial fmap

I'm not sure I'll end up using the Partial type in Eros, but I like having it around. If you think of variations, extensions and/or other uses, please let me know.

A type for partial values

(Edit 2008-01-14: updated formatting.)

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.

(July 3 edit: tweaked some indentation.)