Как работает этот Haskell для вычисления перестановок с использованием понимания списка?

Question

Я читаю Хаскелла Саймона Томпсона: ремесло функционального программирования , и мне интересно, как это работает:

perms [] = [[]]
perms xs = [ x:ps | x <- xs , ps <- perms ( xs\\[x] ) ]

Я не могу понять, какчто perms( xs\\[x] ) должен функционировать.Трассировка двухэлементного списка показывает:

perms [2,3]
  [ x:ps | x <- [2,3] , ps <- perms ( [2,3] \\ [x] ) ]       exe.1
  [ 2:ps | ps <- perms [3] ] ++ [ 3:ps | ps <- perms [2] ]   exe.2
  ...

Как перейти от exe.1 к exe.2?

Answer 1

Это в основном говорит:

1. Возьмите любое x из списка xs (x <- xs)
2. Взять ps, то есть перестановку списка xs\\[x] (т.е. xs с удаленным x) - perms ( xs\\[x] )
3. Вернуть результат.

perms(xs\\[x]) - это рекурсивный вызов, который удаляет x из xs.

Answer 2

Ну, это просто вставляет 2 и 3 соответственно в [2,3] \\ [x].Таким образом, у вас есть

[ 2:ps | ps <- perms ([2,3] \\ [2]) ] ++ [ 3:ps | ps <- perms ([2,3] \\ [3]) ]

И поскольку \\ является оператором разности, то есть он возвращает элементы первого списка, которых нет во втором списке, результат равен [3] и [2] соответственно.