The expressiveness of Haskell – Split a List.

Just recently playing around with one of the excellent Advent of Code problems (specifically 2015 question 6 ) a possible solution involved splitting a list into two parts where the first element goes into the first part, the second element into the second part and so on. For example

  • [1, 2, 3, 4, 5, 6] -> [1, 3, 5], [2, 4, 6]

So, in terms of function signatures we can write splitList :: [a] -> ([a], [a]) Notice there’s no constraint on the type in the list, it’s a very general function.

One way of doing this is is to make use of pattern matching and build up a solution recursively. i.e.

Here the splitList function calls another function that returns the solution in the ‘correct shape’. This go function uses pattern matching for the possible cases of the input list.

  • An empty input list get split into two empty lists.
  • Splitting a list of one item gives a list with that item and an empty list.
  • Similarly for a list of two items the result is two lists with one item in each.
  • The more general case pattern matches the input to two items and ‘the rest’, it then builds up the result lists and calls itself.

This certainly works fine – here are some sample runs.

And looking at the code it is fairly clear as to what’s happening. However it is a bit verbose and I think Haskell can provide a ‘better’ solution!

We have a list containing elements of type a. We know nothing about a so trying to apply a filter to the list won’t really work. However the list could be morphed into another list such that the original data is still there but there’s extra information that can be used as leverage. The zip function takes two lists and returns a list of pairs. i.e. zip :: [a] -> [b] -> [(a, b)] and if one list is longer than the other then zip terminates when the shortest list has ben processed. This allows us to use an infinite list when zipping. So we can zip up the original list and in effect tag the data in such a way that it will allow us to extract alternate elements.

For example

We can now filter [('a',0),('b',1),('c',2),('d',3)] by taking only those elements whose second value is odd (or even) i.e. filtering by odd:

We now have the alternate elements but they are tagged – so we need to remove the tags by taking just the first element of each entry in the list of pairs.

Using the above ideas in an alternate implementation of splitList we have

here the pair of lists are created from the alternate elements simply by zipping up with tags starting at different values.

A very succinct one-liner using function composition. I find little things like this in Haskell very, very pleasing and immensely satisfying! 🙂

Here are a few sample runs.

 

Thanks for reading…!

 

8 comments

Leave a Reply

Your email address will not be published. Required fields are marked *

ˆ Back To Top