Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

haskell
communitycreator

How to split a list at position n in Haskell

Abdul Monum

Overview

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.

Recursive solution

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 the n problem; that is, [1,2], [3,4].

Code

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])
Haskell program for splitting a list

Explanation

  • 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 and tail are built-in Haskell functions that return the head of the list and the remainder of the list, respectively.

  • Line 5: We use 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.
  • Line 6: We attach the head of the list to the 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

haskell
communitycreator
RELATED COURSES

View all Courses

Keep Exploring