[Haskell-cafe] Random question

[wren ng thornton]

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