La función de permutación recursiva siempre devuelve la lista vacía

Question

Estoy aprendiendo Haskell, y una de mis funciones de práctica era un recursivo simple permute. Adapté the solution described here y originalmente dieron este:

selections [] = [] 
selections (x:xs) = (x, xs) : [ (y, x:ys) | (y,ys) <- selections xs ] 

permute xs = [y:ps | (y,ys) <- selections xs, ps <- permute ys] 

(Sí, esto podría ser más corto, pero yo estaba pasando por lo explícito y claridad.)

Sin embargo, esta versión de permute siempre devuelve una lista vacía! Después agitando un poco, me tengo que trabajar cambiando a permute:

permute [] = [[]] 
permute xs = [y:ps | (y,ys) <- selections xs, ps <- permute ys] 

Sin embargo, todavía estoy perplejo en cuanto a ello la versión original siempre devuelve una lista vacía.

Answer 1

Bueno, los dos son obviamente muy similares, entonces ¿por qué no mirar en detalle dónde están en desacuerdo? La parte recursiva es exactamente la misma en ambos, así que primero podemos decir que ambas versiones hacen lo mismo en listas no vacías. Esto suena incorrecto porque dan resultados diferentes, pero en realidad es verdad porque realizan la misma operación en el resultado de la llamada recursiva.

El caso base de la versión correcta es permute [] = [[]], que se explica por sí mismo. El caso base de la primera versión, sin embargo, está implícito en la lista de comprensión. Dada la definición:

permute xs = [y:ps | (y,ys) <- selections xs, ps <- permute ys] 

... podemos sustituir en []xs para ver lo que sucede:

permute [] = [y:ps | (y,ys) <- selections [], ps <- permute ys] 

dada la definición selections [] = [], podemos simplificar a:

permute [] = [y:ps | (y,ys) <- [], ps <- permute ys] 

... de lo que está claro que no se generan resultados, por lo que toda la lista de comprensión está vacía, simplificándose a solo:

permute [] = [] 

Ahora, consideremos el último paso antes de la base recursiva, sustituyendo [x] como argumento:

permute [x] = [y:ps | (y,ys) <- selections [x], ps <- permute ys] 

La definición de selections es selections (x:xs) = (x, xs) : [ (y, x:ys) | (y,ys) <- selections xs ], sustituyendo en [x] da selections [x] = (x, []) : [ (y, x:ys) | (y,ys) <- selections [] ]. selections [] evalúa a [], por lo que toda la lista de comprensión se reduce a [], dando selections [x] = (x, []) : [] o solo selections [x] = [(x, [])].

Sustituto que en permute que el anterior:

permute [x] = [y:ps | (y,ys) <- [(x, [])], ps <- permute ys] 

Sólo hay un elemento de la lista, por lo que puede pasar por alto la unión y sustituir directamente la comprensión <-:

permute [x] = [y:ps | (y,ys) = (x, []), ps <- permute ys] 

permute [x] = [ x:ps | ps <- permute []] 

Una vez establecido que permute [] evalúa a [], podemos sustituir eso también y encontrar que la lista de comprensión nuevamente se reduce a []:

permute [x] = [] 

... que se generaliza fácilmente para devolver [] para cualquier entrada. El de trabajo versión, sin embargo, utiliza la siguiente definición:

permute [] = [[]] 

En la reducción final de la etapa de recursiva final, esto cambia las sustituciones a lo siguiente:

permute [x] = [ x:ps | ps <- permute []] 

permute [x] = [ x:ps | ps <- [[]] ] 

Desde ps es ser encuadernado a algo con un solo elemento, podemos volver a sustituirlo directamente:

permute [x] = (x:[]) 

Cual es solo diciendo que permute [x] = [x].