Ну, эти два, очевидно, очень похожи, так почему бы не посмотреть подробно, где они не согласны?Рекурсивная часть в обоих случаях одинакова, поэтому сначала мы можем сказать, что обе версии делают одно и то же в непустых списках.Это звучит неправильно, потому что они дают разные результаты, но на самом деле это правда, что они выполняют одну и ту же операцию с результатом рекурсивного вызова .
Базовый случай из правильной версии: permute [] = [[]], что говорит само за себя.Базовый случай из первой версии, однако, подразумевается в понимании списка.Учитывая определение:
permute xs = [y:ps | (y,ys) <- selections xs, ps <- permute ys]
... мы можем заменить xs в [], чтобы посмотреть, что произойдет:
permute [] = [y:ps | (y,ys) <- selections [], ps <- permute ys]
Учитывая определение selections [] = [], мы можемупростим до:
permute [] = [y:ps | (y,ys) <- [], ps <- permute ys]
... из которого видно, что никаких результатов не генерируется, поэтому понимание всего списка пустое, упрощаясь до:
permute [] = []
Теперь,рассмотрим последний рекурсивный шаг перед базой, подставив [x] в качестве аргумента:
permute [x] = [y:ps | (y,ys) <- selections [x], ps <- permute ys]
Определение selections равно selections (x:xs) = (x, xs) : [ (y, x:ys) | (y,ys) <- selections xs ], подстановка в [x] дает selections [x] = (x, []) : [ (y, x:ys) | (y,ys) <- selections [] ].selections [] оценивается как [], поэтому понимание всего списка также уменьшается до [], давая selections [x] = (x, []) : [] или просто selections [x] = [(x, [])].
Подставьте это в permute, как указано выше:
permute [x] = [y:ps | (y,ys) <- [(x, [])], ps <- permute ys]
В списке только один элемент, поэтому мы можем игнорировать привязку понимания <- и подставить напрямую:
permute [x] = [y:ps | (y,ys) = (x, []), ps <- permute ys]
permute [x] = [ x:ps | ps <- permute []]
Установив, что permute [] оценивается как [], мы также можем подставить это значение и обнаружить, что понимание списка снова уменьшается до []:
permute [x] = []
... чтолегко обобщается на возвращение [] для любого ввода.В рабочей версии, однако, используется следующее определение:
permute [] = [[]]
При окончательном сокращении последнего рекурсивного шага это заменяет следующие:
permute [x] = [ x:ps | ps <- permute []]
permute [x] = [ x:ps | ps <- [[]] ]
Поскольку ps привязан к чему-то с одним элементом, мы снова можем заменить напрямую:
permute [x] = (x:[])
То есть, просто говоря, что permute [x] = [x].