### Re: foldr (.) id

wren ng thornton <wren <at> freegeek.org>

2012-10-28 01:34:17 GMT

On 10/26/12 2:41 PM, Greg Fitzgerald wrote:
> Hi Haskellers,
>
> I've recently found myself using the expression: "foldr (.) id" to compose
> a list (or Foldable) of functions. It's especially useful when I need to
> map a function over the list before composing. Does this function, or the
> more general "foldr fmap id", defined in a library anywhere? I googled and
> hoogled, but no luck so far.
While the prelude's (.) just so happens to be an fmap, that most
emphatically does not mean fmap is "the" generalization of (.). In fact,
fmap is almost never a helpful generalization of (.). The only time it
would be helpful is if you're already explicitly depending on the fact
that (e->) happens to be a functor, in which case your use of (.) was
simply a specialization of fmap in the first place! Removing a
specialization and adding a generalization aren't the same process. And
the fact that id is showing up here should set off warning bells that
the (.) you're dealing with comes from the category structure, not the
functor structure.
It so happens that endomorphisms form a monoid with id, hence the Endo
suggested by other folks. However, Endo is just the restriction of
general categories to single-object categories (aka monoids). So you
could go with the monoid generalization, in which case what you want is
mconcat, which is equal to foldr mappend mempty but may be implemented
more efficiently for some monoids. Or, if you're trying to be general
then you should go with the category generalization, in which case what
you want is foldr (.) id--- using the Category definitions rather than
the Prelude. Unfortunately, the full generality of foldr (.) id cannot
be easily realized in Haskell since the remaining argument is a list
rather than something more general like the reflexive transitive closure
of a relation. In a pseudo-Haskell with full dependent types we'd say:
kind Relation a = a -> a -> *
data RTC (a :: *) (r :: Relation a) :: Relation a where
Nil :: forall x::a. RTC a r x x
Cons :: forall x y z::a. r x y -> RTC a r y z -> RTC a r x z
paraRTC :: forall (a :: *) (r p :: Relation a).
(forall x :: a, p x x) ->
(forall x y z :: a. r x y -> RTC a r y z -> p y z -> p x z) ->
forall x z :: a. RTC a r x z -> p x z
-- aka foldrRTC. The only difference is that the second function
-- argument doesn't get a copy of <at> RTC a r y z <at> .
cataRTC :: forall (a :: *) (r p :: Relation a).
(forall x :: a, p x x) ->
(forall x y z :: a. r x y -> p y z -> p x z) ->
forall x z :: a. RTC a r x z -> p x z
class Category (r :: Relation *) where
id :: forall a. r a a
(.) :: forall a b c. r b c -> r a b -> r a c
-- Ideally the first three arguments should be passed implicitly
cataRTC * (->) (~>) (.) id :: forall a b. RTC * (->) a b -> a ~> b
--
--
Live well,
~wren