Select Pair Function in Haskell

Question

In my class, our professor used this select function for a permutation function.

select :: [a] -> [(a,[a])]
select [] = []
select (x:xs) = (x,xs) : map(\(y,ys) ->(y,x:ys))(select xs)

In this code, this part confuses me

map(\(y,ys) ->(y,x:ys))(select xs)

I didn't actually understand what this part does

\(y,ys) ->(y,x:ys)

Answer 1

select returns for a given list of 2-tuples where each item has as first item the item selected and the second item a list of all elements except the selected one.

So this means that:

Prelude> select [1,4,2,5]
[(1,[4,2,5]),(4,[1,2,5]),(2,[1,4,5]),(5,[1,4,2])]

For an empty list, we thus return an empty list (of 2-tuples), since we can not select a single element.

For a list that contains at least one element there are two cases:

1. we select the first element, and we use the tail as list of remaining elements; and
2. we select another element. We can recurse on the tail, and thus select an element from the tail, but the tail of course does not contain the element the head of the list of remaining elements. We will later need to add x to all the items.

We can do that with a mapping where we prepend x to each list of remaining elements.

For example if we perform select [1, 4] then we thus obtain the first element with:

select [1, 4] = (1, [4]) : map (\(y, ys) -> (y, x : ys)) (select [4])

select [4] will return:

select [4] = (4, []) : map (\(y, ys) -> (y, x : ys)) (select [])

select for an empty list returns an empty list, so that means that:

select [4] = (4, []) : map (\(y, ys) -> (y, x : ys)) []

and thus:

select [4] = (4, []) : []

which is equivalent to:

select [4] = [(4, [])]

for the select [1,4] we thus obtain:

select [1, 4] = (1, [4]) : map (\(y, ys) -> (y, x : ys)) [(4, [])]

we thus will need to add 1 to the empty list, we do that with the mapping and thus obtain:

select [1, 4] = (1, [4]) : [(4, [1])]

which is thus equivalent to:

select [1, 4] = [(1, [4]), (4, [1])]

The \(y,ys) ->(y,x:ys) is thus a lambda expression that maps a 2-tuple (y, ys) to a 2-tuple (y, x : ys), it thus prepend the list in the second item of the 2-tuple.