How does this definition of ArrowLoop.loop work?

Question

The function instance for ArrowLoop contains

loop :: ((b,d) -> (c,d)) -> (b -> c)
loop f b = let (c,d) = f (b,d) in c

First I have a problem with the signature: How can we possibly get b -> c from (b,d) -> (c,d)? I mean, the c in the resulting tuple may depend on both elements of the input, how is it possible to "cut off" the influence of d?

Second I don't get how the let works here. Doesn't contain (c,d) = f (b,d) a cyclic definition for d? Where does d come from? To be honest, I'm surprised this is valid syntax, as it looks like we would kind of redefine d.

I mean in mathematics this would make kind of sense, e.g. f could be a complex function, but I would provide only the real part b, and I would need to chose the imaginary part d in a way that it doesn't change when I evaluate f (b,d), which would make it some kind of fixed point. But if this analogy holds, the let expression must somehow "search" for that fixed point for d (and there could be more than one). Which looks close to magic to me. Or do I think too complicated?

Answer 1

This works the same way the standard definition of fix works:

fix f = let x = f x in x

i.e., it's finding a fixed point in the exact same way fix does: recursively.

For instance, as a trivial example, consider loop (\((),xs) -> (xs, 1:xs)) (). This is just like fix (\xs -> 1:xs); we ignore our input, and use the d output (here xs) as our main output. The extra element in the tuple that loop has is just to contain the input parameter and output value, since arrows can't do currying. Consider how you'd define a factorial function with fix — you'd end up using currying, but when using arrows you'd use the extra parameter and output that loop gives you.

Basically, loop ties a knot, giving a arrow access to an auxiliary output of itself, just like fix ties a knot, giving a function access to its own output as an input.

Answer 2

"Search for the fixed point" is exactly what this does. This is Haskell's laziness in action. See more at Wikipedia.