I need to check if a list only contains odd numbers, bigger than 10. This is what I did.

f :: [Int] -> Bool
f xs= [x |x<-xs, x >10,  odd x]

Why does this not work?

CodePudding user response：

When you write [x |x<-xs, x >10, odd x] you're making up a list of Ints, a [Int], not a Boolean. For instance you can verify that [x | x <- [1..20], x > 10, odd x] is the list [11,13,15,17,19]. So it does contain the numbers that you want, but how do you tell that those are all of the numebrers in xs?

You could certainly equate that list to xs itself, and that would work:

f xs = xs == [x |x<-xs, x >10,  odd x]

This way the == ensures that when you only take odd numbers greater than 10 from xs you get back exactly xs, meaning that all numbers satisfy the predicate.

Maybe this is the mistake you were looking for.

I'm not sure whether this solution traverses xs twice (once to extract the entries satisfying the predicate, and once to check for equality) or not. It looks very simple, so I can't help but think that the list is traversed only once.

Anyway, another strategy is to stick to your request: you want all numbers x from the list xs for which odd x and x > 10 are both True:

f :: [Int] -> Bool
f xs = all (\x -> odd x && x > 10) xs

By noticing that both sides have a trailing xs, you can reduce the definition:

f :: [Int] -> Bool
f = all (\x -> odd x && x > 10)

And that lambda, if you want, could be define more succintly as (odd & (> 10)), thus getting

f :: [Int] -> Bool
f = all (odd & (> 10))

provided you import Control.Monad (liftM2) and define

(&) :: (a -> Bool) -> (a -> Bool) -> (a -> Bool)
(&) = liftM2 (&&)

CodePudding user response：

Your type signature mentions that the function returns a boolean value, but your proposed body returns a list of numbers. Haskell has no automatic conversions such as Lisp.

Should you wish to stick to pedestrian code, you could get the sublist of offending numbers, and just check that the sublist is empty.

f :: [Int] -> Bool
f xs = let offenders = [x | x <- xs, x <= 10  ||  even x]
       in   (null offenders)

Note that due to the laziness of the language runtime, evaluation of offenders stops as soon as we find a first element.

Should you want something a bit more haskell-ish, you can use the sequence :: (Traversable t, Monad m) => t (m a) -> m (t a) polymorphic library function to turn a list of predicates into a single function returning a list of boolean values, then pass that list to and. That checks one number.

Then use all to apply these checks to all numbers in the input list. Like this:

f2 :: [Int] -> Bool
f2 = all (and . sequence [(>10), odd])

Explanation:

To understand how exactly the sequence function gets specialized by the compiler, one can use the TypeApplications language extension.

With the extension enabled, given 3 type arguments, expression sequence @tt @tm @ta maps tt to the Traversable instance, tm to the Monad instance and ta to argument type a.

$ ghci
 GHCi, version 8.8.4: https://www.haskell.org/ghc/  :? for help
 λ> 
 λ> :type sequence
 sequence :: (Traversable t, Monad m) => t (m a) -> m (t a)
 λ> 
 λ> :set -XTypeApplications
 λ> 

We start with the easiest part, mapping tt to lists and ta to Bool, leaving tm undefined as an underscore _:

 λ> 
 λ> :type  sequence @[]  @_  @Bool
 sequence @[] @_ @Bool :: Monad _ => [_ Bool] -> _ [Bool]
 λ> 

Now, if we assign tm to “function of an Int variable”, we have the whole picture:

 λ> 
 λ> :type  sequence @[]  @((->)Int)  @Bool
 sequence @[] @((->)Int) @Bool :: [Int -> Bool] -> Int -> [Bool]
 λ> 

The last type can be interpreted as [Int -> Bool] -> (Int -> [Bool]), that is, function sequence transforming a list of predicates into a single function returning a list of boolean values.