I´m trying to understand haskell and I´m stuck with a "cannot construct the infinite type"-error

I want to implement "<*>" for my own data type, imitating the behaviour of a list.

My functioning code so far:

data List a = Nil | Cons a (List a) deriving Show

instance Functor (List) where
--  fmap :: (Functor f) => (a -> b) -> f a -> f b
    fmap f Nil = Nil
    fmap f (Cons a (b)) = Cons (f a) (fmap f b)

Now I´m trying to create an instance of 'Applicative List':

instance Applicative List where
    pure a = Cons a (Nil)
--  (<*>) :: f (a -> b) -> f a -> f b
    (Cons a (b)) <*> (Cons c (d)) = Cons (fmap a (Cons c (d))) (b <*> (Cons c (d)))
    (Nil) <*> _ = Nil
    _ <*> (Nil) = Nil

The goal is to define '<*>' so it simulates the behaviour of a List. Example:

 (fmap (*)) [5,6,3] <*> [0,2]
--> [0,10,0,12,0,6]

so it should create:

(fmap (*)) (Cons 5 (Cons 6 (Cons 3 (Nil)))) <*> (Cons 0 (Cons 2 (Nil)))
--> (Cons 0 (Cons 10 (Cons 0 (Cons 12 (Cons 0 (Cons 6 (Nil))))))))

but unfortunately I get a (to me) pretty unuseful error:

10-3.hs:14:65: error:
    * Occurs check: cannot construct the infinite type: b ~ List b
      Expected type: List (List b)
        Actual type: List b
    * In the second argument of `Cons', namely `(b <*> (Cons c (d)))'
      In the expression: Cons (fmap a (Cons c (d))) (b <*> (Cons c (d)))
      In an equation for `<*>':
          (Cons a (b)) <*> (Cons c (d))
            = Cons (fmap a (Cons c (d))) (b <*> (Cons c (d)))
    * Relevant bindings include
        b :: List (a -> b) (bound at 10-3.hs:14:14)
        a :: a -> b (bound at 10-3.hs:14:11)
        (<*>) :: List (a -> b) -> List a -> List b (bound at 10-3.hs:14:18)
   |
14 |     (Cons a (b)) <*> (Cons c (d)) = Cons (fmap a (Cons c (d))) (b <*> (Cons c (d)))
   |                                                                 ^^^^^^^^^^^^^^^^^^
Failed, no modules loaded.

I cant figure out why a List of Lists is expected (List (List b)) because the definition of my data type clearly states a normal List is required as the second parameter for Cons.

I hope someone can help me with this!

EDIT: Thank you this solved it. This might be off-topic now, but I was trying to copy the original syntax used for lists to solve it. Its defined in the Prelude Package as follows:

instance Applicative [] where
    {-# INLINE (<*>) #-}
    fs <*> xs = [f x | f <- fs, x <- xs]

As I couldn´t use the list comprehension, as for me not wanting to create an actual list (shure I could just convert it later on but I dont like that idea). I translated the syntactic sugar with lambdaBot and got this:

fs <*> xs = concatMap (\ f -> concatMap (\ x -> [f x]) xs) fs

Is there a way to do it like this or is this essentialy the equivalent to doing it with an append (helper)-function?

CodePudding user response：

In the offending line:

  (Cons a (b)) <*> (Cons c (d)) = Cons (fmap a (Cons c (d))) (b <*> (Cons c (d)))

The subexpression fmap a (Cons c (d)) has type List b and you are trying to Cons that onto (b <*> (Cons c (d))) which also has type List b. But remember that the type is Cons :: a -> List a -> List a. Note that the first element of Cons needs to be an element and the second element should be a list. So, the compiler assumes that your element type is itself List b and then it reports that it expects the second argument to have type List (List b).

To fix this, instead of using Cons you should write an append :: List a -> List a -> List a function and use that:

  (Cons a (b)) <*> (Cons c (d)) = append (fmap a (Cons c (d))) (b <*> (Cons c (d)))

Small note about syntax: you can make the code quite a bit cleaner like this:

  Cons f fs <*> xs = append (fmap f xs) (fs <*> xs)

Tips:

• Use suggestive names like f for functions, and add an s to the end for lists of something.
• Avoid redundant pattern matching (Cons c (d)) -> xs.
• Avoid redundant parentheses. In particular you never have to write parentheses around variables like (b) and (d).