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 [1,2], [3,4]
.
The most simple split is at position 0
. If n
is 0
, then our problem is simple. The answer is the head of the list and the remainder. In this case, [1]
, [2,3,4]
.
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 [2]
, [3,4]
.
Note: If we add the head of the original list (
1
) to the first split of the above solution ([2]
) and keep the second split as it is, we arrive at the solution to then
problem; that is,[1,2]
,[3,4]
.
The code below demonstrates the Haskell program to split a list at position n
.
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.
Note:
head
andtail
are 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.split1
with (head list:split1, split2)
, which is the general solution. The let
keyword allows us to access split1
and split2
in the in
expression.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.
RELATED TAGS
CONTRIBUTOR
View all Courses