Element is in first half of the list, Haskell

Question

Reading the book Get Programming with Haskell, one of the questions was to find if a given element is in the first half of a list. This can be done as

isInFirstHalf x xs = elem x firstHalf
    where firstHalf = take (length xs `div` 2) xs

However, the problem is that here length traverses the whole list. In an imperative language, one can shortcircut the loop early by keeping track of the element index and the current counter. E.g. if the list has a million elements, and there was a match on the third element, once you finish looping through the sixth element, you can immediately return true.

My question is if there's a way to implement something like this in Haskell.

Answer 1

Sure.

halfAsLong (x:_:xs) = x:halfAsLong xs
halfAsLong _ = []

isInFirstHalf x xs = elem x (zipWith const xs (halfAsLong xs))

Try it out:

> isInFirstHalf 3 (1:2:3:4:5:6:undefined)
True

Exercises for the reader:

• Where did the element index and current counter of your proposed imperative solution go? (They are still in there, just hidden in a way I think is a bit subtle!)
• This rounds down when dividing odd lengths in half, like length xs `div` 2 does. How would the code have to change to round up, like (length xs + 1) `div` 2 does?