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

[Ryan Ingram]

You can write this in terms of comonads if you have this additional function:

] focus :: (Container w) => (a -> a) -> (w a -> w a)

with the idea that "focus" modifies the current "point" of the comonad
(the thing returned by extract) while leaving the rest alone.

] focus f w = something (f $ extract w)

For lists, this is easy:

> focus f (x:xs) = f x : xs

Then we can use comonadic "extend" to build the sublists:

> each :: (a -> a) -> [a] -> [[a]]
> each = extend . focus

However, I think each element of the result might be "focused" on the
wrong target; we may need to be able to re-focus the lists at the
beginning.  (I haven't tested this code...)

  -- ryan

On Mon, Jun 8, 2009 at 12:24 PM, Matthew<adnorm at gmail.com> 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
>