Как этот Haskell функционирует для вычисления перестановок с помощью работы понимания списка?

Я читаю 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?

7
задан Evan Carroll 7 August 2010 в 22:15
поделиться

2 ответа

По сути, он говорит:

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

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

4
ответ дан 7 December 2019 в 05:15
поделиться

Ну, он просто вставляет 2 и 3 соответственно в [2,3] \\\ [x]. Получается

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

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

4
ответ дан 7 December 2019 в 05:15
поделиться
Другие вопросы по тегам:

Похожие вопросы: