Как и любая рекурсивная функция, которая работает со списками, эту можно разбить на два случая:
1) Что должна делать функция в пустом списке?
2) Если я знать, что функция делает со списком длины n, могу ли я использовать это, чтобы выяснить, что функция должна делать со списком длины n + 1.
Как только вы узнаете эти две вещи, у вас есть определение, которое будет работать в любом списке (по крайней мере, одного конечной длины - такая процедура, конечно, никогда не закончится для бесконечной длины; здесь это не имеет значения, так как нет смысла говорить о перестановках из бесконечный список). [Если у вас есть какой-либо математический фон, вы узнаете это как простую формулировку закона математической индукции .]
Для функции perms ясно, что есть только один способ перестановки 0 элементов пустого списка: другой пустой список. Это дает [[]] для базового случая, как в первой строке примера решения.
Для рекурсивного / индуктивного шага, скажем, у нас есть список xs длины n (где n > 0) и предположим (как нам позволено), что мы уже знаем, как вычислить все перестановки любого списка длины n - 1.
Каждая перестановка должна начинаться с определенного элемента xs - давайте назовем этот элемент i и подумаем, как получить все перестановки xs, первый элемент которых i. Должно быть ясно, что они точно соответствуют всем перестановкам списка delete i xs (то есть xs с одним удаленным i) - учитывая перестановку j последнего, список i : j является перестановкой xs, который начинается с i, и наоборот, все такие перестановки xs могут быть получены таким образом.
Обратите внимание, что это именно тот список [ i:j | j <- perms $ delete i xs ]
( И мимоходом обратите внимание, что, поскольку мы предположили, что i находится в xs, delete i xs действительно имеет длину n - 1, поэтому по индуктивной гипотезе мы знаем, как это вычислить.)
* Конечно, 1046 * было выбрано совершенно произвольно, и все элементы xs должны быть учтены как первый элемент некоторых перестановок. Таким образом, мы просто собрали все вышеперечисленное для всех элементов i в xs - что в точности соответствует выражению в рекурсивном шаге:
[ i:j | i <- xs, j <- perms $ delete i xs ]
Возможно, вам потребуется прочитать некоторые из Выше, медленно, несколько раз, прежде чем это имеет смысл - но это принципиально очень элементарные логики c (и, как и большинство элементарных логик c, имеет неприятную привычку часто выглядеть сложнее, чем на самом деле).