How to split a list in even and odd indexes in Haskell

Overview

Haskell is a functional programming language. The functional programming paradigm focuses on changing data through expressions that don’t have side effects. These expressions are often called pure functions. We’ll write a pure function that splits a list into two halves based on odd and even index positions. Let’s break down the problem before jumping to the code.

Recursive solution

Functional programming encourages us to define the problem in a more abstract way, independent of the concrete order of instructions. Often, it is helpful to break down the problem into smaller valid problems and solve them recursively.

Let’s take an example of a list [4,4,1,8,9,2]. If we divide the list into two halves based on even and odd index positions then the answer should be [4,1,9], [4,8,2]. Note that the first part of the split is the list with even index positions and the latter is the list with odd index positions.

• Any recursive solution starts with a base case. In our case, the base scenario is simple. If we have an empty list, then we cannot split it further. Therefore, we return two empty lists.

• Now, to solve the general case where we have a list with any number of elements present, we try to identify a smaller problem and see if we can use its solution to solve the original problem.

• A smaller problem would be our function solving the split problem for a smaller list from the original list. Let’s identify a smaller list [4,1,8,9,2] (we removed the head of the original list) which can be split into even and odd index positions and assume our function correctly solves this problem. The solution to this problem is [4,8,2], [1,9].

• Note that if we add the head of the original list (4) to the list with odd index positions [1,9] in the above solution, then this is the solution to the list that consists of even index positions of the original problem! Also, note that the list with even index positions [4,8,2] in the smaller solution is the answer for the list with odd index positions of the original problem! We arrive at the final answer [4,1,9], [4,8,2].

Program

Let’s look at a program in Haskell to split a list based on odd and even index positions.

Explanation

The split function divides a list into two halves based on odd and even index positions.

• Line 2: split :: [Int] -> ([Int], [Int]) is the type annotation for our function called split. Haskell is statically typed, and every function or variable has a type. In this case, split is a function that takes a list of the Int type and returns a tuple of lists (type Int).
• Line 3: We have the function definition that shows that our function takes a list. It also takes a case expression on the list that implements the recursive formulation of the problem.
• Line 5: The first equation shows that if there is any empty list, we return a tuple of empty lists.
• Line 6: The second equation implements the general case. x:xs is a syntax in Haskell that neatly provides us with the head of the list, x, and the remainder list xs. We do a recursive call of the split function on the list xs. We can safely assume it correctly provides the solution into evens and odds. For the complete list x:xs, we attach the head x with odds which is the even split of the original problem, and therefore return the tuple (x:odds, evens) for the final solution.