[Haskell-cafe] Random question
wren ng thornton
wren at freegeek.org
Thu Sep 25 20:27:16 EDT 2008
Iain Barnett wrote:
> On 24 Sep 2008, at 10:13 pm, Evan Laforge wrote:
> > For one approach, check
> > out 'replicate' to make copies of something, and then 'sequence' to
> > run them and return a list.
> >
>
> Thanks, I haven't found anything that explains 'sequence' well yet, but
> I'll keep looking.
Yet another explanation that might be helpful...
Consider a functor as a container (hence an |F a| value is an F-shaped
container of values of type |a|). And remember that every monad is also
a functor. We could imagine a value of type |F (G a)|, that is, a big
F-shaped box containing many G-shaped boxes each containing a's. When G
is a monad and not just a plain old functor, values of this sort are
rather irksome to deal with because of the side effects.
But, if the functor F has certain properties[1] then it is possible to
have a function that takes an |F (G a)| and distributes F over G to
yield an analogous |G (F a)| value that preserves the internal
structures of F and G. This function essentially runs a string through
all the little |G a| beads in order to run them in some canonical
sequence[2], it then collects their results and wraps them up in
F-shaped boxes.
One of the places such a function is helpful is this. Consider if you
have an |F a| value and you then fmap a monadic function |a -> G b| over
it. You now have an |F (G b)| but no simple way to get back what you
really want: an |F b| value. If you have a function to distribute the
functors then you can get a |G (F b)| which is a program that computes
an |F b| subject to the state in G which it threads through each of
those calls to that monadic function we fmapped over the |F a|.
The |sequence| function from the Prelude is exactly such a function,
except that it fixes F to be [ ] and is only polymorphic over G and a.
We could in principle have a more general function that doesn't force
you to use lists. In fact, it exists as Data.Traversable.sequenceA which
allows F to be any Data.Traversable structure and allows G to be any
applicative functor (which are halfway between functors and monads).
[1] Namely being Data.Foldable and Data.Traversable so that we can,
respectively, consume and reconstruct F containers. It's these
mathematical properties we need, not the type classes themselves.
Alternatively, if we can define for |f| a function |fsequence :: (Monad
m) => f (m a) -> m (f a)| then we can use that function to define
instances for both of those type classes; this is what
Data.Traversable's fmapDefault and foldMapDefault functions are about.
[2] What sequence this threading occurs in matches whatever order the
folding function iterates over the elements in the F functor.
--
Live well,
~wren
More information about the Haskell-Cafe
mailing list