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.