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

Matthew adnorm at gmail.com
Mon Jun 8 15:24:36 EDT 2009

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.


More information about the Haskell-Cafe mailing list