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

[Dan Weston]

Oops. Make that: "a list comprehension, which enumerates the product 
space *without* duplicates"!

Dan Weston wrote:
> 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
>>
>>
>