[Haskell-cafe] Foldable, Traversable and choosing an order

[Alejandro Serrano Mena]

Hi,
Your choice of Traversable must already give you an answer to that
question. In fact, if you could implement `Traversable` you can get
`Foldable` for free by using `foldMapDefault` [
http://hackage.haskell.org/package/base-4.12.0.0/docs/Data-Traversable.html#v:foldMapDefault].
Then you know that both instances "agree" on their behavior.

Regards,
Alejandro

El lun., 23 sept. 2019 a las 21:06, Juan Casanova (<juan.casanova at ed.ac.uk>)
escribió:

> Hello again, haskell-cafe.
>
> I was trying to implement the Unifiable typeclass from
> Control.Unification on one of my types, and did so fine, but then
> realized I needed a Traversable instance.
>
> So I thought about it, and concluded: Yes, my type definitely is
> Traversable, and I implemented Traversable. But then I realized I
> needed a Foldable instance for that.
>
> And then I wasn't so sure anymore. I *can* implement a Foldable
> instance, but it requires a choice of the order in which my structure
> is traversed that I don't really want to make? A.k.a: I can think of
> at least two different ways of implementing Foldable that would give
> different results if the function passed to foldr was not associative.
>
> So I looked online a bit, and it seems this is a topic people have
> talked about, but maybe not precisely in the context of the order.
> What I have gathered is that: yes, if a functor is Traversable, then
> there is at least one way to implement a Foldable in it. And I
> understand this, but then, I don't really grasp how that works in my
> specific case. Because my Traversable instance does not make a choice
> of this order (at least I think so), and I do need to make that choice
> to implement Foldable (at least I think so), and I don't see how the
> "default" implementation of foldMap in terms of traverse makes that
> choice. But the choice must be made somewhere if it is made in the
> Foldable. So what is going on?
>
> Of course, here's the code. My types:
>
> data SOTermPF fn p f = ConstF fn | Proj Int | CompF p [f] deriving Eq
> newtype SOTermF fn f = SOF (SOTermPF fn f f) deriving Eq
>
> My Traversable instance (with comments on intermediate types because
> otherwise it can get pretty obscure):
>
> instance Traversable (SOTermF fn) where
>         traverse f (SOF (ConstF c)) = pure (SOF (ConstF c))
>         traverse f (SOF (Proj idx)) = pure (SOF (Proj idx))
>         -- f g :: f b
>         -- map f sargs = [f b]
>         -- CompF :: a -> ([a] -> SOTermPF fn p a)
>         -- (\h -> \ts -> SOF (CompF h ts)) :: ([a] -> SOTermF fn a)
>         -- fmap (\h -> \ts -> SOF (CompF h ts)) (f g) :: f ([b] -> SOTermF
> fn b)
>         -- traverse :: (aa -> ff bb) -> [aa] -> ff [bb]
>         -- traverse :: (f b -> f b) -> [f b] -> f [b]
>         -- ((fmap (\h -> \ts -> SOF (CompF h ts)) (f g)) <*>) :: f [b] ->
> f
> (SOTermF fn b)
>         -- traverse id (map f sargs) :: f [b]
>         -- (fmap (\h -> \ts -> SOF (CompF h ts)) (f g)) <*> (traverse id
> (map
> f sargs)) :: f (SOTermF fn b)
>         traverse f (SOF (CompF g sargs)) = (fmap (\h -> \ts -> SOF (CompF
> h
> ts)) (f g)) <*> (traverse id (map f sargs))
>
> But to implement Foldable I need to choose an order because in the
> case where I do have elements under the functor (CompF), I have them
> in two shapes: The "head" and the "arguments" (the p and the [f] in
> CompF p [f]). So, of course, the arguments are traversed in the order
> of the list, but the order that I need to choose is: Do I apply the
> head first and the arguments later or do I apply the arguments first
> and the head later? But my traverse seems so natural. Am I making that
> choice there? Maybe if I made the fmap over the arguments (while
> traversing the list) instead of over the head, and then did a flipped
> application of <*>? Does that mean my traverse instance has implicitly
> assumed that the head will be done first?
>
> All of this is really out of curiosity and making sure I know what I'm
> doing: I will not use foldr on my structure and I'm pretty sure that
> the traversal that Control.Unification needs is associative. But I
> don't like seeing arbitrary choices appear out of nowhere in my code,
> I want to make sure of why I made them. :P
>
> Thanks in advance,
> Juan.
>
>
>
> --
> The University of Edinburgh is a charitable body, registered in
> Scotland, with registration number SC005336.
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> To (un)subscribe, modify options or view archives go to:
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
> Only members subscribed via the mailman list are allowed to post.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20190924/87fabe4f/attachment.html>