CODEWITHSUNDEEP
listhaskell
Bradley
Bradley

Reputation: 1281

Splitting a list into a tuple of lists at a specified index

I found this piece of code on a question which is similar to one which I am trying to solve and I'm trying to apply the logic of this function to my problem. However, the explanation of the code isn't completely clear on the question. The code is as follows: 

   splitAtIndex :: Int -> [a] -> ([a], [a])
   splitAtIndex 0 xs    = ([], xs)
   splitAtIndex _ [] = ([], [])  
   splitAtIndex x (y:ys) =  (y:ys', ys'') 
     where 
       (ys', ys'') = splitAtIndex (x - 1) ys

The way I understand this, is that you take the index and the whole list and form a tuple of lists where the tuple of lists is equal to the recursive call of index-1 of the tail of the list. Am I missing something here? Is the use of apostrophes important here? I really don't see where the split of the list takes place. I'm sure once explained it will seem simple but I can't seem to grasp it.

Thanks!

Upvotes: 0

Views: 244

Answers (2)

Robert M. Lefkowitz
Robert M. Lefkowitz

Reputation: 1495

As has been pointed out, the apostrophes are equivalent to letters in names. The convention is that if you have a variable x, then a modified copy of x is often referred to as x'.

To eliminate that confusion, you could rewrite the definition as:

splitAtIndex x (y:ys) = (y:p, q) where (p, q) = splitAtIndex (x - 1) ys

To understand the algorithm, it might be helpful to consider an example. Let us say you want to split the list [1,2,3,4,5,6] at position 2. The call would be:

splitAtIndex 2 [1,2,3,4,5,6]

The where clause in your function results in the following expression:

splitAtIndex 1 [2,3,4,5,6]

because ys is the tail and (x-1) is (2-1). The result of that expression is a tuple (p,q). But the result of the original expression conses the first element of the original list onto the first element of the tuple (y:p,q). So the result of splitAtIndex 2 [1,2,3,4,5,6] is (1:p, q) where p is the first element of splitAtIndex 1 [2,3,4,5,6] and q is the second element of that tuple. As we would expect splitAtIndex 1 [2,3,4,5,6] to return ([2],[3,4,5,6]), the final result is (1:[2],[3,4,5,6]) (which is ([1,2],[3,4,5,6]).

Upvotes: 1

Patricia
Patricia

Reputation: 2865

The apostrophes belong to the variables that are used for the recursive call splitAtIndex (x - 1) ys. That is the only meaning.

And you can understand the code when you start in your thoughts with an index of 1. Here you take the empty list at the left of the tuple and hang on its left the head of the list. And so on.

Upvotes: 0

Related Questions