Acumuladores, conj y recursión

Question

He resuelto 45 problemas de 4clojure.com y noté un problema recurrente en la forma en que trato de resolver algunos problemas con la recurrencia y los acumuladores.

Trataré de explicar lo mejor que puedo hacer para terminar con soluciones fugly esperando que algunos Clojurers puedan "obtener" lo que no obtendré.

Por ejemplo, el problema 34 pide que se escriba una función (sin usar rango) tomando dos enteros como argumentos y creando un rango (sin usar el rango). Simplemente ponlo a hacer (... 1 7) y obtienes (1 2 3 4 5 6).

Ahora, esta pregunta no se trata de resolver este problema en particular.

¿Qué pasa si yo quiero para resolver esto usando recursion y un acumulador?

Mi proceso de pensamiento dice así:

• Tengo que escribir una función de tomar dos argumentos, comienzo con (fn [xy])

• Voy a tener que recursivo y tendré que hacer un seguimiento de una lista, usaré un acumulador, así que escribo una segunda función dentro del primero tomando un argumento adicional:

  (fn [xy]
  ((fn g [xy acc] ...) x y '())

(al parecer no puedo formatear correctamente ese código en Clojure SO !?)

Aquí ya no estoy seguro de hacerlo correctamente: la primera función debe tomar exactamente dos argumentos enteros (no es mi llamada) y no estoy seguro: si quiero usar un acumulador, ¿puedo usar un acumulador sin crear una función anidada?

entonces quiero conj, pero no puedo hacer:

(conj 0 1) 

por lo que hacen cosas extrañas para asegurarse de que tengo una primera secuencia y termino con esto:

(fn 
    [x y] 
    ((fn g [x y acc] (if (= x y) y (conj (conj acc (g (inc x) y acc)) x))) 
    x 
    y 
    '())) 

Pero entonces esto producir esto:

(1 (2 (3 4))) 

lugar de esto:

(1 2 3 4) 

Así que terminan haciendo un adicional aplanar y funciona pero es totalmente feo.

Empiezo a entender algunas cosas e incluso estoy empezando, en algunos casos, a "pensar" de una manera más acrítica, pero tengo un problema al escribir la solución.

Por ejemplo aquí me decidió:

• de usar un acumulador
• a Recurse incrementando x hasta que llega y

Pero termino con la monstruosidad anterior .

Hay una gran cantidad de manera de resolver este problema y, una vez más, que no es lo que busco.

lo que busco es cómo, después decidí contras/conj, utilice un acumulador, y recursivo, puedo terminar con esto (no escrito por mí):

#(loop [i %1 
     acc nil] 
    (if (<= %2 i) 
    (reverse acc) 
    (recur (inc i) (cons i acc)))) 

En lugar de esto :

((fn 
    f 
    [x y] 
    (flatten 
    ((fn 
    g 
    [x y acc] 
    (if (= x y) acc (conj (conj acc (g (inc x) y acc)) x))) 
    x 
    y 
    '()))) 
1 
4) 

tomo es un comienzo para ser capaz de resolver algunos problemas, pero estoy un poco decepcionado por las soluciones feas que tienden a producir ...

Answer 1

Creo que hay un par de cosas que aprender aquí.

primer, una especie de regla general: las funciones recursivas suelen tener un orden natural, y al agregar un acumulador se invierte eso. puede ver eso porque cuando se ejecuta una función recursiva "normal" (sin acumulador), hace algún trabajo para calcular un valor, luego recurre para generar la cola de la lista, finalmente termina con una lista vacía. en cambio, con un acumulador, comienza con la lista vacía y agrega cosas al frente; está creciendo en la otra dirección.

por lo general, cuando agrega un acumulador, obtiene un orden inverso.

ahora a menudo esto no importa. por ejemplo, si no está generando una secuencia, sino un valor que es la aplicación repetida de un operador conmutativo (como la suma o la multiplicación). entonces obtienes la misma respuesta de cualquier manera.

pero en su caso, va a importar. vas a obtener la lista revés:

(defn my-range-0 [lo hi] ; normal recursive solution 
    (if (= lo hi) 
    nil 
    (cons lo (my-range-0 (inc lo) hi)))) 

(deftest test-my-range-1 
    (is (= '(0 1 2) (my-range-0 0 3)))) 

(defn my-range-1 ; with an accumulator 
    ([lo hi] (my-range-1 lo hi nil)) 
    ([lo hi acc] 
    (if (= lo hi) 
     acc 
     (recur (inc lo) hi (cons lo acc))))) 

(deftest test-my-range-1 
    (is (= '(2 1 0) (my-range-1 0 3)))) ; oops! backwards! 

y con frecuencia lo mejor que puede hacer para solucionar este problema es simplemente invertir esa lista al final.

pero aquí hay una alternativa: podemos hacer el trabajo al revés. en lugar de incrementar el límite inferior se puede decremento el límite alto:

(defn my-range-2 
    ([lo hi] (my-range-2 lo hi nil)) 
    ([lo hi acc] 
    (if (= lo hi) 
     acc 
     (let [hi (dec hi)] 
     (recur lo hi (cons hi acc)))))) 

(deftest test-my-range-2 
    (is (= '(0 1 2) (my-range-2 0 3)))) ; back to the original order 

[nota - no hay otra forma de revertir las cosas más adelante; i no estructurar mi argumento muy bien]

segundo, como se puede ver en my-range-1 y my-range-2, una buena manera de escribir una función con un acumulador es como una función con dos conjuntos diferentes de argumentos. eso le da una implementación muy limpia (imho) sin la necesidad de funciones anidadas.

---

también tienen algunas preguntas más generales sobre secuencias, conj y similares. aquí, clojure es algo desordenado, pero también útil. arriba he estado dando una visión muy tradicional con listas basadas en contras. pero clojure te anima a utilizar otras secuencias. y a diferencia de las listas de contras, los vectores crecen hacia la derecha, no a la izquierda.por lo otra forma de revertir ese resultado es el uso de un vector:

(defn my-range-3 ; this looks like my-range-1 
    ([lo hi] (my-range-3 lo hi [])) 
    ([lo hi acc] 
    (if (= lo hi) 
     acc 
     (recur (inc lo) hi (conj acc lo))))) 

(deftest test-my-range-3 ; except that it works right! 
    (is (= [0 1 2] (my-range-3 0 3)))) 

aquí conj es la adición a la derecha. No hice uso de conj en my-range-1, por lo que aquí se re-escrito para ser más claro:

(defn my-range-4 ; my-range-1 written using conj instead of cons 
  ([lo hi] (my-range-4 lo hi nil)) 
  ([lo hi acc] 
    (if (= lo hi) 
      acc 
      (recur (inc lo) hi (conj acc lo))))) 

(deftest test-my-range-4 
    (is (= '(2 1 0) (my-range-4 0 3)))) 

nota que este código es muy similar a my-range-3 pero el resultado es al revés, ya que estamos empezando con una lista vacía, no es un vector vacío. en ambos casos, conj agrega el nuevo elemento en la posición "natural". para un vector que está a la derecha, pero para una lista está a la izquierda.

y se me acaba de ocurrir que puede que realmente no comprenda qué es una lista. básicamente, un cons crea un cuadro que contiene dos cosas (sus argumentos). el primero es el contenido y el segundo es el resto de la lista. entonces la lista (1 2 3) es básicamente (cons 1 (cons 2 (cons 3 nil))). en cambio, el vector [1 2 3] funciona más como una matriz (aunque creo que se implementa utilizando un árbol).

así que conj es un poco confuso porque la forma en que funciona depende del primer argumento. para obtener una lista, llama al cons y agrega elementos a la izquierda. pero para un vector extiende la matriz (-like thing) a la derecha. Además, tenga en cuenta que conj toma una secuencia existente como primer arg, y una cosa para agregar como segundo, mientras que cons es al revés (lo que se agrega es lo primero).

---

todo el código de seguridad disponibles en https://github.com/andrewcooke/clojure-lab

---

Actualización: Me volvió a escribir las pruebas para que el resultado esperado es una lista citado en los casos en que el código genera una lista. = comparará listas y vectores y devolverá verdadero si el contenido es el mismo, pero hacerlo explícito muestra más claramente lo que realmente está obteniendo en cada caso. tenga en cuenta que '(0 1 2) con un ' al frente es igual que (list 0 1 2) - el ' impide que se evalúe la lista (sin él, 0 se trataría como un comando).

Answer 2

Después de leer todo esto, yo Todavía no estoy seguro de por qué necesitarías un n acumulador.

((fn r [a b] 
    (if (<= a b) 
     (cons a (r (inc a) b)))) 
    2 4) 
=> (2 3 4) 

parece una solución recursiva bastante intuitiva. lo único que cambiaría en el código "real" es usar lazy-seq para que no se quede sin stack para grandes rangos.

cómo había llegado a esa solución:

Cuando se está pensando en usar la recursividad, me parece que ayuda a tratar de plantear el problema con los términos menor número posible de que se pueda imaginar, y tratar de la mano tanto como "trabajo" a la recursividad en sí.

En particular, si sospecha que puede eliminar uno o más argumentos/variables, ese es generalmente el camino a seguir, al menos si desea que el código sea fácil de comprender y depurar; a veces terminas comprometiendo la simplicidad a favor de la velocidad de ejecución o reduciendo el uso de la memoria.

En este caso, lo que pensé cuando comencé a escribir fue: "el primer argumento para la función es también el elemento de inicio del rango, y el último argumento es el último elemento". pensamiento recursivo es algo que tipo de tener que entrenarse para hacerlo, pero una solución bastante obvio, entonces, es decir: una gama [a, b] es una secuencia que comienza con el elemento a seguido de una gama de [a + 1, b]. Entonces, los rangos realmente pueden describirse recursivamente. El código que escribí es más o menos una implementación directa de esa idea.

adición:

he encontrado que al escribir código funcional, acumuladores (e índices) es mejor evitarlos. Algunos problemas los requieren, pero si puede encontrar una manera de deshacerse de ellos, generalmente estará mejor si lo hace.

adición 2:

En cuanto a las funciones recursivas y listas/secuencias, la forma más útil pensar al escribir ese tipo de código es el estado de su problema en términos de "el primer elemento (cabeza) de una lista "y" el resto de la lista (cola) ".

Answer 3

Si he resuelto esto utilizando un acumulador Me gustaría hacer algo como:

user=> (defn my-range [lb up c] 
     (if (= lb up) 
      c 
      (recur (inc lb) up (conj c lb)))) 
#'user/my-range 

luego llamar con

#(my-range % %2 []) 

Por supuesto, que haría uso de letfn o algo para moverse por no tener defn disponible.

Así que sí, necesita una función interna para usar el enfoque de acumulador.

Mi proceso de pensamiento es que una vez que haya terminado, la respuesta que quiero devolver estará en el acumulador. (Eso contrasta con su solución, donde hace mucho trabajo para encontrar la condición final). Así que busco mi condición final y si llegué, devuelvo el acumulador. De lo contrario, agrego el próximo artículo al acumulador y repito para un caso más pequeño. Entonces, solo hay dos cosas que averiguar, cuál es la condición final y qué quiero poner en el acumulador.

El uso de un vector ayuda mucho porque conj se agregará a él y no es necesario usar reverse.

I'm on 4clojure too, btw. He estado ocupado, así que me he retrasado últimamente.

Answer 4

Parece que su pregunta es más acerca de "cómo aprender", entonces hay un problema técnico/de código. Terminas escribiendo ese tipo de código porque de cualquier manera o fuente que aprendiste la programación en general o Clojure en específico ha creado una "carretera neuronal" en tu cerebro que te hace pensar en las soluciones de esta manera en particular y terminas escribiendo código Me gusta esto. Básicamente cada vez que enfrenta cualquier problema (en este caso particular recursividad y/o acumulación) termina usando esa "carretera neuronal" y siempre se le ocurre ese tipo de código.

La solución para deshacerse de esta "carretera neuronal" es dejar de escribir código por el momento, mantener el teclado alejado y comenzar a leer una gran cantidad de códigos existentes (desde soluciones existentes de problemas 4clojure hasta proyectos de código abierto en github) y piénsalo profundamente (incluso lee una función 2-3 veces para realmente dejar que se establezca en tu cerebro). De esta forma terminarías destruyendo tu "carretera neural" existente (que produce el código que escribes ahora) y crearás una nueva "autopista neuronal" que produciría el hermoso e idiomático código Clojure. Además, intente no pasar al código de mecanografía tan pronto como vea un problema, sino más bien tómese un tiempo para pensar clara y profundamente sobre el problema y las soluciones.

Answer 5

No puedo agregar a las ya buenas respuestas que ha recibido, pero responderé en general. A medida que avanza en el proceso de aprendizaje de Clojure, puede encontrar que muchas soluciones, aunque no todas, pueden resolverse utilizando Clojure incorporadas, como mapas, y también pensando en problemas en términos de secuencias. Esto no significa que no deba resolver las cosas recursivamente, pero escuchará, y creo que es un consejo sabio, que la recursión de Clojure es para resolver problemas de muy bajo nivel que no puede resolver de otra manera.

Ocurre una gran cantidad de procesamiento de archivos .csv, y recientemente recibí un comentario que nth crea dependencias.Sí, y el uso de mapas me permite obtener elementos para comparar por nombre y no por posición.

No voy a descartar el código que usa nth con los datos analizados clojure-csv en dos pequeñas aplicaciones que ya están en producción. Pero voy a pensar en cosas de una manera más secuencial la próxima vez.

Es difícil aprender de los libros que hablan sobre vectores y enésimo, repetición ... y así sucesivamente, y luego darse cuenta de que aprender Clojure te hace avanzar desde allí.

Una de las cosas que he encontrado que es buena para aprender Clojure, es que la comunidad es respetuosa y servicial. Después de todo, están ayudando a alguien cuyo primer idioma de aprendizaje fue Fortran IV en un CDC Cyber ​​con tarjetas perforadas, y cuyo primer lenguaje de programación comercial fue PL/I.