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

[Juan Casanova]

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.