[Haskell-cafe] Comonadic composition and the game "Doublets"

[Matthew]

Today, I was working on coding a solver for the game "doublets".
It's a word game where you transform the start word into the end
word one letter at a time (and the intermediate states must also
be valid words).  For example, one solution to ("warm", "cold") is

	["warm", "ward", "card", "cord", "cold"]

So, one of my first goals was to write a function that would generate
the possible words a given word could transition to.  Here's a simple
recursive implementation:

	transition :: [Char] -> [[Char]]
	transition [] = []
	transition (c:cs) = map (c:) (transition cs) ++ map (:cs) ['a'..'z']

For some reason, I find this formulation to be strangely unsatisfying.
It seems to me that this sort of computation -- i.e. modifying each
element of a container (but only one at a time) -- should be
expressible with some higher order function.  In a nutshell, what I'm
looking for would be a function, say "each" with this type.

	each :: (Container c) => (a -> a) -> c a -> c (c a)

I'm not particularly sure what Class to substitute for "Container".
Comonad seemed like a promising solution initially, and provides
the basis for my current implementation of the "doublets" solver.

The problem being that cobind (extend) takes a function of type (w a - 
 > a)
instead of (a -> a).  I suspect that there may be a clever way to write
"each" by using liftW in combination with .>>  or something like that,
but presently, I'm at a loss.

Has anyone else encountered this sort of abstraction before.  I'd love
to hear your ideas about what Classes "each" should support, and
how to implement it.


Matt