[Haskell-cafe] Comonadic composition and the game "Doublets"
Dan Weston
westondan at imageworks.com
Mon Jun 8 18:19:09 EDT 2009
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
>>
>>
>
More information about the Haskell-Cafe
mailing list