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

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

Answer 2

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

Answer 3

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 4

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

Answer 5

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

Answer 6

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

Answer 7

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

Answer 8

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)

Answer 9

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

Answer 10

Solution inspired by Carl's answer.

import Control.Monad.Instances

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

Answer 11

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

Answer 12

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

Answer 13

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.

Answer 14

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

Answer 15

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