scala - recursivas - recursividad programacion

Unión de conjunto recursivo: ¿cómo funciona realmente?

Question

Actualmente estoy tomando el curso de Scala en Coursera en mi tiempo libre después del trabajo, en un intento por finalmente probar la programación funcional. Actualmente estoy trabajando en una tarea en la que se supone que debemos "calcular" la unión de dos conjuntos que contienen algún objeto. Estoy omitiendo los detalles intencionalmente, ya que no es realmente importante para lo que estoy tratando de hacer aquí. Lo que es relevante, sin embargo, es que los conjuntos se definen como árboles binarios, con cada nodo que contiene un elemento y dos subárboles.

Siendo ese el caso; la union ejemplo en la conferencia es la siguiente:

def union(other:BTSet) :BTSet = ((left union right) union other) incl element

Pregunta 1: francamente, incluso después de haber leído las preguntas frecuentes relevantes y otros temas del foro, todavía no entiendo cómo y por qué funciona esta función. No hay absolutamente ninguna "acción" hecha aquí en la implementación de la unión además de agregar (la llamada incl ) el elemento en el nodo principal, simplemente se llama una y otra vez. Estaría muy agradecido de alguna explicación ...

Pregunta 2: El foro del curso contiene muchas publicaciones que afirman que esta solución no es eficiente en absoluto y que no es lo suficientemente buena. Al ver que no entiendo cómo funciona para empezar, realmente no entiendo por qué no es lo suficientemente bueno.

TENGA EN CUENTA que, de ninguna manera, solicito un alerón para la solución de asignación. Estoy más que dispuesto a "hacer el trabajo para el grado", pero simplemente no entiendo lo que se supone que debo hacer aquí. No creo que las instrucciones y orientación proporcionadas en el curso sean adecuadas para entender las peculiaridades de la programación funcional, por lo tanto, agradezco cualquier comentario / respuesta que aborde la forma de pensar correctamente y no cómo codificar correctamente .

Answer 1

Estoy haciendo el mismo curso, y la implementación anterior de la union resultó ser extremadamente ineficiente.

Se me ocurrió la siguiente solución no tan funcional para crear una unión de conjuntos de árbol binario, que es MUCHO más eficiente:

def union(that: BTSet): BTSet = {
  var result:BTSet = this
  that.foreach(element => result = result.incl(element))
  result
}

Answer 2

No puedes entender los algoritmos recursivos a menos que mires el caso base. De hecho, a menudo, la clave del entendimiento reside en la comprensión del caso base primero. Como el caso base no se muestra (probablemente porque no notó que hay uno en primer lugar), no hay comprensión posible.

Answer 3

Por lo tanto, en base a todas las respuestas anteriores, creo que el verdadero caballo de batalla es incl y la forma recursiva de llamar a union es solo para examinar todos los elementos en los conjuntos.

Se me ocurrió la siguiente implementación de unión, ¿es esto mejor?

def union(other:BTSet) :BTSet = right union (left union (other incl element))

Answer 4

Supongo que incl insertar un elemento en un conjunto existente? Si es así, ahí es donde está sucediendo todo el trabajo real.

La definición de unión es el conjunto que incluye todo en cualquier conjunto de entrada. Dado dos conjuntos almacenados como árboles binarios, si toma las uniones del primer conjunto con las ramas del segundo, el único elemento en el que podría faltar el resultado es el elemento en el nodo raíz del segundo árbol, por lo que si insertas ese elemento tienes la unión de ambos conjuntos de entrada.

Es solo una manera muy ineficiente de insertar cada elemento de ambos conjuntos en un nuevo conjunto que comienza vacío. Es de suponer que los duplicados se descartan por el incl , por lo que el resultado es la unión de las dos entradas.

Tal vez sería útil ignorar la estructura del árbol por el momento; no es realmente importante para el algoritmo esencial. Digamos que tenemos conjuntos matemáticos abstractos. Dado un conjunto de entrada con elementos desconocidos, podemos hacer dos cosas:

• Agregue un elemento (que no hace nada si el elemento ya estaba presente)
• Compruebe si el conjunto no está vacío y, si es así, descompóngalo en un solo elemento y dos subconjuntos disjuntos.

Para tomar la unión de dos conjuntos {1,2} y {2,3}, comenzamos por descomponer el primer conjunto en el elemento 1 y los subconjuntos {} y {2}. Recursivamente tomamos la unión de {}, {2} y {2,3} usando el mismo proceso, luego insertamos 1 en el resultado.

En cada paso, el problema se reduce de una operación de unión a dos operaciones de unión en entradas más pequeñas; un algoritmo estándar de dividir y vencer. Al alcanzar la unión de un conjunto simple {x} y un conjunto vacío {}, la unión es trivialmente {x}, que luego se devuelve a la cadena.

La estructura de árbol se utiliza para permitir el análisis / descomposición de casos en conjuntos más pequeños y para hacer la inserción más eficiente. Lo mismo podría hacerse utilizando otras estructuras de datos, como las listas que se dividen a la mitad para la descomposición y con la inserción realizada mediante un control exhaustivo de la singularidad. Para tomar la unión de manera eficiente se requiere un algoritmo que sea un poco más inteligente, y se aprovecha de la estructura utilizada para almacenar los elementos.

Answer 5

  2
 / /  union  4
1   3

((1 union 3) union 4) incl 2
  ^^^^^^^^^......................................assume it works

(((E union E) union 3 incl 1) union 4) incl 2
   ^^^^^^^^^.....................................still E

(E union E) union 3 incl 1 = E union 3 incl 1 = 3 incl 1

El siguiente subárbol debe ser 3 incluido 1

(  3             ) 
(    /   union D ) incl 2
(      1         )


(((1 union E) union 4) incl 3) incl 2
   ^^^^^^^^^.......................................expand

(((( (E union E) union E) incl 1) union 4) incl 3) incl 2
      ^^^^^^^^^^^^^^^^^^^^^^^^^^..................still 1

((1 union 4) incl 3) incl 2
   ^^^^^^^^......................................continue

((((E union E) union 4) incl 1) incl 3) incl 2
   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^..........expand 1 union 4

((4 incl 1) incl 3) incl 2
  ^^^^^^^^^^^^^^^^^^^^^^^^^............Final union result 

Gracias @Rex Kerr dibuja los pasos. Sustituyo el segundo paso con el paso de tiempo de ejecución real, que puede dar una descripción más clara de la función de union Scala.

Answer 6

  A
 / /  union  D
B   C

((B union C) union D) incl A
  ^^^^^^^^^......................................assume it works

(  B             )
(    /   union D ) incl A
(     C          )

(((0 union C) union D) incl B) incl A
   ^^^^^^^^^.....................................just C

(((C union D) incl B) incl A
   ^^^^^^^^^.....................................expand

((((0 union 0) union D) incl C) incl B) incl A
    ^^^^^^^^^....................................just 0

(((0 union D) incl C) incl B) incl A
   ^^^^^^^^^.....................................just D

((D incl C) incl B) incl A
^^^^^^^^^^^^^^^^^^^^^^^^^^.......................all incl now

Solo escríbelo paso a paso. Ahora ves que la unión se reduce a un grupo de declaraciones incl aplicadas al argumento de la derecha.