Acumuladores, conj e recursão

StackOverflow https://stackoverflow.com//questions/10666228

Pergunta

Resolvi 45 problemas do 4clojure.com e notei um problema recorrente na forma como tento resolver alguns problemas usando recursão e acumuladores.

Tentarei explicar o melhor que puder o que estou fazendo para acabar com soluções horríveis, esperando que alguns Clojurers "conseguissem" o que não estou conseguindo.

Por exemplo, o problema 34 pede para escrever uma função (sem usar faixa) pegando dois números inteiros como argumentos e cria um intervalo (sem usar intervalo).Simplificando, você faz (...1 7) e você obtém (1 2 3 4 5 6).

Agora, esta questão não é sobre como resolver este problema específico.

E se eu querer resolver isso usando recursão e um acumulador?

Meu processo de pensamento é assim:

  • Preciso escrever uma função com dois argumentos, começo com (fn [x y] )

  • Vou precisar recorrer e acompanhar uma lista, vou usar um acumulador, então escrevo uma segunda função dentro da primeira pegando um argumento adicional:

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

(aparentemente não consigo formatar corretamente o código Clojure no SO!?)

Aqui já não tenho certeza se estou fazendo corretamente:a primeira função deve pegue exatamente dois argumentos inteiros (não minha chamada) e não tenho certeza:se eu quiser usar um acumulador, posso usar um acumulador sem criar uma função aninhada?

Então eu quero conj, mas não posso fazer:

(conj 0 1)

então eu faço coisas estranhas para ter certeza de que tenho uma sequência primeiro e acabo com isto:

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

Mas então isso produz isto:

(1 (2 (3 4)))

Em vez disso:

(1 2 3 4)

Então acabo fazendo um adicional achatar e funciona, mas é totalmente feio.

Estou começando a entender algumas coisas e até começando, em alguns casos, a "pensar" de uma forma mais clojuresca, mas estou com um problema para escrever a solução.

Por exemplo aqui eu decidi:

  • usar um acumulador
  • recorrer aumentando x até chegar sim

Mas acabo com a monstruosidade acima.

Há um muito de forma a resolver este problema e, mais uma vez, não é isso que procuro.

O que procuro é como, depois de decidir contras/conj, usar um acumulador e recorrer, posso acabar com isso (não escrito por mim):

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

Em vez disso:

((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)

Acho que é um começo conseguir resolver alguns problemas, mas estou um pouco decepcionado com as soluções feias que costumo produzir...

Foi útil?

Solução

acho que há algumas coisas para aprender aqui.

primeiro, uma espécie de regra geral - funções recursivas normalmente têm uma ordem natural e adicionar um acumulador inverte isso.você pode ver isso porque quando um "normal" (sem acumulador) a função recursiva é executada, ela realiza algum trabalho para calcular um valor e, em seguida, recorre para gerar o final da lista, terminando finalmente com uma lista vazia.em contraste, com um acumulador, você começa com a lista vazia e adiciona coisas na frente - ela está crescendo na outra direção.

normalmente, quando você adiciona um acumulador, obtém uma ordem inversa.

agora, muitas vezes isso não importa.por exemplo, se você não estiver gerando uma sequência, mas um valor que é a aplicação repetida de um comutativo operador (como adição ou multiplicação).então você obtém a mesma resposta de qualquer maneira.

mas no seu caso, isso vai importar.você obterá a lista ao contrário:

(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!

e muitas vezes o melhor que você pode fazer para corrigir isso é simplesmente inverter a lista no final.

mas aqui há uma alternativa - podemos realmente fazer o trabalho de trás para frente.em vez de incrementando o limite baixo que você pode diminuir o limite superior:

(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 – há outra maneira de reverter as coisas abaixo;não estruturei muito bem meu argumento]

segundo, como você pode ver em my-range-1 e my-range-2, uma boa maneira de escrever uma função com um acumulador é como uma função com dois conjuntos diferentes de argumentos.isso oferece uma implementação muito limpa (imho), sem a necessidade de funções aninhadas.

você também tem algumas perguntas mais gerais sobre sequências, conj e similar.aqui o clojure é meio confuso, mas também útil.acima, tenho apresentado uma visão muito tradicional com listas baseadas em contras.mas o clojure incentiva você a usar outras sequências.e diferentemente das listas de contras, os vetores crescem para a direita, não para a esquerda.então outro maneira de reverter esse resultado é usar um vetor:

(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))))

aqui conj está adicionando à direita.eu não usei conj em my-range-1, então aqui está reescrito para ficar mais 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))))

observe que este código parece muito igual a my-range-3 mas o resultado é inverso porque estamos começando com uma lista vazia, não com um vetor vazio.em ambos os casos, conj adiciona o novo elemento na posição "natural".para um vetor está à direita, mas para uma lista está à esquerda.

e me ocorreu que você pode não entender realmente o que é uma lista.basicamente um cons cria uma caixa contendo duas coisas (seus argumentos).o primeiro é o conteúdo e o segundo é o resto da lista.então a lista (1 2 3) é basicamente (cons 1 (cons 2 (cons 3 nil))).em contraste, o vetor [1 2 3] funciona mais como um array (embora eu ache que seja implementado usando uma árvore).

então conj é um pouco confuso porque a forma como funciona depende do primeiro argumento.para uma lista, ele chama cons e assim adiciona coisas à esquerda.mas para um vetor ele estende o array (como algo) para a direita.também, observe que conj pega uma sequência existente como primeiro argumento e algo para adicionar como segundo, enquanto cons é o inverso (a coisa a adicionar vem primeiro).

todo o código acima disponível em https://github.com/andrewcooke/clojure-lab

