Acumuladores, conj y recursividad

Question

He resuelto 45 problemas de 4clojure.com y me di cuenta de un problema recurrente en la forma en que me tratan de resolver algunos de los problemas mediante la recursividad y acumuladores.

Voy a intentar explicar lo mejor que puedo lo que estoy haciendo para terminar con fugly soluciones con la esperanza de que algunos Clojurers sería "conseguir" lo que yo estoy haciendo.

Por ejemplo, la resolución 34 pide escribir una función (sin usar rango de a ) tomar dos enteros como argumentos y crea una variedad (sin el uso de la gama).Simplemente coloque hacer (...1 7) y (1 2 3 4 5 6).

Ahora esta pregunta no es acerca de cómo resolver este problema en particular.

Lo que si me quiero para resolver este uso de la recursividad y un acumulador?

Mi proceso de pensamiento va como esto:

• Necesito escribir una función que recibe dos argumentos, voy a empezar con (fn [x, y] )

• Voy a tener que recurse y voy a tener que seguir la pista de una lista, voy a utilizar un acumulador, así que tengo que escribir una 2ª función dentro de la primera que toma un argumento adicional:

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

(al parecer, yo no puedo correctamente el formato que Usa código ASÍ!?)

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

A continuación, quiero conj, pero no puedo hacerlo:

(conj 0 1)

así que tengo que hacer cosas raras para asegurarse de que tiene una secuencia de primera 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 luego esta el de producir este:

(1 (2 (3 4)))

En lugar de esto:

(1 2 3 4)

Así que termino haciendo un adicional de aplanar y funciona, pero es totalmente feo.

Estoy empezando a entender un par de cosas y estoy incluso de partida, en algunos casos, a "pensar" en un más clojuresque manera, pero tengo un problema la elaboración de la solución.

Por ejemplo, aquí he decidido:

• el uso de un acumulador
• buscar recursivamente por el incremento de los x hasta que llega y

Pero termino con la monstruosidad de arriba.

Hay un mucho de manera que para resolver este problema y, una vez más, no es lo que yo busco.

Lo que yo busco es cómo, después me decidí a cons/conj, el uso de un acumulador, y recurse, 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)

Puedo tomar es un comienzo para ser capaz de resolver un par de problemas, pero estoy un poco decepcionado por el feo soluciones que tienden a producir...

Answer 1

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

primero, una especie de regla general - funciones recursivas normalmente tienen un orden natural, y la adición de un acumulador que invierte.se puede ver que debido a que cuando una persona "normal" (sin acumulador) función recursiva se ejecuta, se hace un poco de trabajo para calcular un valor, luego se recorre el árbol para generar la cola de la lista, finalmente, termina con una lista vacía.en contraste, con un acumulador, de empezar con la lista vacía y agregar cosas a la frente - está creciendo en la otra dirección.

por lo general, cuando se agrega un acumulador, se obtiene un orden invertido.

ahora, a menudo, esto no importa.por ejemplo, si se está generando no es una secuencia, sino un valor que es la aplicación repetida de un conmutativa operador (como suma o multiplicación).luego de obtener la misma respuesta en ambos sentidos.

pero en su caso, se va a importar.usted va a obtener la lista hacia atrá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, a menudo, el mejor que usted puede hacer para corregir esto es sólo revertir esa lista al final.

pero aquí hay una alternativa - en realidad podemos hacer el trabajo hacia atrás.en lugar de el incremento de los el límite inferior 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 manera de revertir las cosas de abajo;yo no la estructura de 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 una función con dos conjuntos diferentes de argumentos.que le da un aspecto muy limpio (en mi humilde opinión) la ejecución sin la necesidad de funciones anidadas.

---

también tiene algunas preguntas más generales sobre las secuencias, conj y el como.aquí clojure es una especie de desorden, pero también es útil.anteriormente he estado dando una muy tradicional que ver con los contras basado en listas.pero clojure promueve el uso de otras secuencias.y a diferencia de los contras listas, vectores crecer a la derecha, no la izquierda.así otro la 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.yo no lo uso conj en my-range-1, así que aquí está 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))))

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

y se me acaba de ocurrir que usted no puede realmente entender lo que es una lista.básicamente un cons crea una caja que contiene dos cosas (sus argumentos).el primero es el contenido y el segundo es el resto de la lista.así que la lista (1 2 3) es, básicamente, (cons 1 (cons 2 (cons 3 nil))).en contraste, el vector [1 2 3] funciona más como una matriz (aunque creo que es implementado usando un árbol).

así conj es un poco confuso, porque la forma en que funciona depende del primer argumento.para una lista de llamadas cons y así añade cosas a la izquierda.pero para un vector se extiende la matriz(-como la cosa) a la derecha.también, tenga en cuenta que conj toma una secuencia existente como primer argumento, y algo más para agregar como segundo, mientras que cons es a la inversa (cosa que añadir que ocurra primero).

---

todo lo anterior código disponible en https://github.com/andrewcooke/clojure-lab

---

actualización:reescribí las pruebas, de manera que el resultado esperado es un citada lista en los casos en que el código se genera una lista. = se comparan las listas y vectores y devuelva true si el contenido es el mismo, pero se hace explícito se muestra más claramente lo que usted está consiguiendo realmente en cada caso.tenga en cuenta que '(0 1 2) con un ' en el frente es igual (list 0 1 2) - la ' deja la lista de la que está siendo evaluado (sin ella, 0 sería tratado como un comando).

