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

[Dan Weston]

I think the structure you are looking for is called a "wedge sum" [1], 
which is the coproduct in the category of the pointed spaces, each of 
which is (in this case) the group action of changing one letter to 
another in the ith position of a word of fixed length.

One small tricky part is that, in contrast to the direct product of n 
1-D spaces with a list comprehension, which enumerates the product space 
with duplicates:

[(x,y,z,...) | x <- xs, y <- ys, z <- zs, ... ]

with a wedge sum a naive algorithm overcounts the point (or origin, in 
this case the identity function). This can be seen in your transition 
function, where non-identity transformations are counted only once, but 
the identity transformation is counted n times:

*Main> length . filter (== "abd") . transition $ "abc"
1
*Main> length . filter (== "abc") . transition $ "abc"
3

If you want your result to be a set, you may want to treat the identity 
transformation separately.

[1] http://en.wikipedia.org/wiki/Wedge_sum

Dan

Matthew wrote:
> 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
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
> 
>