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.