Implementation of `first` in Arrow library

Question

I don't understand the implementation of first in the library.

first seems to be defined recursively with *** -- I don't see when the recursion shall end!?

first :: a b c -> a (b,d) (c,d)
first = (*** id)

and

(***) :: a b c -> a b' c' -> a (b,b') (c,c')
f *** g = first f >>> arr swap >>> first g >>> arr swap
    where swap ~(x,y) = (y,x)

first f is (f *** id) which is (first f >>> arr swap >>> first id...) and the new first will be another (*** id) and so on...

Answer 1

You are correct, if you implement an arrow like this:

instance Arrow MyType where
    arr f = ...

and then try to use first or (***), you will get an infinite loop since the implementations refer to each other non-productively. However, defining the default methods this way allows you to instantiate Arrow as either

instance Arrow MyType where
    arr f = ...
    first t = ...

or

instance Arrow MyType where
    arr f = ...
    t *** t' = ...

whichever is more convenient/efficient (depending on what you care about), and the missing method will be defined automatically in terms of the one you did specify.

If we try to instantiate Arrow without giving an implementation of first or (***), we will get the following warning:

warning: [-Wmissing-methods]
• No explicit implementation for
    either ‘first’ or ‘***’
• In the instance declaration for ‘Arrow MyType’

This is because the source comes with a MINIMAL pragma:

{-# MINIMAL arr, (first | (***)) #-}

which tells the compiler that, even though defaults are supplied, an instance is not complete unless it specifies arr and one of first or (***). So the requirement is encoded and checked.

---

As for your comment:

Not necesseraly I can leave the default and then the recursion will take place by definition. specific implementation are not the question here...

You can't use methods of a typeclass without an instance. It's seldom even possible to try, because the types of methods always refer to the type, e.g.

class Arrow k where
    first :: k a b -> k (a,c) (b,c)
    ...

When you use first, you have to have a specific k in mind in order to use the result, e.g.

print $ first (arr id) (1,2)                -- using it at k ~ (->)
print =<< runKleisli (first (arr id)) (1,2) -- using it at Kleisli IO

At some point the type constraints of the program will pin k down to be something concrete, and that is the instance that is used. You can't use a class without an instance.

(And even in the cases where things line up in such a way that a specific instance is not determined, the classic example being

show . read :: String -> String

The compiler will just yell at you

• Ambiguous type variable ‘a0’ arising from a use of ‘read’
   prevents the constraint ‘(Read a0)’ from being solved.
   Probable fix: use a type annotation to specify what ‘a0’ should be.

No infinite recursion if the program doesn't compile!)