[Haskell-cafe] Observations about foldM

[Edward Kmett]

It is associativity that is required, not commutativity (in addition to the
fact that the list is finite).

This is why Data.Foldable provides operations for monoids over containers.
Monoids just provide you with associativity and a unit, which lets you
reparenthesize the fold however you want.

See the monoids library or my slides from hac-phi for lots of (ab)uses of a
monoid's associativity.

http://comonad.com/reader/2009/hac-phi-slides/

-Edward Kmett

On Wed, Aug 19, 2009 at 10:32 AM, Eugene Kirpichov <ekirpichov at gmail.com>wrote:

> 2009/8/19 Dan Doel <dan.doel at gmail.com>:
> > On Wednesday 19 August 2009 12:14:24 am Jason McCarty wrote:
> >> Interestingly, foldM can also be written as a left fold. To see this,
> note
> >> that it is a theorem that foldr f z xs = foldl f z xs as long as f is
> >> associative and z is a unit for f.
> >
>
> This is not true: f has to be commutative, not associative.
>
> Consider matrix multiplication.
>
> > It must also be the case that xs is finite in length, because if it is
> > infinite, then 'foldl f z xs' is bottom, while 'foldr f z xs' needn't be.
> This
> > difference holds over into foldM implemented with each, where you can
> write
> > something like:
> >
> >  foldM (\f e -> if even e then Left (show e) else Right f) "no evens"
> [1..]
> >
> > and get an answer of 'Left "2"' with a foldr implementation, but bottom
> with a
> > foldl implementation.
> >
> > This potentially translates into its own performance concerns, because in
> such
> > monads, the computation can short-circuit upon finding a 'throw' when
> using
> > the foldr implementation, but with the foldl implementation, you have to
> do at
> > least a little shuffling of thunks for the entire list.
> >
> > -- Dan
> > _______________________________________________
> > Haskell-Cafe mailing list
> > Haskell-Cafe at haskell.org
> > http://www.haskell.org/mailman/listinfo/haskell-cafe
> >
>
>
>
> --
> Eugene Kirpichov
> Web IR developer, market.yandex.ru
>  _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20090819/96e5c54a/attachment.html