Блог

Это мой первый вопрос на этом сайте. Так что, если я груб или недостаточно формален, я уже сожалею.
В моем классе дискретной математики профессор показал нам эту функцию перестановки

 permute :: [a] -> [[a]]
permute [] = [[]]
permute xs = [y:zs| (y,ys) <- select xs, zs <- permute ys]

select :: [a] -> [(a,[a])]
select [] = []
select (x:xs) = (x,xs) : map((y,ys) ->(y,x:ys))(select xs)
  

Я не понял эту часть

 permute xs = [y:zs| (y,ys) <- select xs, zs <- permute ys]
  

Я пытался permute [1] четко понять, что в первой рекурсии select xs принимает [1] и возвращает [(1,[])] . Затем permute ys принимает [] , если я не ошибаюсь.

Во второй рекурсии select принимает [] и возвращает [] . Я где-то здесь потерялся. Как я вижу, он должен возвращаться [[1],[]] , но он возвращается [[1]] .
Я был бы очень рад, если кто-нибудь поможет.

Если вы вызовете permute [1] , то select [1] , вернет [(1, [])] , так что это означает, что понимание списка займет y = 1 и ys = [] . Затем мы вызываем permute [] , который возвращает [[]] . Таким образом, это означает, что zs потребуется только zs = [] . Таким образом, мы получим [ y : zs ] , что эквивалентно [ 1 : [] ] , и, таким образом [[]] .

Итак, поскольку zs <- permute [] и, следовательно, эквивалентно zs <- [[]] , то это означает, что он повторяется только один раз zs = [] .

Если вы permute [1,2] , то мы таким образом вызываем select [1,2] , и это возвращает [(1, [2]), (2, [1])] . Таким образом, это означает, что при понимании списка (y, ys) он будет «повторяться» дважды: один раз с y=1 помощью and ys=[2] ; а затем с y=2 помощью and ys=[1] . Для каждого значения для (y, ys) него будет затем вызываться permute . permute [1] [[1]] Вернется и вернется permute [2] [[2]] . Таким образом, это означает, что мы вернем список с: [ 1 : [2], 2 : [1]] , который, таким образом, эквивалентен [[1,2], [2,1]] .