Search code examples
listhaskellsplitfold

Walk through a list split function in Haskell

This is a follow up to my previous question.

I am trying to understand the list splitting example in Haskell from here:

foldr (\a ~(x,y) -> (a:y,x)) ([],[])

I can read Haskell and know what foldr is but don't understand this code. Could you walk me through this code and explain it in more details ?

Solution

  • Let’s try running this function on a sample input list, say [1,2,3,4,5]:

    1. We start with foldr (\a ~(x,y) -> (a:y,x)) ([],[]) [1,2,3,4,5]. Here a is the first element of the list, and (x,y) start out as ([],[]), so (a:y,x) returns ([1],[]).
    2. The next element of the input list is a = 2, and (x,y) = ([1],[]), so (a:y,x) = ([2],[1]). Note that the order of the lists has swapped. Each iteration will swap the lists again; however, the next element of the input list will always be added to the first list, which is how the splitting works.
    3. The next element of the input list is a = 3, and (x,y) = ([2],[1]), so (a:y,x) = ([3,1],[2]).
    4. The next element of the input list is a = 4, and (x,y) = ([3,1],[2]), so (a:y,x) = ([4,2],[3,1]).
    5. The next element of the input list is a = 4, and (x,y) = ([4,2],[3,1]), so (a:y,x) = ([5,3,1],[4,2]).
    6. There are no more elements left, so the return value is ([5,3,1],[4,2]).

    As the walkthrough shows, the split function works by maintaining two lists, swapping them on each iteration, and appending each element of the input to a different list.