Walk through a list split function in Haskell

Question

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 ?

Answer 1

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.

Answer 2

We can take a look at an example. For example if we have a list [1, 4, 2, 5]. If we thus process the list, then we see that foldr will be calculated as:

foldr (\a ~(x,y) -> (a:y,x)) ([],[]) [1,4,2,5]

So here a is first the first item of the list, and then it will tus return something like:

(1:y, x)
    where (x, y) = foldr (\a ~(x,y) -> (a:y,x)) ([],[]) [4,2,5]

Notice that here the (x, y) tuple is swapped when we prepend a to the first item of the 2-tuple.

(1:y, x)
    where (x, y) = (4:y', x')
          (x', y') = foldr (\a ~(x,y) -> (a:y,x)) ([],[]) [2,5]

and if we keep doing that, we thus obtain:

(1:y, x)
    where (x, y) = (4:y', x')
          (x', y') = (2:y'', x'')
          (x'', y'') = (5:y''', x''')
          (x''', y''') = foldr (\a ~(x,y) -> (a:y,x)) ([],[]) []

Since we reached the end of the list, we thus obtain for the foldr … ([], []) [], the 2-tuple ([], []):

(1:y, x)
    where (x, y) = (4:y', x')
          (x', y') = (2:y'', x'')
          (x'', y'') = (5:y''', x''')
          (x''', y''') = ([],[])

So x''' = [] and y''' = [], so thus this is resolved to:

(1:y, x)
    where (x, y) = (4:y', x')
          (x', y') = (2:y'', x'')
          (x'', y'') = (5:[], [])
          (x''', y''') = ([],[])

so x'' = [5] and y'' = []:

(1:y, x)
    where (x, y) = (4:y', x')
          (x', y') = (2:[], [5])
          (x'', y'') = (5:[], [])
          (x''', y''') = ([],[])

so x' = [5] and y' = [2]:

(1:y, x)
    where (x, y) = (4:[5], [2])
          (x', y') = (2:[], [5])
          (x'', y'') = (5:[], [])
          (x''', y''') = ([],[])

so x = [4, 5] and y = [2] so eventually we obtain:

(1:[2], [4,5])
    where (x, y) = (4:[5], [2])
          (x', y') = (2:[], [5])
          (x'', y'') = (5:[], [])
          (x''', y''') = ([],[])

so the result is the expected ([1,2], [4,5]).

Answer 3

Let's translate the fold away.

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

What's this mean? foldr for lists is defined

foldr :: (a -> r -> r) -> r -> [a] -> r
foldr k z = go
  where
    go [] = z
    go (p : ps) = p `k` go ps

Let's inline it and simplify:

splatter = go
  where
    go [] = ([], [])
    go (p : ps) =
      (\a ~(x,y) -> (a:y,x)) p (go ps)

splatter = go
  where
    go [] = ([], [])
    go (p : ps) =
      (\ ~(x,y) -> (p:y,x)) (go ps)

splatter = go
  where
    go [] = ([], [])
    go (p : ps) =
      let (x, y) = go ps
      in (p : y, x)

The lazy-by-default pattern match in the let means that we don't actually actually make the recursive call until someone forces x or y.

The key thing to notice is that x and y swap places on each recursive call. This leads to the alternating pattern.