fix vs. ArrowLoop

Question

Description of loop from Control.Arrow:

The loop operator expresses computations in which an output value is fed back as input, although the computation occurs only once. It underlies the rec value recursion construct in arrow notation.

Its source code, and its instantiation for (->):

class Arrow a => ArrowLoop a where
    loop :: a (b,d) (c,d) -> a b c

instance ArrowLoop (->) where
    loop f b = let (c,d) = f (b,d) in c

This immediately reminds me of fix, the fixpoint combinator:

fix :: (a -> a) -> a
fix f = let x = f x in x

So my question is:

1. Is it possible to implement that particular loop via fix?
2. How are their functionalities different?

Junto

Answer 1

1. Well, of course. Every recursive definition can be written with fix:

   loop f b = let (c, d) = f (b, d) in c
   loop f b = fst $ let (c, d) = f (b, d) in (c, d)
   loop f b = fst $ let x = f (b, d) in x
   loop f b = fst $ let x = f' x in x
     where f' (_, d) = f (b, d)
   loop f b = fst $ fix $ f . (b,) . snd
   

   And it works the other way around:

   fix f = loop (join (,) . f . snd) ()
   

2. The above should convince you that loop and fix are equivalently powerful when talking about (->). Why, then, if arrows are meant to generalize functions, is ArrowLoop not defined like so?

   class Arrow a => ArrowLoop a where
     fix :: a b b -> b
   

   Arrows also generalize the notion of "process": when Arrow a, a b c is a way to calculate a c from a b. If ArrowLoop was defined to directly generalize fix, then it would be severely crippled. fix would have to "execute" the process without any context and directly produce a value of type b, which means the "process" a b b cannot e.g. perform IO. Or, consider the arrow

   newtype LT i o = LT { runLT :: [i] -> [o] }
   

   You’d like it if fix would produce a [b] from a LT b b, but it doesn’t.

   loop is a way around these restrictions. It takes a process as argument and produces a process as result. In a sense, all the context associated with the first process can be survived in the second, which would not be possible if loop were more like fix.

   Note that I can implement an analogue of fix for ArrowLoops:

   -- resulting process ignores its input
   fix' :: ArrowLoop a -- taking an impl of loop as argument
        => a b b -> a u b
   fix' f = loop ((id &&& id) . f . arr snd)
   -- take off the outer application to () (application means (->), after all)
   -- and arrowify: join (,) = id &&& id; snd = arr snd; (Prelude..) = (Control.Category..)
   -- but the RHSs are more general
   

   But I don't believe

   loop' :: Arrow a => (forall x u. a x x -> a u x) -- taking an impl of fix' as argument
         -> a (b, d) (c, d) -> a b c
   

   is implementable, so we can’t base ArrowLoop on fix' either.

Sixtyfourmo

In the case of something like Kleisli IO, isn't mfix enough? – Keto

@Keto Yes, but there are arrows that are not based on monads (which is kind of the point of arrows) that can’t make do with fix. Further, as I was playing around writing this answer, I tried to implement loopy things in terms of fixy things and kept hitting vaguely ArrowApply-shaped roadblocks (and those are related to monads). So, I think that "a fixy thing is enough for arrow a" might even be equivalent to "a is a Kleisli arrow". We don’t want to be restricted to Kleisli arrows, so we need loop. – Sixtyfourmo

I just meant that your comment about purity being required was too strong. – Keto

@Keto I meant "pure" in the general sense of "without any context", not in the more specific sense of "not IO". I’ll see if I can reword it. – Sixtyfourmo

You say the process a b b can't perform IO, but that doesn't seem right. – Keto

@Keto I said the argument of the hypothetical fix, an a b b, would not be able to perform IO. This is true. In general, it isn’t. We’d like to keep it false even if ArrowLoop a, so ArrowLoop can’t be based on fix. – Sixtyfourmo

Oh, sorry, I mixed up fix with fix'. – Keto