Haskell Novice Trouble with Splitting a List in Half

Question

Here's my attempt to write a function that splits a list of even length into two equal halves.

halve :: [a] -> ([a], [a])
halve x 
   | even len = (take half x, drop half x)
   | otherwise = error "Cannnot halve a list of odd length"
   where
      len = length x
      half = len / 2

I am getting the following error:

 No instance for (Fractional Int) arising from a use of ‘/’
    In the expression: len / 2
    In an equation for ‘half’: half = len / 2
    In an equation for ‘halve’:

I don't understand the error but I have a suspicion that Haskell needs to be told in advance that len is something you can divide by 2. So, how do I rectify the example? Is my code anywhere near idiomatic haskell? I'd appreciate any other comments regarding my code.

Answer 1

The / is used for when you're happy to have a non-integer answer. Since you've already checked the number's even, you can hapily use integer division with div:

halve :: [a] -> ([a], [a]) 
halve x | even len = (take half x, drop half x) 
        | otherwise = error "Cannnot halve a list of odd length" 
   where len = length x 
         half = len `div` 2

(Personally I'd be happy to halve an odd length list inexactly and avoid an error message, but that's up to you.)

This distinction is indicated by the types:

(/) :: Fractional a => a -> a -> a
div :: Integral a => a -> a -> a 

so you can only use / when the type supports non-integer division, and you can only use div when it's a whole-number type. That way you can't make a mistake thinking you're doing one sort of division when you're actually doing another.

Well done, by the way, you're thinking stuff through well.

"No instance for... "

Actually, the "No instance for ..." error message is almost always because something's the wrong type. I most frequently get it when I've put arguments in the wrong order. In this case you've had is for using the othetr sort of divition when yout type is Int.

It says "No instance" because the function you're trying to use works for a class of types, but the type of the data you're giving isn't in (an instance of) that class. The compiler sees this as a missing instance declaration, where more often than not it's just a mistake and it's the wrong type altogether. I very rarely intend to make something an instance of a class and then forget, whereas I more often put arguments in the wrong place.

Answer 2

Mind you, halving a list can be done structurally, without any indices. Make two traversals of the list in parallel, one advancing at twice the rate of the other. When the faster hits bottom, the slow one has reached halfway.

halve :: [a] -> ([a], [a])
halve xs = go xs xs
  where
    go xs []  = ([],xs)
    go (x:xs) [_] = ([x],xs)
    go (x:xs) (_:_:ys) = let (first,last) = go xs ys in (x:first, last)

The second clause in go is the 'tie-breaker' in the case of an odd-length list. As is, the code places the odd-one out at the end of the first half. Simply change the right hand side to ([],x:xs) if you prefer otherwise.

This idea is half of the key to the "There And Back Again" pattern identified by Danvy and Goldberg (http://www.brics.dk/RS/05/3/BRICS-RS-05-3.pdf).

Answer 3

The type signature of the length function is [a] -> Int; this tells you that length returns an Int.

Moreover, the / operator (of type signature Fractional a => a -> a -> a) is only compatible with types which have a Fractional instance; because no Fractional instance exists for Int, you're not allowed to write something like

length x / 2

Use the div function (of type signature Integral a => a -> a -> a) to perform integer division:

div len 2

---

Besides, there are ways of improving your implementation of halve.

1. Instead of (take half x, drop half x), you could use splitAt half x, which only requires one pass through x.

2. Here is an implementation that is both more natural (that's what card players do!) and more efficient (no need to compute the length):

   halve :: [a] -> ([a], [a])
   halve []  = ([], [])
   halve [x] = ([x], [])  -- necessary case for input lists that contains an odd number of elements
   halve (x : y : zs) = (x : xs, y : ys)
     where
       (xs, ys) = halve zs
   

Answer 4

take and drop expect an argument of type Int. (/) performs a fractional division, so its result cannot be of type Int. Use div instead to perform an integral division:

halve :: [a] -> ([a], [a])
halve x 
   | even len = (take half x, drop half x)
   | otherwise = error "Cannnot halve a list of odd length"
   where
      len = length x
      half = len `div` 2