atualizar:reescrevi os testes para que o resultado esperado seja uma lista entre aspas nos casos em que o código gera uma lista. = comparará listas e vetores e retornará verdadeiro se o conteúdo for o mesmo, mas torná-lo explícito mostra mais claramente o que você realmente está obtendo em cada caso.Observe que '(0 1 2) com um ' na frente é igual (list 0 1 2) - o ' impede que a lista seja avaliada (sem ela, 0 seria tratado como um comando).

Outras dicas

Depois de ler tudo isso, ainda não sei por que você precisaria de um acumulador.

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

parece uma solução recursiva bastante intuitiva.a única coisa que eu mudaria no código "real" é usar o lazy-seq para que você não fique sem pilha para intervalos grandes.

como cheguei a essa solução:

Quando você está pensando em usar a recursão, acho que ajuda tentar expor o problema com o menor número possível de termos que você puder imaginar e tentar transferir o máximo de "trabalho" para a recursão em si.

Em particular, se você suspeita que pode descartar um ou mais argumentos/variáveis, esse geralmente é o caminho a seguir - pelo menos se você deseja que o código seja fácil de entender e depurar;às vezes você acaba comprometendo a simplicidade em favor da velocidade de execução ou reduzindo o uso de memória.

Nesse caso, o que pensei quando comecei a escrever foi:"o primeiro argumento da função também é o elemento inicial do intervalo, e o último argumento é o último elemento".O pensamento recursivo é algo que você precisa treinar para fazer, mas uma solução bastante óbvia é dizer:a faixa [a, b] é uma sequência começando com o elemento a seguido pela a faixa de [a + 1, b].Portanto, os intervalos podem de fato ser descritos recursivamente.O código que escrevi é praticamente uma implementação direta dessa ideia.

termo aditivo:

Descobri que, ao escrever código funcional, é melhor evitar acumuladores (e índices).Alguns problemas exigem isso, mas se você conseguir encontrar uma maneira de se livrar deles, geralmente será melhor fazê-lo.

adendo 2:

Em relação a funções recursivas e listas/sequências, o A maneira mais útil de pensar ao escrever esse tipo de código é declarar seu problema em termos de "o primeiro item (cabeça) de uma lista" e "o resto da lista (cauda)".

Não posso acrescentar nada às já boas respostas que você recebeu, mas responderei de maneira geral.À medida que você avança no processo de aprendizagem do Clojure, você descobrirá que muitas, mas não todas as soluções, podem ser resolvidas usando os recursos integrados do Clojure, como mapa e também pensando nos problemas em termos de sequências.Isso não significa que você não deva resolver as coisas recursivamente, mas você ouvirá - e acredito que seja um conselho sábio - que a recursão do Clojure serve para resolver problemas de nível muito baixo que você não pode resolver de outra maneira.

Acontece que faço muito processamento de arquivos .csv e recentemente recebi um comentário de que nth cria dependências.Sim, e o uso de mapas pode me permitir obter elementos para comparação por nome e não por posição.

Não vou jogar fora o código que usa nth com dados analisados ​​pelo clojure-csv em dois pequenos aplicativos já em produção.Mas vou pensar nas coisas de uma forma mais sequencial na próxima vez.

É difícil aprender com livros que falam sobre vetores e enésimo, loop..recorrer e assim por diante, e então perceber que aprender Clojure faz você avançar a partir daí.

Uma das coisas que descobri que é bom em aprender Clojure é que a comunidade é respeitosa e prestativa.Afinal, eles estão ajudando alguém cuja primeira linguagem de aprendizagem foi Fortran IV em um CDC Cyber ​​com cartões perfurados, e cuja primeira linguagem de programação comercial foi PL/I.

Se eu resolvesse isso usando um acumulador, faria algo como:

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

então ligue com

#(my-range % %2 [])

Claro, eu usaria letfn ou algo para contornar não ter defn disponível.

Então sim, você precisa de uma função interna para usar a abordagem do acumulador.

Meu processo de pensamento é que, assim que terminar, a resposta que quero retornar estará no acumulador.(Isso contrasta com a sua solução, onde você trabalha muito para encontrar a condição final.) Então procuro minha condição final e, se a alcancei, devolvo o acumulador.Caso contrário, coloco o próximo item no acumulador e recorro a um caso menor.Portanto, há apenas duas coisas para descobrir: qual é a condição final e o que quero colocar no acumulador.

Usar um vetor ajuda muito porque conj será anexado a ele e não há necessidade de usar reverse.

Estou no 4clojure também, por falar nisso.Tenho estado ocupado, então fiquei para trás ultimamente.

Parece que sua pergunta é mais sobre "como aprender" do que sobre um problema técnico/de código.Você acaba escrevendo esse tipo de código porque de qualquer forma ou fonte que você aprendeu a programar em geral ou Clojure em específico criou uma "rodovia neural" em seu cérebro que faz você pensar nas soluções dessa maneira específica e você acaba escrevendo código assim.Basicamente sempre que você enfrenta algum problema (neste caso específico recursão e/ou acumulação) você acaba usando aquela "rodovia neural" e sempre surge com esse tipo de código.

A solução para se livrar dessa "rodovia neural" é parar de escrever código por enquanto, manter o teclado afastado e começar a ler muitos códigos clojure existentes (desde soluções existentes do problema 4clojure até projetos de código aberto no github) e pensar sobre profundamente (até mesmo leia uma função 2 a 3 vezes para realmente deixá-la se estabelecer em seu cérebro).Dessa forma, você acabaria destruindo sua "rodovia neural" existente (que produz o código que você escreve agora) e criaria uma nova "rodovia neural" que produziria o belo e idiomático código Clojure.Além disso, tente não começar a digitar o código assim que encontrar um problema; em vez disso, reserve um tempo para pensar clara e profundamente sobre o problema e as soluções.

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top