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