Two versions

1. Using pattern matching, tail and init:

   middle :: [a] -> [a]
   middle l@(_:_:_:_) = middle $ tail $ init l
   middle l           = l
   

2. Using length, take, signum, mod, drop and div:

   middle :: [a] -> [a]
   middle xs = take (signum ((l + 1) `mod` 2) + 1) $ drop ((l - 1) `div ` 2) xs
     where l = length xs
   

The second one is basically a one-liner (but uses where for readability).

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

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)

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 right datastructure for the right problem. In this case, you ve specified something that only makes sense on a finite list, right? There is no middle to an infinite list. So just reading the description, we know that the default Haskell list may not be the best solution: we may be paying the price for the laziness even when we don t need it. Notice how many of the solutions have difficulty avoiding 2*O(n) or O(n). Singly-linked lazy lists just don t match a quasi-array-problem too well.

Fortunately, we do have a finite list in Haskell: it s called Data.Sequence.

Let s tackle it the most obvious way: index (length / 2) .

Data.Seq.length is O(1) according to the docs. Data.Seq.index is O(log(min(i,n-i))) (where I think i=index, and n=length). Let s just call it O(log n). Pretty good!

And note that even if we don t start out with a Seq and have to convert a [a] into a Seq, we may still win. Data.Seq.fromList is O(n). So if our rival was a O(n)+O(n) solution like xs !! (length xs), a solution like

middle x = let x  = Seq.fromList x in Seq.index(Seq.length x  `div` 2)

will be better since it would be O(1) + O(log n) + O(n), which simplifies to O(log n) + O(n), obviously better than O(n)+O(n).

(I leave as an exercise to the reader modifying middle to return 2 items if length be even and 1 if length be odd. And no doubt one could do better with an array with constant-time length and indexing operations, but an array isn t a list, I feel.)

Haskell solution inspired by Carl s answer.

middle = m =<< drop 1
   where m []  = take 1
         m [_] = take 2
         m (_:_:ys) = m ys . drop 1

If the sequence is a linked list, traversal of this list is the dominating factor of efficiency. Since we need to know the overall length, we have to traverse the list at least once. There are two equivalent ways to get the middle elements:

• Traverse the list once to get the length, then traverse it half to get at the middle elements.
• Traverse the list in double steps and single steps at the same time, so that when the first traversal stops, the second traversal is in the middle.

Both need the same number of steps. The second is needlessly complicated, in my opinion.

In Haskell, it might be something like this:

middle xs = take (2 - r) $ drop ((div l 2) + r - 1) xs
          where l = length xs
                r = rem l 2

middle xs =
  let (ms, len) = go xs 0 [] len
  in  ms

go (x:xs) i acc len =
  let acc_ = case len `divMod` 2 of
         (m, 0) -> if m  == (i+1) then (take 2 (x:xs))
                                  else acc
         (m, 1) -> if m  == i     then [x]
                                  else acc
  in go xs (i+1) acc_ len

go [] i acc _ = (acc,i)

This solution traverses the list just once using lazy evaluation. While it traverses the list, it calculates the length and then backfeeds it to the function:

let (ms, len) = go xs 0 [] len

Now the middle elements can be calculated:

let acc  = case len `divMod` 2 of
...

F# solution based on Carl s answer:

let halve_list l =
    let rec loop acc1 = function
        | x::xs, [] -> List.rev acc1, x::xs
        | x::xs, [y] -> List.rev (x::acc1), xs
        | x::xs, y::y ::ys -> loop (x::acc1) (xs, ys)
        | [], _ -> [], []
    loop [] (l, l)

It s pretty easy to modify to get the median elements in the list too:

let median l =
    let rec loop acc1 = function
        | x::xs, [] -> [List.head acc1; x]
        | x::xs, [y] -> [x]
        | x::xs, y::y ::ys -> loop (x::acc1) (xs, ys)
        | [], _ -> []
    loop [] (l, l)

A more intuitive approach uses a counter:

let halve_list2 l =
    let rec loop acc = function
        | (_, []) -> [], []
        | (0, rest) -> List.rev acc, rest
        | (n, x::xs) -> loop (x::acc) (n - 1, xs)
    let count = (List.length l) / 2
    loop [] (count, l)

And a really ugly modification to get the median elements:

