Ways to get the middle of a list in Haskell?

Question

I've just started learning about Functional Programming, using Haskel.

I'm slowly getting through Erik Meijer's lectures on Channel 9 (I've watched the first 4 so far) and in the 4th video Erik explains how tail works, and it fascinated me.

I've tried to write a function that returns the middle of a list (2 items for even lengths, 1 for odd) and I'd like to hear how others would implement it in

• The least amount of Haskell code
• The fastest Haskell code

If you could explain your choices I'd be very grateful.

My beginners code looks like this:

middle as | length as > 2   = middle (drop 2 (reverse as))
          | otherwise       = as

Answer 1

I don't make any performance claims, though it only processes the elements of the list once (my assumption is that computing length t is an O(N) operation, so I avoid it), but here's my solution:

mid [] = []                      -- Base case: the list is empty ==> no midpt
mid t = m t t                    -- The 1st t is the slow ptr, the 2nd is fast
  where m (x:_) [_] = [x]        -- Base case: list tracked by the fast ptr has
                                    -- exactly one item left ==> the first item
                                    -- pointed to by the slow ptr is the midpt.
        m (x:y:_) [_,_] = [x,y]  -- Base case: list tracked by the fast ptr has
                                    -- exactly two items left ==> the first two
                                    -- items pointed to by the slow ptr are the 
                                    -- midpts
        m (_:t) (_:_:u) = m t u  -- Recursive step: advance slow ptr by 1, and
                                    -- advance fast ptr by 2.

The idea is to have two "pointers" into the list, one that increments one step at each point in the recursion, and one that increments by two.

(which is essentially what Carl Smotricz suggested)

Answer 2

Just for your amusement, a solution from someone who doesn't speak Haskell:

Write a recursive function that takes two arguments, a1 and a2, and pass your list in as both of them. At each recursion, drop 2 from a2 and 1 from a1. If you're out of elements for a2, you'll be at the middle of a1. You can handle the case of just 1 element remaining in a2 to answer whether you need 1 or 2 elements for your "middle".