How do I define an Arrow instance for a Haskell binary tree GADT?

Question

I'm trying to use arrows to manipulate a generic binary tree in Haskell, and I'm running into issues actually instantiating the Arrow class. I think my issues are due to incompatible type signatures in the class, but if I can't instantiate, how could I mix arrow operators that work on trees with normal arrow operations in a function?

Here are my simple definitions, mostly lifted from the Haskell wiki (first won't compile, unsurprisingly, because its signature is a b c -> a (b, d) (c, d) and a Tree is not a tuple). first basically illustrates what I'd like to do:

data Tree a = Empty | Branch a (Tree a) (Tree a)
              deriving (Show, Eq)

newtype ArrowTree a b = ArrowTree {
  evaluate :: a -> b
}

instance Category ArrowTree where
  (ArrowTree f) . (ArrowTree g) = ArrowTree (f . g)
  id = arr id

instance Arrow ArrowTree where 
  arr f = ArrowTree f
  first = ArrowTree mapF
    where mapF g (Branch a l r) = Branch a (g l) r
          mapF g Empty = Empty

Any thoughts? I have a vision of using loop and a custom definition of *** to recursively operate on both sides of the tree independently. Thanks!

Answer 1

You say you want to use arrow operations on trees instead of on tuples. But it's not the tuple type that has the Arrow instance!

Providing an instance of the Arrow class wouldn't get you first :: (b -> c) -> Tree b -> Tree c, it would get you something like first :: Tree b c -> Tree (b, d) (c, d) (if Tree had two type parameters). If we consider the basic first :: (b -> c) -> (b, d) -> (c, d), the Arrow class isn't abstracting out the tuple and allowing you to generalise it, it's abstracting out the function arrows (hence the name Arrow). The tuples are still hardcoded. The generalisation lines up like this:

first :: (b  -> c) -> ((b, d)  -> (c, d))
first :: (b `a` c) -> ((b, d) `a` (c, d))

It's only the two inner function arrows that get replaced with the arrow type a, and that a is all you can replace with your own type in your particular instance. You can't replace the tuples with Trees, no matter what instance you use.

An Arrow needs to have 2 type parameters, and you should be able to conceptually think of it as representing something that "goes from one type to another" in some (possibly quite abstract) fashion. Your tree type doesn't look like an Arrow at all; it has one type parameter, and it just contains values of that type. It doesn't contain any way of going from that type to some other type.

Your ArrowTree does have 2 type parameters a and b, and what it contains is an a -> b function so obviously it supports the notion of "going from a to b". But since it is exactly the same as a normal function, it's going to be an Arrow in the same way as a normal function is. That's not really going to help you use operations like first and *** on trees instead of tuples.

If you want to lift ordinary functions onto trees in a similar manner that arrow operations can lift ordinary functions onto tuples, then it sounds like you don't actually want a custom Arrow instance at all. You don't want custom "functions", you want normal functions applied to trees. So if Arrow is going to help you at all, it would be by using the ordinary function instance of Arrow to implement new functions (not as part of any type class) that lift functions onto trees.