Some enlightenment on Haskell Arrows

[dmaze]

A while ago, I achieved some Zen around the Monad type in Haskell; I could loosely describe it as "a value, with some extra class-specific goop that gets passed around", and I could write a state-tracking monad and a list-reading monad from scratch. So far, so good.

But the state-tracking monad is kind of icky to write. Let's say the state is an integer counter, and you want a getCount function that returns the current count and increments the counter. For the basic return function that promotes a value to a monad, you need to preserve the current value of the counter, so it needs to be a hidden function parameter, which means your monad type is really a function type.

data CountMonad a = CountMonad (Int -> (a,Int))
instance Monad CountMonad where
  return x = CountMonad (\n -> (x,n))
  (CountMonad f) >>= g = CountMonad (\n -> let (x,n') = f n
                                               (CountMonad g') = g x
                                           in g' n')
getCount :: CountMonad Int
getCount = CountMonad (\n -> (n,n+1))

Reasoning out in particular the >>= operator is a pain. I think this is where arrows come in. Since they deal in functions and not in values, it's easy to say "my arrow is a function with an extra hidden parameter":

data CountArrow b c = CountArrow ((b,Int) -> (c,Int))
instance Arrow CountArrow where
  arr f = CountArrow (\(x,n) -> (f x,n))
  (CountArrow f1) >>> (CountArrow f2) = CountArrow (f2 . f1)
  first (CountArrow f) = CountArrow (\((x,y),n) -> let (x',n') = f (x,n)
                                                   in ((x',y),n))
getCount :: CountArrow ignored Int
getCount = CountArrow (\(_,n) -> (n,n+1))

Is that "better"? It's easier to read, certainly, but a lot harder to figure out what's going on under the hood. I can rationalize Monad operations in terms of Maybe. Modern GHC provides some syntactic sugar for dealing with arrows which looks useful if hard to figure out from the documentation, plus there are some libraries; but the libraries helpfully point out that since normal functions (b -> c) are instances of Arrow I can extend things like my counted arrow as wrappers on arbitrary arrows.

So I'm not sure I have "the Zen" of arrows yet. But I can at least answer "what's the point" which is getting somewhere.

Comments

[dmaze]

Rewriting this in terms of other arrows isn't too hard:

data (Arrow a) => CountArrow a b c = CountArrow (a (b,Int) (c,Int))

Mostly you can use the standard arr function to raise an arbitrary function into an arrow, but in particular implementing first requires using ghc's extended arrow syntax.

instance (Arrow a) => Arrow CountArrow a b c where
  arr f = ArrowCounted (arr (\(x,n) -> (f x,n)))
  (ArrowCounted f1) >>> (ArrowCounted f2) = ArrowCounted (f1 >>> f2)
  first (ArrowCounted f) =
    ArrowCounted (proc ((x,y),n) -> do (x',n') <- f -< (x,n)
                                       returnA -< ((x',y),n'))

In particular, it helps to read proc as "lambda", and the funky -< operator as appearing in between a function and its parameter; then this reads just like monadic "do" syntax.

(The other useful comment is that, having realized where the arrow could be useful at all, it's taken me a morning to come up with a couple of ways to write this class; the IO monad means that any Haskell work uses monads from day one and things like lists and Maybe are usefully monads, but it took years to actually get a handle on it.)

[kvarko.livejournal.com]

Hey, Haskell! I didn't know that you knew Haskell! I use it every day at work. It's one of the highlights of my job :)

Sorry I don't have time to read your email deeper and comment, but just wanted to say: Haskell! (Presumably, fredrickegerman will have something to say on this post.)

[dmaze]

...weren't you my 6.827 TA way back in the day? Haskell isn't actually part of my day job, but my recurring fascination with it gets me routinely mocked by my coworkers.