2

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...

Will Ness
  • 70,110
  • 9
  • 98
  • 181
user3680029
  • 179
  • 8
  • Hint: `(>>>) = flip (.)`. Note that `(>>>)` is here the "outer" function. Due to laziness it is not said that the operands are evaluated. – Willem Van Onsem Sep 01 '19 at 08:39
  • 6
    I may be missing something, but having checked the [documentation](http://hackage.haskell.org/package/base-4.12.0.0/docs/Control-Arrow.html#t:Arrow), the minimal complete definition of the `Arrow` class requires `arr` and either one of `first` and `(***)`. So these definitions aren't truly recursive, they just define either method in terms of the other. It's just like the two defining methods of the `Eq` class, or `traverse` and `sequenceA` in `Traversable`. You have to give the definition of one method, then the other is provided for you. – Robin Zigmond Sep 01 '19 at 09:17
  • I would be happy to give the above as an answer, but I know @WillemVanOnsem is far more knowledgeable than me, and his comment has me thinking there must be something else I'm missing – Robin Zigmond Sep 01 '19 at 09:19
  • 1
    it's not implementation, but *default* definition. see [comment](https://stackoverflow.com/questions/57744404/arrow-first-implementation-in-arrow-lib#comment101927621_57744404) by @RobinZigmond. – Will Ness Sep 01 '19 at 09:24
  • Willem, you mean that an 'evaluation' of (>>>) (?) will force to stop the recursion at the 'first level'? Because id is determined at the first-level of evaluation (what I mean is that Haskell doesn't need to 'dig' further to have a evaluable expression and it stops the recursion) – user3680029 Sep 01 '19 at 11:50
  • 3
    @user3680029 look at any instance definition, there will be an implementation for (at least) one of the functions and so no infinite recursion. Those are default definitions so that you don't need to write out all the functions if they can be implemented in terms of each other - you write one and get the others for free. – moonGoose Sep 01 '19 at 13:20
  • But nevertheless the default implementation looks recursive. I wouldn't have this problem if first was defined as \f (x,y) -> (f x,y) (first specialised to function) it's a stand alone definition w/o any (****) [less polymorphic as Id is a method of the Category Class from which functions are also instances..] – user3680029 Sep 01 '19 at 19:12
  • But any valid instance will have either `first` or `(***)` defined in a way that doesn't depend on the other, just as you observe the instance for `(->)` has. – Robin Zigmond Sep 01 '19 at 20:06
  • Not necesseraly I can leave the default and then the recursion will take place by definition. specific implementation are not the question here... – user3680029 Sep 01 '19 at 21:49
  • 2
    Sure, but it's clearly not *intended* for neither of these methods to be given implementations in an instance - precisely because you then indeed run into recursion. As i said earlier, try defining an `Eq` instance without implementing either `(==)` or `(/=)` - that's clearly not what's intended, but is totally analogous to what you are suggesting here, as each has a default implementation in terms of the other. – Robin Zigmond Sep 01 '19 at 22:42
  • Yes.... but as far as I can see (in hackage) Eq hasn't a default implementation... thanks to the cross reference I have to define only one method (==) or (/=) – user3680029 Sep 02 '19 at 04:39
  • Sorry on Wiki they are telling that Eq has a definition of (==) and (/=) in terms of each other. With the same reasoning we can imagine a infinite recursion of the type (==) = not (not (not .... (/=...(... . But here may be because it's more intuitive the recursion 'naturally' broke at the first step (/=) is simply not (==) and not an infinite thunk of not(not(... coming back to Willem comment may here laziness is more easy to grasp in this scenario.... – user3680029 Sep 02 '19 at 05:17
  • 2
    @user3680029 go by the answer. the answer is good. ignore anything that contradicts it. the "implementations" you refer to are not implementations, they are default definitions that are used in case there's no implementation. but there must be *some* implementation given, and the infinite recursion *will* be broken because when the implementation is given by the user, *it* is used by Haskell, *not* the default definition that is used *only* when there is no implementation for that method. in Eq as in Arrow as well. a given type's instance must implement *some* method(s), if not all of them. – Will Ness Sep 02 '19 at 12:08

1 Answers1

3

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!)

luqui
  • 59,485
  • 12
  • 145
  • 204
  • Ok. Perfect I understand it was tedious but I can accept that I can have here a "virtual" recursion due to that each time the specific implementation will eliminate the recursive pattern... nevertheless I will create an arrow datatype and check all of this (with an implementation of first and with leaving the default one). Thank you all for your help . – user3680029 Sep 02 '19 at 12:29