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
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
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.
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
extend fare essentially the same,
extend (extract . (fmap h)) = fmap h, i.e. if
g = extract . (fmap h)acts on each string separately, then
extend gdoes 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?