CODEWITHSUNDEEP
haskell
letter
letter

Reputation: 91

couln't match expected type with list sorting

we have to write a code with an higher-order function. It should be just one sentence long. A given list will be checked, if it is sorted. So far, I have this:

compare (a:xs) = foldl (\a b -> a < b ) True a xs || foldl (\a b -> a > b ) True

I alway get the error message: couln't match expected type bool witch actual type t0 Bool -> Bool. what does that mean?

Upvotes: 0

Views: 96

Answers (2)

Random Dev
Random Dev

Reputation: 52280

Ok I will try to give you some help of how you can do it.

First you should observe, that in order to check if a list is sorted you usually compare consecutive elements and check for example if they are ascending or not - note that you have to use two consecutive elements.

Now foldl and foldr let you only see one of them at a time - so you probably have to remember the previous element you saw somehow - and the only place to do this is to include it somehow in your state.

This can be done in various ways but I would recommend tuples.

So instead of the state being is the list sorted so far I would but in a tuple (is the list sorted so far, previous element).

Here is a simple template you have to fill with a few things:

isSorted :: Ord a => [a] -> Bool
isSorted (x:xs) = _A (foldl (\ (sorted,prev) cur -> (_B, _C)) (_D, _E) (_F))

if you try this this will not compile because you have to think about some holes (if you load it GHC(i) will help you with the types):

  • _E,_F should have type a and [a] respectively, hint _E should be the first previous element you saw - as checking this predicate for empty lists is useless you can probably use xs and x somehow ;)
  • _D should have type Bool
  • _C should have type a and be your next previous element
  • _B should have type Bool - this is where the flesh is - basically what you already tried
  • _A should have type (Bool, a) -> Bool you'll figure it out.

I will give the solution in an hour or so to make this answer complete - but you should really try to do it by yourself

solution

isSorted :: Ord a => [a] -> Bool
isSorted []     = True
isSorted (x:xs) = fst (foldl
                  (\ (sorted,prev) cur -> (sorted && prev <= cur, cur))
                  (True, x)
                  xs)

Upvotes: 0

chi
chi

Reputation: 116139

Hint 1: the third argument of foldl must be a list, and a is not.

Hint 2: Using your fold,

foldl (\a b -> a < b) base [1,2,3]
= (((base < 1) < 2) < 3)

and something is wrong here: the result of base < 1 is a boolean, and we can't compare that with 2 afterwards.

So, your function \a b -> a < b looks wrong in this context: it has the wrong type.

Upvotes: 2

Related Questions