Why can't I use 'isJust' in the lambda function in `foldr`?

user_16196566 0
Viewed 154

I am currently writing an interpreter in haskell for a primitive programming language. I am trying to see if the current program being analysed is correctly Typed before interpreting. Basically what I end up with is a list called maybeList that holds maps of the initialised variables if they are correct, or Nothings if they don't, like this:

[Maybe [(k,v)]]

I am trying to fold over this list with this function

foldr (\x y -> (isJust x) && (isJust y)) True maybeList

From what I understand about Haskell and the foldr function, this should work. However, it gives me the error:

Couldn't match expected type ‘Bool’ with actual type ‘Maybe a0’ 
In the expression:

 foldr (\ x y -> (isJust x) && (isJust y)) True maybeList

What I'm asking is why doesn't the compiler know that the isJust function returns a boolean, it keeps treating it as a Maybe a0 type?

P.S. I understand that a simple elem Nothing maybeList will work in place of this. But I would like to understand why this doesn't work

type-mismatch fold haskell
5 Answers

The reducing function for foldr takes as second argument something of the same type as the initial element:

foldr (\x y -> (isJust x) && (isJust y)) True maybeList
--        \_______________________________/    
--                         |
--          these two must be the same type

So y is of type Bool but you are considering it of type Maybe a.

Therefore, foldr (\x y -> (isJust x) && y) True maybeList is the right solution.

user_92712660

A foldr takes as second parameter the accumulator. Indeed, the type of foldr is:

foldr :: Foldable f => (a -> b -> b) -> b -> f a -> b

Here b is the type of the accumulator that goes conceptually from right-to-left, whereas a are the items of the list.

Since you work with True in foldr (\x y -> isJust x && isJust y) True, this thus means that the accumulator, and hence y also is of type Bool.

We can implement this with:

foldr (\x y -> isJust x && y) True maybeList

We however do not need foldr here. What you here determine is whether all the items are a Just …. We can thus work with all :: Foldable f => (a -> Bool) -> f a -> Bool:

all isJust maybeList
user_675790

The problem is in the part isJust y, y is the result of the fold for the tail of the list and therefore has type Bool. Just like the second argument True you are giving to the foldr function.

You can't call isJust on a value of type Bool. A simple fix would be to leave out the isJust.

The full error messages I get are:

<interactive>:3:16: error:
    • Couldn't match expected type ‘Maybe a’ with actual type ‘Bool’
    • In the expression: (isJust x) && (isJust y)
      In the first argument of ‘foldr’, namely
        ‘(\ x y -> (isJust x) && (isJust y))’
      In the expression:
        foldr (\ x y -> (isJust x) && (isJust y)) True maybeList
    • Relevant bindings include
        y :: Maybe a (bound at <interactive>:3:11)
        it :: Maybe a (bound at <interactive>:3:1)

<interactive>:3:42: error:
    • Couldn't match expected type ‘Maybe a’ with actual type ‘Bool’
    • In the second argument of ‘foldr’, namely ‘True’
      In the expression:
        foldr (\ x y -> (isJust x) && (isJust y)) True maybeList
      In an equation for ‘it’:
          it = foldr (\ x y -> (isJust x) && (isJust y)) True maybeList
    • Relevant bindings include
        it :: Maybe a (bound at <interactive>:3:1)

Which shows that GHC interprets it the wrong way around. It thinks that you meant to have the result be of type Maybe a0 for some a0. Then the second argument of foldr, namely True, has the wrong type and the result of the lambda has the wrong type.

user_152075680

The type of foldr is

foldr :: (a -> b -> b) -> b -> t a -> b

which means your lamda expression should take a Bool for it's second argument, whereas in your case it expects a Maybe.

user_4024280

@Ismor has the correct explanation.

Note that Haskell has a library function*

all :: (a -> Bool) -> [a] -> Bool
all f = foldr (\x y -> f x && y) True

So the solution of foldr (\x y -> isJust x && y) True maybeList is equivalent to all isJust maybeList.

Thus, the solution reads exactly like the specification: check to see if all elements of maybeList are Just => all isJust maybeList.

* Technically, the type of all is

all :: (Foldable f) => (a -> Bool) -> f a -> Bool

So any type constructor which implements the Foldable typeclass can be checked to see whether all its elements satisfy a particular predicate. You can thus use this for trees, lists, Maybes, etc.

user_119123420
Related