Haskell Permute Function

user_14596875 0
Viewed 96

This is my first question on this site. So if I am rude or not formal enough, I am sorry already.
In my discrete math class professor showed us this permute function

permute :: [a] -> [[a]]
permute [] = [[]]
permute xs = [y:zs| (y,ys) <- select xs, zs <- permute ys]

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

I didn't understand this part

permute xs = [y:zs| (y,ys) <- select xs, zs <- permute ys]

I tried permute [1] to understand clearly, in the first recursion select xs takes [1] and returns [(1,[])]. Then permute ys takes [] if I am not mistaken.

In the second recursion, select takes [] and returns [] . I am lost somewhere here. As I see it, it should return [[1],[]] but it returns [[1]].
I would be very happy if someone helps.

permutation discrete-mathematics algorithm haskell
1 Answers

If you call permute [1], then select [1], will return [(1, [])], so that means that the list comprehension will take y = 1 and ys = []. Then we call permute [], which returns [[]]. This thus means that zs will only take zs = []. We thus will yield [ y : zs ] which is equivalent to [ 1 : [] ], and thus [[]].

So since zs <- permute [], and thus is equivalent to zs <- [[]], then this means that it only iterates once with zs = [].

If you permute [1,2] then we thus call select [1,2], and this returns [(1, [2]), (2, [1])]. This thus means that in the list comprehension, (y, ys) will "iterate" twice: once with y=1 and ys=[2]; and later with y=2 and ys=[1]. For each value for (y, ys) it will then call permute. The permute [1] will return [[1]], and permute [2] will return [[2]]. This thus means that we will return a list with: [ 1 : [2], 2 : [1]] which is thus equivalent to [[1,2], [2,1]].

user_675790
Related