Я читаю Haskell Simon Thompson: Ремесло Функционального программирования, и я задаюсь вопросом, как делает эту работу:
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
?
По сути, он говорит:
x
из списка xs
( x <- xs
) ps
, который является перестановкой списка xs \\ [x]
(т.е. xs
с удаленным x
) - perms (xs \\ [x])
perms (xs \\ [x])
- это рекурсивный вызов, который удаляет x
из xs
.
Ну, он просто вставляет 2
и 3
соответственно в [2,3] \\\ [x]
. Получается
[ 2:ps | ps <- perms ([2,3] \\ [2]) ] ++ [ 3:ps | ps <- perms ([2,3] \\ [3]) ]
А поскольку \\\
является оператором разности, т.е. возвращает элементы первого списка, которых нет во втором списке, то получаются [3]
и [2]
соответственно.