cannot construct the infinite type

Question

I want to use applicative function and tried as follow:

*ReaderExercise Control.Applicative> (+4) <*> (+3)

then got following error message:

<interactive>:51:11: error:
    * Occurs check: cannot construct the infinite type: a ~ a -> b
      Expected type: (a -> b) -> a
        Actual type: a -> a
    * In the second argument of `(<*>)', namely `(+ 3)'
      In the expression: (+ 4) <*> (+ 3)
      In an equation for `it': it = (+ 4) <*> (+ 3)
    * Relevant bindings include
        it :: (a -> b) -> b (bound at <interactive>:51:1)

What do I expect is a return function with one argument.
What does it mean an infinite type?

Answer 1

The error "Occurs check: cannot construct [an] infinite type" results when Haskell determines that a type variable (explicitly given by the programmer or implicitly introduced by Haskell) must satisfy a condition that implies it would need to be recursively defined in terms of itself in a way that would lead to an infinitely "deep" type (i.e., the type variable "occurs" in its own definition).

It normally results from either a typo or conceptual error on the part of the programmer related to confusing two different "levels of structure" in a program.

As a simple example, a list of ints (type [Int]) is a valid Haskell type, and so is a list of lists of ints ([[Int]]) or a list of lists of lists of lists of lists of ints ([[[[[Int]]]]]) but only a finite number of list levels are allowed. You can't have a list of lists of lists of lists of lists, etc. all the way down -- that would be an infinite type. If Haskell thinks you want it to construct such a type, it'll give you an "occurs check" error.

The following definition:

yuck (x:xs) = x == xs

gives this error for exactly this reason. Haskell knows from the left-hand side that yuck takes a list of some unknown element type a where variable x is the head of type a and variable xs is the tail of type [a]. From the RHS, the operator (==) forces x and xs to have the same type -- in other words, it implies the constraint a ~ [a] where the tilde indicates "type equality". No finite type (no type with a finite number of list levels) has this properties, only the invalid infinite type [[[[...forever...]]]] could allow you to remove the outer list level and still have the same type left over, so you get the error.

The issue here is that the programmer has confused two levels of structure: the list xs and an element x.

In your specific example, the reason for the error is similar, but harder to explain. The operator:

(<*>) :: (Applicative f) => f (a -> b) -> f a -> f b

takes two applicative actions with different underlying types: the left-hand side has type given by the applicative functor f applied to the underlying type a -> b; the right-hand side has type given by the same applicative functor f applied to the underlying type b.

You haven't told Haskell which applicative functor f you meant to use, so Haskell tries to infer it. Because the LHS has type:

(+4) :: (Num n) => n -> n

Haskell tries to match the type n -> n with f (a -> b). It may be clearer to write these types using the prefix form of the (->) type operator: Haskell is trying to match (->) n n with f ((->) a b) where f is an applicative functor.

Fortunately, there's an applicative functor instance for (->) t for any type t. So, Haskell reasons that the applicative functor you want is f = (->) n, and it successfully matches (->) n n = f n to f ((->) a b). This implies that n is equal to ((->) a b). Haskell then tries to match the types on the RHS, matching (->) n n = f n with (->) n a = f a. This works, and it implies that n is equal to a.

Now we have a problem. n is simultaneously equal to a -> b (from the LHS) and a (from the RHS). This implies creation of an infinite function type, something that looks like:

(((... forever ...)->b)->b)->b)->b

which is the only way you could remove an outer ...->b and be left with the same type. This is an impossible infinite type, so you get the error.

The underlying problem is that you've made a conceptual error. Given that you are working on a ReaderExample, I think you intended to use the (->) n applicative functor instance, so you and Haskell are in agreement on this point. In this context:

(+4) :: (Num n) -> n -> n

is a reader action that reads a number from the reader and adds four to it. Similarly (+3) is a reader action that reads a number from the reader and adds three to it.

However, (<*>) is an operator that takes a reader action on the LHS that reads from the reader to produce a function (not a number!) that is then applied to the result of using the RHS to read from the reader to produce a number. For example, if you defined:

multiplyByReader :: (Num n) -> n -> n -> n
multiplyByReader readerNum input = readerNum * input

then:

multiplyByReader <*> (+4)

or the simpler version:

(*) <*> (+4)

would make sense. The intended meaning would be: Construct a reader action that (1) uses the LHS to read a number from the reader to create a function that multiplies by the reader; and then (2) applies this function to the number that results from applying the RHS to the reader.

This would be equivalent to \r -> r * (r + 4), as you can see:

> ((*) <*> (+4)) 5   -- same a 5 * (5 + 4)
45
>

When you write (+3) <*> (+4), you're mixing up two different structural levels: the LHS reader yields a number but should instead yield a function that can be applied to a number.

My best guess is that you want to create a reader action that applies (+4) to the reader to get a number and then applies (+3) to that result. In this case, (+3) isn't a reader action; it's just a function you want to apply to the result of the reader action (+4), which is equivalent to fmapping over the reader action:

(+3) <$> (+4)

Of course, you could equivalently write it directly as:

(+3) . (+4)

Both are composite reader actions that add seven to the number read:

> ((+3) <$> (+4)) 5
12
> ((+3) . (+4)) 5
12
>