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
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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe