Erlang список понимания, перестановки

Question

Я возился с примером перестановок из книги.Следующий код работает по назначению.

perms([]) -> [[]];
perms(L) -> [[H|T] || H <- L, T <- perms(L--[H])].

И когда я подставляю выражения, он становится таким:

[ [1 | perms([2])], 
   [2 | perms([1])] ]

[ [1 | [[2 | perms([])]]], 
   [2 | [[1 | perms([])]]] ]

[ [1 | [ [2 | [[]] ] ]], 
  [2 | [ [1 | [[]] ] ]] ]

И это правильно оценивается как [[1,2], [2,1]].

Но когда я изменил базовый случай на пустой список, из списка появляется пустой список:

perms([]) -> [];

Возвращает пустой список.Когда я заменил, я получил это.

   [ [1 | [[2 | [] ]]], 
     [2 | [[1 | [] ]]] ] 

Я попробовал оба выражения с flatten, но они дали тот же и правильный результат.

[[1 | lists:flatten([[2 | lists:flatten([[]]) ]])], [2 | lists:flatten([[1 | lists:flatten([[]]) ]])]]
[[1 | lists:flatten([[2 | lists:flatten([]) ]])], [2 | lists:flatten([[1 | lists:flatten([]) ]])]].

Так что я не мог понять разницу между двумявыражения.

Answer 1

Эта функция реализует рекурсивный алгоритм:

• Каковы перестановки непустого списка?Для каждого из элементов в списке возьмите перестановки списка минус этот элемент и добавьте элемент к каждой такой перестановке.
• Каковы перестановки пустого списка?Существует только один: сам пустой список, поэтому мы возвращаем список, содержащий один элемент, а именно пустой список: [[]]

Путем изменения базового регистра для возврата [] вместо [[]], вы говорите:

• Каковы перестановки пустого списка?Существует ноль перестановок.

И затем в рекурсивном случае вы переходите к шагу «возьмите перестановки ...» - но перестановок нет, поэтому нет ничего, что вы могли бы добавить к элементамк.