Answer 2

Después de leer todo eso, todavía no estoy seguro de por qué necesitarías un 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 pila para grandes rangos.

cómo llegué a esa solución:

Cuando está pensando en usar la recursión, me parece que ayuda a probar el problema con los pocos términos posibles que puede pensar, y tratar de entregar la mayor cantidad de "trabajo" a la recursión misma.

En particular, si sospecha que puede colocar uno o más argumentos / variables, generalmente es la forma de ir, al menos si desea que el código sea fácil de entender y depurar; A veces terminas comprometiendo la simplicidad a favor de la velocidad de ejecución o la reducción del uso de la memoria.

En este caso, lo que pensé cuando comencé a escribir fue: "El primer argumento a la función es también el elemento de inicio del rango, y el último argumento es el último elemento". El pensamiento recursivo es algo que tiene que entrenarse para hacer, pero una solución bastante obvia es decir: una rango de [a, b] es una secuencia que comienza con el elemento a seguido de A RANGO de [a + 1, b]. Así que los rangos pueden ser descritos recursivamente. El código que escribí es una implementación directa de esa idea.

addendum:

He encontrado que al escribir el código funcional, los acumuladores (e indexos) se evitan mejor. Algunos problemas lo requieren, pero si puedes encontrar una manera de deshacerse de ellos, generalmente estás mejor si lo haces.

addendum 2:

Con respecto a las funciones recursivas y las listas / secuencias, la forma más útil de pensar cuando se escribe ese tipo de código es indicar su problema en términos de "El primer elemento (cabeza) de una lista" y "El resto de la lista (cola).

Answer 3

No puedo agregar a las ya buenas respuestas que ha recibido, pero voy a responder en general.Como usted va a través de la Clojure proceso de aprendizaje, usted puede encontrar que muchas, pero no todas las soluciones puede ser resuelto mediante la Clojure construido-ins, como el mapa y también pensando en los problemas en términos de secuencias.Esto no significa que usted no debe resolver las cosas de forma recursiva, pero usted va a escuchar-y creo que es ser sabios consejos-que Clojure la recursividad es para resolver problemas de muy bajo nivel de problemas que no puede resolver de otra manera.

Se me ocurre hacer un montón de .archivo csv de procesamiento, y recientemente ha recibido un comentario que enésima crea dependencias.Lo hace, y el uso de los mapas me permita obtener elementos de comparación por nombre y no por su posición.

No voy a tirar el código que usa el enésimo con clojure-csv datos analizados en dos pequeñas aplicaciones que ya están en producción.Pero yo voy a pensar acerca de las cosas más sequency manera que la siguiente vez.

Es difícil aprender de los libros que hablan de vectores y n, lazo ..se repiten y así sucesivamente, y luego darse cuenta de aprendizaje Clojure crece hacia adelante a partir de ahí.

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

Answer 4

Si he resuelto mediante 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

a continuación, llame a con

#(my-range % %2 [])

Por supuesto, yo uso la letfn o de algo para conseguir alrededor no tener defn disponible.

Así que, sí, usted no necesita un interior de función para utilizar el acumulador de enfoque.

Mi proceso de pensamiento es que una vez que he terminado la respuesta quiero regreso será en el acumulador.(Que contrasta con su solución, donde usted hace un montón de trabajo en la búsqueda de la terminación-de la condición.) Por eso busco mi final-condición y si he llegado hasta aquí, puedo devolver el acumulador.De lo contrario me tachuela en el siguiente punto de la acumulador y se repiten para un caso menor.Tan sólo hay 2 cosas a la figura hacia fuera, lo que al final es condición, y lo quiero poner en el acumulador.

El uso de un vector ayuda mucho, porque conj se anexará a ello y no hay ninguna necesidad de utilizar reverse.

Estoy en 4clojure demasiado, por cierto.He estado muy ocupado así que me he quedado a la zaga de los últimos tiempos.

Answer 5

Parece que su pregunta es más sobre "cómo aprender", un problema técnico / código. Usted termina escribiendo ese tipo de código porque de la manera o fuente que aprendió la programación en general o en ello, en específicas, ha creado una "carretera neural" en su cerebro que le hace pensar en las soluciones de esta manera en particular y usted termina de escribir código como esto. Básicamente, cada vez que enfrentas algún problema (en esta recursión de caso y / o acumulación particular), terminas usando esa "carretera neural" y siempre se le ocurren ese tipo de código.

La solución para deshacerse de esta "carretera neural" es dejar de escribir el código por el momento, mantener ese teclado y comenzar a leer un montón de código de Clojure existente (desde soluciones existentes de 4CLOJURE problema hasta proyectos de código abierto en GitHub) y piense en ello profundamente (incluso lea una función 2-3 veces para que realmente lo deje reposar en su cerebro). De esta manera, terminaría destruyendo su "carretera neural" existente (que produce el código que escribe ahora) y creará una nueva "carretera neural" que produciría el código de Clojure Hermoso e idiomático. Además, trate de no saltar al código de escritura tan pronto como viste un problema, más bien, darse un tiempo para pensar con claridad y profundamente sobre el problema y las soluciones.