let median2 l =
    let rec loop acc = function
        | (n, [], isEven) -> []
        | (0, rest, isEven) ->
            match rest, isEven with
            | x::xs, true -> [List.head acc; x]
            | x::xs, false -> [x]
            | _, _ -> failwith "Should never happen"
        | (n, x::xs, isEven) -> loop (x::acc) (n - 1, xs, isEven)

    let len = List.length l
    let count = len / 2
    let isEven = if len % 2 = 0 then true else false
    loop [] (count, l, isEven)

Getting the length of a list requires traversing its entire contents at least once. Fortunately, it s perfectly easy to write your own list data structure which holds the length of the list in each node, allowing you get get the length in O(1).

Weird that this perfectly obvious formulation hasn t come up yet:

middle []    = []
middle [x]   = [x]
middle [x,y] = [x,y]
middle xs    = middle $ init $ tail xs

A very straightforward, yet unelegant and not so terse solution might be:

middle :: [a] -> Maybe [a]
middle xs
    | len <= 2 = Nothing
    | even len = Just $ take 2 . drop (half - 1) $ xs
    | odd len = Just $ take 1 . drop (half) $ xs
    where 
          len = length xs
          half = len `div` 2

This iterates twice over the list.

mid xs = m where
  l = length xs
  m | l `elem` [0..2] = xs
  m | odd l = drop (l `div` 2) $ take 1 $ xs
  m | otherwise = drop (l `div` 2 - 1) $ take 2 $ xs

I live for one liners, although this example only works for odd lists. I just want to stretch my brain! Thank you for the fun =)

foo d = map ((Just a) -> a) $ filter (/=Nothing) $ zipWith (a b -> if a == b then Just a else Nothing) (Data.List.nub d) (Data.List.nub $ reverse d)

I m not much of a haskeller myself but I tried this one.

First the tests (yes, you can do TDD using Haskell)

module Main
where
import Test.HUnit
import Middle
main = do runTestTT tests
tests = TestList [ test1
                 , test2
                 , test3
                 , test4
                 , test_final1
                 , test_final2
                 ]

test1         =     [0]    ~=? middle [0]
test2         =     [0, 1] ~=? middle [0, 1]
test3         =     [1]    ~=? middle [0, 1, 2]
test4         =     [1, 2] ~=? middle [0, 1, 2, 3]
test_final1   =     [3]    ~=? middle [0, 1, 2, 3, 4, 5, 6]
test_final2   =     [3, 4] ~=? middle [0, 1, 2, 3, 4, 5, 6, 7]

And the solution I came to:

module Middle
where

middle a = midlen a (length a)

midlen (a:xs) 1 = [a]
midlen (a:b:xs) 2 = [a, b]
midlen (a:xs) lg = midlen xs (lg - (2)) 

It will traverse list twice, once for getting length and a half more to get the middle, but I don t care it s still O(n) (and getting the middle of something implies to get it s length, so no reason to avoid it).

My solution, I like to keep things simple:

middle [] = []
middle xs | odd (length xs) = [xs !! ((length xs) `div` 2)]
          | otherwise = [(xs !! ((length xs) `div` 2)),(reverse $ xs) !! ((length xs)`div` 2)]

Use of !! in Data.List as the function to get the value at a given index, which in this case is half the length of the list.

Edit: it actually works now

I like Svante s answer. My version:

> middle :: [a] -> [a]
> middle [] = []
> middle xs = take (r+1) . drop d $ xs
>  where
>    (d,r) = (length xs - 1) `divMod` 2

Here is my version. It was just a quick run up. I m sure it s not very good.

middleList xs@(_:_:_:_) = take (if odd n then 1 else 2) $ drop en xs
    where n = length xs
          en = if n < 5 then 1 else 2 * (n `div` 4)
middleList xs = xs

I tried. :)

If anyone feels like commenting and telling me how awful or good this solution is, I would deeply appreciate it. I m not very well versed in Haskell.

EDIT: Improved with suggestions from kmc on #haskell-blah

EDIT 2: Can now accept input lists with a length of less than 5.

Another one-line solution:

--
middle = ap (take . (1 +) . signum . (`mod` 2) . (1 +) . length) $ drop =<< (`div` 2) . subtract 1 . length
--