I have encountered a structure that looks like a monad with a one-sided inverse and some additional properties. I am not sure which properties of this structure are essential and which are accidental, so I will follow a simple example in my description.

I have a base type a which consists of sorted strings (e.g "aacdee" but not "abca") and the monad M from a, which is just the List monad:M a is lists of sorted strings. This monad defines pure: a -> M a, fmap: (a -> a) -> M a -> M a and bind: (a -> M a) -> M a -> M a.

Now I define extract: M a -> a which takes a list of strings, concatenates them and sorts the result. This is a left inverse of pure, i.e. extract . pure = id on a, but not a right inverse.

I also want to define extend: (M a -> a) -> M a -> M a in such a way that extract . (extend f) = f for all f: M a -> a.

While it would be possible to define extend f = pure . f, I do not want to do this. For example, if f is the function that replaces each character with the next one in the alphabet, concatenates and sorts, I want extend f to just replace each character with the next. Similarly if f removes all “a”’s from the first string, all “b”’s from the second, etc.

For a less trivial example, take f as the function that takes the first string, then if the second string is longer than the first extends the first string with the last elements of the second and so on. For example, f ["ab", "c", "def"] = "abf". In this case I want extend f to just fiter each string leaving only the letters that will contribute to the result, in the example (extend f) ["ab", "c", "def"] = ["ab", "", "f"].

The idea behind all of this is that in M a one can have parallel optimization for many kinds of f, and I want to define extend f as an optimized implementation for many specific cases, falling back to extend f = pure f only in the unoptimized cases.

My extend will not satisfy the comonad axioms, but will at least satisfy the following conditions (or very similar ones, I am not completely sure about the associativity):

  • (extend f) . pure = pure . f . pure, i.e on a single string f and extend f are essentially the same,
  • extend (extract . (fmap h)) = fmap h, i.e. if g = extract . (fmap h) acts on each string separately, then extend g does the same,
  • (extend f) . (extend g) = extend (f . pure . g), i.e. associativity, or maybe a weaker form of it.

My question. Is this a well known structure? Does it have any peculiar interesting properties?


This site is temporarily in read only mode and not accepting new answers.

Browse other questions tagged .