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.

CodePudding user response：

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?

CodePudding user response：

Daniel Wagner posted a very nice answer that shows that you don't really need indices, after all.

Still, if you do want to use indices, a solution can be crafted as follows.

• We enumerate all the list elements by pairing them with their indices. This is done by using zip [0..] xs (or zip [1..] xs if you want to start counting at 1).
• We find whether your x is in the list, and find its index i if it's present. One could proceed by direct recursion, or use something like dropWhile ((/= x) . fst) ... and then test the result.
• Once we know i, we need to check whether there are at least i elements after that. This can be solved by direct recursion, or by dropping i-1 elements and testing whether the result is a non empty list.

There are other alternatives, of course. We could for instance skip enumerating elements with zip [0..] and use recursion by keeping track of the current index: foo n x (y:ys) = ... foo (n 1) x ys ....