foo s1 s2 = null ([x | x <- s2, x == s1])

Please explain when this function will end?

Will Haskell first iterate through the entire list and then check for null, or when one element appears, will he check for null and complete the iteration? If the first option, then how can it be made more lazy?

CodePudding user response：

Will Haskell first iterate through the entire list and then check for null.

No. null checks if it is an empty list, and returns True for an empty list [], and False for the (:) data constructor. The "old" null is implemented as [src]:

null                    :: [a] -> Bool
null []                 =  True
null (_:_)              =  False

It will thus evaluate the list comprehension to head normal form (HNF), and once it knows the outer data constructor it can return True or False: it will not check what the first element is, so if that is an expensive expression, it will not waste time on that one either.

The "new" null is implemented as [src]:

null :: t a -> Bool
null = foldr (\_ _ -> False) True

where foldr for a list is implemented as [src]:

foldr k z = go
          where
            go []     = z
            go (y:ys) = y `k` go ys

which will thus also simply check if the outer data constructor is an empty list [] or a "cons" (:) since in this case k returns True and is not interested in the parameters.

List comprehensions are lazy as well: these will only evaluate the outer data constructor if necessary, and construct the head and tail if necessary. Your list comprehension is desugared to:

concatMap (\x -> if x == s1 then [x] else []) s2

If it thus has to evaluate the outer data constructor of the list, it will iterate over s2, if x == s1 then it will produce as outer data constructor the "cons" and then null can thus use that to determine if the list is empty.

This thus means that from the moment it finds an element x from s2 where x == s1, it will return False.