Element is in first half of the list, Haskell

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?

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 ....

Here’s another way to think of the task. An element x appears in the first half of a list xs, excluding the midpoint, if there are strictly fewer elements before the first occurrence of the element than after it.

We can write break (== x) xs using the standard function break :: (a -> Bool) -> [a] -> ([a], [a]) to split xs into two parts: those appearing before x (or all of xs, if x is not found), and the remainder (including x, if it is found).

> break (== 0) []
([], [])

> break (== 0) [0, 1]
([], [0, 1])

> break (== 0) [1, 0]
([1], [0])

> break (== 0) [1, 2, 0, 3, 4]
([1, 2], [0, 3, 4])

> break (== 0) [1, 2, 3, 4]
([1, 2, 3, 4], [])

We then want to compare the lengths of these two parts without calculating the actual lengths strictly as Int. To do so, we can compute the shape of each part by ignoring all its elements, using shape = map (const ()), a.k.a. void :: (Functor f) => f a -> f () specialised to lists.

shape :: [a] -> [()]
shape = void

The Ord instance for lists sorts them lexicographically, and all values of type () are equal—okay, the only value of type ()—so a comparison of shapes [()] is a comparison of the lengths of the lists, which is also lazy enough for our purposes. (For maximal laziness, shape could be defined as genericLength on a lazy natural number type like data N = Z | S N with an appropriate Ord instance.)

> [] < repeat ()
True

> shape [5 .. 10] >= shape [1 .. 3]
True

> shape [1 .. 3] > shape [1 ..]
False

We can also “decrement” the shape of a list using drop 1, which we’ll use to skip counting the element itself if it was found. (Alternatively, we could “increment” the shape with (() :).)

Finally, putting these elements together leads to a fairly simple solution:

isInFirstHalf :: (Eq a) => a -> [a] -> Bool
isInFirstHalf x xs = shape before < shape (drop 1 after)
  where
    (before, after) = break (== x) xs

Notice that if the element was not found, after will be empty, so drop 1 will have no effect, but the shape of before can’t possibly be smaller than the empty shape [], so the comparison (<) will still correctly return False.