CODEWITHSUNDEEP
haskelltypescompiler-errorsfold
Yaokun Xu
Yaokun Xu

Reputation: 74

Occurs check: cannot construct the infinite type

The task I want to handle is described as below:

pipe [f1,...,fn] x should return f1(f2(...(fn x)))

Here is my code:

pipe :: [(a -> a)] -> (a -> a)
pipe fs   = foldl' f base fs
  where
    f a x = a (x)
    base  = (\x -> x)

I think this makes sense as it iterates through the function list, however, the compiler tells me:

tutorial.hs:45:20: error:
    • Occurs check: cannot construct the infinite type: a ~ a -> a
      Expected type: (a -> a) -> (a -> a) -> a -> a
      Actual type: ((a -> a) -> a -> a) -> (a -> a) -> a -> a
    • In the first argument of ‘foldl'’, namely ‘f’
      In the expression: foldl' f base fs
      In an equation for ‘pipe’:
         pipe fs
            = foldl' f base fs
            where
                f a x = a (x)
                base = (\ x -> x)
    • Relevant bindings include
        fs :: [a -> a] (bound at tutorial.hs:45:6)
        pipe :: [a -> a] -> a -> a (bound at tutorial.hs:45:1)
   |
45 | pipe fs   = foldl' f base fs
   |                    ^
Failed, no modules loaded.

I am a newcomer to Haskell, and Thanks for your help in advance:)

Upvotes: 1

Views: 451

Answers (2)

Yuan Wang
Yuan Wang

Reputation: 479

You could do

pipe :: [a -> a] -> (a -> a)
pipe = foldr (flip (.)) id

There is a difference between foldr and foldl.

Your base function is equivalent to id.

In your version, the definition of f is incorrect. It should take two functions and return a new function.

You could write it as

pipe :: [(a -> a)] -> (a -> a)
pipe fs   = foldl f id fs
  where
    f g h = g . h
    base  = (\x -> x)

or 

pipe :: [(a -> a)] -> (a -> a)
pipe fs   = foldl f id fs
  where
    f g h a = h (g a)
    base  = (\x -> x)

If all functions are commutative, using foldr or foldl makes no difference, otherwise you need to choose foldr or foldl correctly.

Upvotes: 1

chi
chi

Reputation: 116139

I'll explain why your code is not working. Let's compute pipe [g,h] x. We expect this to be g(h x).

I will ignore the types, and simply compute according to the definitions:

pipe [g,h] x
= foldl' f base [g,h] x
= foldl' f (f base g) [h] x
= foldl' f (f (f base g) h) [] x
= f (f base g) h x
= (f base g) h x
= base g h x
= g h x

So, in the last line we can see that g is called with two arguments, h and x, while we expected to have g (h x) instead.

The mistake is that f uses application f a x = a x instead of composition f a x = a . x. Using the latter we would get

... 
= ((base . g) . h) x
= base (g (h x))
= g (h x)

Upvotes: 0

Related Questions