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