How is this function dealing into 2 lists?-CodePudding

The purpose of this self created function is to take in a list, and output 2 lists, they are to ne inserted into the lists alternating. SO [4,5,1,6,7,8] will be dealt into 2 lists like ([4,1,7],[5,6,8])

deal :: [a] -> ([a],[a])
deal [] = ([],[])
deal [x] = ([x],[])
deal (x:xs) = let (ys,zs) = deal xs
              in (x:zs, ys)

this is the function. Im not understanding what is happening with let (ys,zs) = deal xs, i know its basically creating a placeholder for 2 lists but can someone walk me through the recursion thats taking place.

CodePudding user response：

By definition,

deal [8] = ([8], [])

Now:

deal [7,8]
= deal (7:[8])
= let (ys,zs) = deal [8]
  in (7:zs, ys)
-- from the recursion we discover ys=[8], zs=[]
= (7:[], [8])
= ([7], [8])

Again:

deal [6,7,8]
= deal (6:[7,8])
= let (ys,zs) = deal [7,8]
  in (6:zs, ys)
-- from the recursion we discover ys=[7], zs=[8]
= (6:[8], [7])
= ([6,8], [7])

And so on. Every time we recurse, we swap the previous result pair and prepend an item to the first component. Because of the swaps, it's like adding an element to the first component, then to the second one, then again to the first, and so on, alternating. This splits the list in half, roughly speaking.