Haskell is a functional programming language and paradigm that focuses on changing data through expressions with no side effects. These expressions are often called pure functions. In this shot, we will write a pure function that splits a list at a particular position
n. Let’s break down the problem before jumping to the code.
Functional programming encourages us to define the problem more abstractly, independent of the concrete order of instructions. It is often helpful to break down the problem into smaller valid problems and solve them recursively.
Let’s take an example of a list,
[1,2,3,4], that we want to split at position
1. The answer should be
The most simple split is at position
0, then our problem is simple. The answer is the head of the list and the remainder. In this case,
To solve the
n problem, let’s assume our function correctly solves the n-1 problem and we have access to its solution. In our case, the n-1 problem splits
[2,3,4] at position
0. The correct solution is
Note: If we add the head of the original list (
1) to the first split of the above solution (
) and keep the second split as it is, we arrive at the solution to the
nproblem; that is,
The code below demonstrates the Haskell program to split a list at position
splitAtN :: Int ->  a -> ( a,  a) splitAtN = \n -> \list -> case n of 0 -> ([head list], tail list) otherwise -> let (split1, split2) = splitAtN (n-1) (tail list) in (head list:split1, split2) main = print (splitAtN 3 [1,2,3,4,7,8,9])
Line 1: We use
splitAtN :: Int ->  a -> ( a,  a),
a type annotation for our function called
splitAtN. Haskell is statically typed, and every function or variable has a type. In this case,
splitAtN is a function that takes an integer (the position
n) and a list of any type as its argument and returns a tuple (the resulting lists after the split).
Line 2: We use the function definition, which shows that our function takes an integer
n and a
list and a
case expression that implements our recursive formulation of the problem.
Line 4: The first equation represents the base case as discussed above.
tailare built-in Haskell functions that return the head of the list and the remainder of the list, respectively.
splitAtN (n-1) (tail list)to split the list with its head removed at position n-1, which gives us
split1, split2. The second equation represents our recursive definition.
(head list:split1, split2), which is the general solution. The
letkeyword allows us to access
Note: In the explanation above, we avoid visualizing what happened during the program execution of a recursive function but instead focus on its essence, which is treating the recursive function as a black box that can solve smaller valid problems.
View all Courses