Taverna do Kiko

#ChallengeAccepted: FOR Recursivo

Kaique Garcia's photo
Kaique Garcia
·

15 min read

Faz poucas horas que lancei o artigo Estruturas de Controle - FOR aqui no blog, e o fato é que eu não fiz nenhuma reimplementação de estrutura dessa vez. Fiz o artigo nas pressas, precisei encerrar rápido pois minha esposa estava quase surtando com minhas filhas na sala, rs.

E não, isso não era uma desculpa contra minha capacidade, apenas contra o tempo mesmo. Foi falando sobre isso com outro dev que fui desafiado a fazer uma implementação de FOR usando recursividade e seguindo a semântica que eu sugeri no artigo, afinal, eu fui bem ríspido ao falar que o PHP não implementou a semântica clara.

Ou seja, foi praticamente um "faz melhor aí então".

Semanticamente falando, eu consigo fazer melhor sim. Mas acho difícil superar o desempenho de uma estrutura nativa com uma implementação a nível de aplicação. Talvez uma extensão em C seria mais eficaz... Mas o ponto não é esse: vamos usar recursão e semântica.

Ok, Kiko, então qual é o primeiro passo pra resolver esse desafio?

1. Test-Driven Design (TDD)

Eu já mencionei sobre isso no meu primeiro artigo, Coding Dojo. Eu gosto de seguir esse padrão, principalmente quando estamos falando de desafios. Mas para fazer isso nós precisamos de um ambiente com as ferramentas de teste instaladas.

E bem... Eu não estou a fim de escrever esse ambiente do zero agora (preparar Docker, rodar composer pra subir o PHPUnit, preparar um namespace pro source seguindo PSR-4, etc). Então vou usar um ambiente que deixei pronto pra galera: meu repositório base de coding dojo.

1.1. Instalação

Para usar meu repositório de coding dojo é bem fácil, mas com alguns pré-requisitos pra rodar:

  • Ter o Git instalado;
  • Ter o Docker instalado.

Se você não tem um desses dois, os links que coloquei aí em cima são guias de instalação deles para cada sistema operacional.

Enfim, instalando os dois ambientes, basta clonar o repositório na pasta desejada e mandar servir o Docker:

  • git clone git@github.com:kaiquegarcia/dojo-php.git (vai criar a pasta dojo-php a partir de onde você executou o comando no terminal);
  • cd dojo-php;
  • docker-compose up -d (se estiver no Windows/Mac, lembre de iniciar o Docker Desktop antes desse comando. O Docker Engine precisa estar rodando pra isso funcionar).

Pode demorar um pouco para instalar tudo no docker-compose (se tiver algum problema, joga aí nos comentários). Mas depois disso, você já terminou de instalar tudo.

2. Preparando o espaço do desafio

Como isso aqui não é, de fato, uma edição de coding dojo, eu vou criar mais uma pasta de exemplo (Example2). Nela, vou adicionar um readme.md com a descrição do desafio, que vai ser a introdução que soltei nesse artigo, hehe.

* Pronto, comitei.

3. Escrevendo a sugestão de teste

E aqui finalmente vamos começar o TDD: escreve um teste, imaginando como você quer que a implementação funcione. Sua implementação precisa funcionar de tal forma que você possa validar que cada execução está funcionando, portanto, vamos precisar de entradas e resultados esperados.

Como o ambiente de testes já está preparado, a gente só precisa escrever uma classe filha da classe Tests\TestCase.

Mas Kiko, o que você vai testar?

Bem, a gente pode testar os três cases que eu gerei no artigo anterior, que foram:

  1. Contar de 1 a 10;
  2. Contar de 10 a 1;
  3. Pegar os primeiros 10 números pares a partir do número 150.

Se a solução do for funcionar para os três cases, assumirei como desafio concluído.

Ok, faz sentido... Mas e como vai ficar a escrita, Kiko?

Pretendo fazer um método de teste para cada um desses cases... E quanto a escrita do código, para seguir a semântica PARA (entrada) ENQUANTO (condiçãoForVerdade) FAÇA (isso) E DEPOIS (aquilo), penso em criar uma classe chamada RFor (Recursive For), que seguirá o seguinte fluxo de chamadas:

  • construtor: recebe os parâmetros de entrada (new RFor(['contador' => 1]))...

Opa, peraí, Kiko! Passar array no construtor??

Eu sei, não é a melhor implementação... Mas esse é o lance do TDD: as melhorias vem depois! Foca em fazer passar, beleza? Então vamos continuar:

  • construtor (...);
  • depois método whileTrue, recebendo a condição necessária para executar cada loop. No caso, como essa condição será um callable, é interessante injetar no argumento da função o próprio objeto ($this), para que ela possa ler/manipular os dados de entrada;
  • em seguida, o método doThis, que vai receber a ação feita em cada loop, sendo mais um callable;
  • posteriormente, o método andThen, que vai receber a ação que fazemos no fim de cada laço, outro callable;
  • e, por fim, um método run que é o que vai acionar toda a recursão disso.

O que teremos nisso será algo do tipo:

(new RFor(['contador' => 1]))
    ->whileTrue(function ($loop) {
        return $loop->contador <= 10;
    })->doThis(function ($loop) {
        echo $loop->contador . PHP_EOL;
    })->andThen(function ($loop) {
        $loop->contador++;
    });

Ué, Kiko, como você vai fazer o array do construtor virar uma propriedade interna, dinamicamente? Vai criar uma variável contador? E se eu mudar o nome no array?

Eita, quanta pergunta... Infelizmente, isso vai ser um pouco mais avançado do que o ponto onde estamos atualmente na série PHP para Iniciantes. O que vou usar para solucionar isso é a criação de métodos mágicos. Implementando os métodos __get e __set, eu posso criar métodos especiais para gerar um comportamento específico para quando não há uma definição da propriedade que você tentar acessar. No caso, quando não existir a propriedade contador, o PHP irá acionar:

  • em caso de leitura de dados, o método __get('contador');
  • em caso de escrita, o método __set('contador', $valorAEscrever).

E com essas implementações, vou conseguir chegar no resultado esperado.

Orra... Legal! Então, como fica o teste?

Bom, aquele loop lá em cima faz a contagem de 1 a 10. Mas ele joga o resultado todo no buffer e isso não é o que a gente quer... Portanto, precisaremos modificar isso para receber o array de outra forma.

E já que estamos criando funções anônimas, por que não exportar dela mesmo? Assim, a chamada pode ficar dessa forma:

$result = [];
(new RFor(['contador' => 1]))
    ->whileTrue(function ($loop) {
        return $loop->contador <= 10; // return $loop->__get('contador') <= 10
    })->doThis(function ($loop) use (&$result) {
        $result[] = $loop->contador; // $result[] = $loop->__get('contador')
    })->andThen(function ($loop) {
        $loop->contador++; // $loop->__set('contador', $loop->__get('contador') + 1)
    });

Note que escrevi nos comentários o que o PHP estará executando, de fato, em cada linha. Ficou mais claro agora? No final de tudo, estaremos jogando todo o resultado na variável $result, que esperamos ser [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].

Da mesma forma, podemos fazer o contador reverso, que esperamos como resultado o array [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]:

$result = [];
(new RFor(['contador' => 10]))
    ->whileTrue(function ($loop) {
        return $loop->contador >= 1; // return $loop->__get('contador') >= 1
    })->doThis(function ($loop) use (&$result) {
        $result[] = $loop->contador; // $result[] = $loop->__get('contador')
    })->andThen(function ($loop) {
        $loop->contador--; // $loop->__set('contador', $loop->__get('contador') - 1)
    });

E também a captura dos primeiros 10 números pares a partir de 150, que esperamos como resultado [150, 152, 154, 156, 158, 160, 162, 164, 166, 168]:

$result = [];
(new RFor(['numero' => 150, 'resultados' => 0]))
    ->whileTrue(function ($loop) {
        return $loop->resultados < 10; // return $loop->__get('resultados') < 10
    })->doThis(function ($loop) use (&$result) {
        $result[] = $loop->numero; // $result[] = $loop->__get('numero')
    })->andThen(function ($loop) {
        $loop->numero += 2; // $loop->__set('numero', $loop->__get('numero') + 2)
        $loop->resultados++; // $loop->__set('resultados', $loop->__get('resultados') + 1)
    });

Tendo essas execuções em mente, agora podemos criar os testes.

Mas... Kiko, como a gente verifica os resultados?

Boa! Basicamente, como sempre vamos esperar um array, podemos usar o método estático assertEquals do PHPUnit. Ele tem como argumentos obrigatórios o valor esperado e o valor que foi gerado no teste. Se falhar, veremos na automação.

Com isso, chegamos ao desenvolvimento da primeira sugestão de testes:

<?php

namespace Tests\Example2;

use Tests\TestCase;

class RForTest extends TestCase
{
    public function test_countFrom1To10(): void
    {
        $result = [];
        (new RFor(['contador' => 1]))
            ->whileTrue(function ($loop) {
                return $loop->contador <= 10;
            })->doThis(function ($loop) use (&$result) {
                $result[] = $loop->contador;
            })->andThen(function ($loop) {
                $loop->contador++;
            });

        self::assertEquals([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], $result);
    }

    public function test_countFrom10To1(): void
    {
        $result = [];
        (new RFor(['contador' => 10]))
            ->whileTrue(function ($loop) {
                return $loop->contador >= 1;
            })->doThis(function ($loop) use (&$result) {
                $result[] = $loop->contador;
            })->andThen(function ($loop) {
                $loop->contador--;
            });

        self::assertEquals([10, 9, 8, 7, 6, 5, 4, 3, 2, 1], $result);
    }

    public function test_getFirstTenOddNumbersStartingFrom150(): void
    {
        $result = [];
        (new RFor(['numero' => 150, 'resultados' => 0]))
            ->whileTrue(function ($loop) {
                return $loop->resultados < 10;
            })->doThis(function ($loop) use (&$result) {
                $result[] = $loop->numero;
            })->andThen(function ($loop) {
                $loop->numero += 2;
                $loop->resultados++;
            });

        self::assertEquals([150, 152, 154, 156, 158, 160, 162, 164, 166, 168], $result);
    }
}

Kiko, como assim, sugestão de testes??

Isso porque podemos mudar de ideia ao longo da solução (apesar de estar bem clara na minha mente). Além disso, o teste não tem como funcionar porque não existe nenhuma classe RFor ainda, lembra? Vai precisar ser corrigido depois.

* Pronto, comitei. E sim, eu tô fazendo o código enquanto escrevo o artigo.

2. Solucionando o teste

Agora que preparamos os testes do desafio, vamos solucioná-lo. De cara, já sabemos que vamos precisar criar uma classe RFor na pasta de sources do desafio. Essa classe precisa implementar um construtor e os métodos whileTrue(callable), doThis(callable), andThen(callable) e run. Cada callable precisa ser armazenado na classe, mas não em forma de propriedade (pois se chamar uma propriedade como função, o PHP tentará ler um método que não existe e dará erro), e sim em algum array interno. Vamo chamar de $callables. Além disso, também usaremos os métodos mágicos __get e __set para ler/escrever dados na entrada do construtor, o que significa, também, que teremos uma propriedade interna que representa os dados de entrada, que chamarei de $attributes.

Uuuuuh, quanto detalhe...

Sim! Mas com isso já dá pra preparar o escopo:

class RFor
{
    private array $attributes;
    private array $callables = [];

    public function __construct(array $attributes)
    {
        $this->attributes = $attributes;
    }

    public function __get($var)
    {
    }

    public function __set($var, $value): void
    {
    }

    public function whileTrue(callable $condition): self
    {
    }

    public function doThis(callable $action): self
    {
    }

    public function andThen(callable $afterAction): self
    {
    }

    public function run(): void
    {
    }
}

Vamos implementar cada método.

2.1. __get(var)

Nós precisamos ler um dado que está em $this->attributes. Portanto, $var vai ser o índice que estamos buscando. Ainda assim, esse índice pode não existir... E nesse caso vale usar um null coalescing para controlarmos a anulidade.


public function __get($var)
{
    return $this->attributes[$var] ?? null;
}

2.2. __set($var, $value)

Agora precisamos escrever um dado em $this->attributes. Aqui, $var continua sendo o índice, mas $value representará o valor a armazenar. Então simplesmente definimos o valor no índice do array.


public function __set($var, $value)
{
    $this->attributes[$var] = $value;
}

2.3. whileTrue, doThis e andThen

Citei os três métodos pois a implementação é basicamente igual: definir um valor em $this->callables que usaremos posteriormente no método run().


public function whileTrue(callable $condition): self
{
    $this->callables['condition'] = $condition;
    return $this;
}

public function doThis(callable $action): self
{
    $this->callables['action'] = $action;
    return $this;
}

public function andThen(callable $afterAction): self
{
    $this->callables['afterAction'] = $afterAction;
    return $this;
}

Kiko, por que você retorna $this nesses métodos?

Ah, certo. Isso se chama Chained Method Calls ou Acionamento Encadeado de Métodos. Percebeu que, nos nossos testes, nós chamamos ->whileTrue(...)->doThis(...)->andThen(...)? É um método sendo acionado atrás do outro. Isso só ocorre em dois cenários:

  1. Cada método retorna algum novo objeto que implementa o método seguinte;
  2. Cada método retorna a própria instância para possibilitar a chamada encadeada.

Ou seja, você pode tanto chamar:

$obj->whileTrue();
$obj->doThis();
$obj->andThen();

Quanto:

$obj->whileTrue()
    ->doThis()
    ->andThen();

Por isso fiz dessa forma.

2.4. run

Runnnn

Esse é o método que vai, de fato, imitar o for. Aqui, nós vamos chamar o $this->callables['condition']($this) pra saber se podemos executar o laço atual. Se não pudermos, acabou: retorna vazio. Se sim, então chamamos o $this->callables['action']($this) para executar o laço e, depois, $this->callables['afterAction']($this), que é a ação após o laço e antes da próxima chamada.

Pra fechar com chave de ouro, acionamos a recursão: $this->run()


public function run(): void
{
    if (!$this->callables['condition']($this)) {
        return;
    }
    $this->callables['action']($this);
    $this->callables['afterAction']($this);
    $this->run();
}

Kiko, por que você coloca o $this em cada chamada?

Porque as funções anônimas não teriam como acessar os atributos de fora. Além disso, os atributos são arrays, lembra? Eu implementei os métodos mágicos especificamente para forçar o uso da nossa classe nessas funções. Por isso que repasso o $this... Mas dá pra melhorar isso criando outra classe depois numa refatoração, beleza?

Com isso, temos a implementação final da classe:

<?php

namespace Dojo\Example2;

class RFor
{
    private array $attributes;
    private array $callables = [];

    public function __construct(array $attributes)
    {
        $this->attributes = $attributes;
    }

    public function __get($var)
    {
        return $this->attributes[$var] ?? null;
    }

    public function __set($var, $value)
    {
        $this->attributes[$var] = $value;
    }

    public function whileTrue(callable $condition): self
    {
        $this->callables['condition'] = $condition;
        return $this;
    }

    public function doThis(callable $action): self
    {
        $this->callables['action'] = $action;
        return $this;
    }

    public function andThen(callable $afterAction): self
    {
        $this->callables['afterAction'] = $afterAction;
        return $this;
    }

    public function run(): void
    {
        if (!$this->callables['condition']($this)) {
            return;
        }
        $this->callables['action']($this);
        $this->callables['afterAction']($this);
        $this->run();
    }
}

* ... Pronto, comitei.

3. Corrigir o teste

Bom, agora que terminamos a classe, é hora de corrigir o teste para podermos rodar. No nosso caso, a única correção que precisamos fazer é adicionar o import da classe no início do arquivo:

use Dojo\Example2\RFor;

E depois podemos usar o seguinte comando para rodar cada teste: docker exec -it dojo-php php ./vendor/bin/phpunit --filter=RForTest.

... Para minha surpresa: todos os testes falharam. :O.......

.... Porque esqueci de incluir a chamada ao método run em todos os testes, HAHAHAHA.

Facepalm...

Por fim, depois de incluir o método run em tudo, temos a classe de teste final:

<?php

namespace Tests\Example2;

use Dojo\Example2\RFor;
use Tests\TestCase;

class RForTest extends TestCase
{
    public function test_countFrom1To10(): void
    {
        $result = [];
        (new RFor(['contador' => 1]))
            ->whileTrue(function ($loop) {
                return $loop->contador <= 10;
            })->doThis(function ($loop) use (&$result) {
                $result[] = $loop->contador;
            })->andThen(function ($loop) {
                $loop->contador++;
            })->run();

        self::assertEquals([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], $result);
    }

    public function test_countFrom10To1(): void
    {
        $result = [];
        (new RFor(['contador' => 10]))
            ->whileTrue(function ($loop) {
                return $loop->contador >= 1;
            })->doThis(function ($loop) use (&$result) {
                $result[] = $loop->contador;
            })->andThen(function ($loop) {
                $loop->contador--;
            })->run();

        self::assertEquals([10, 9, 8, 7, 6, 5, 4, 3, 2, 1], $result);
    }

    public function test_getFirstTenOddNumbersStartingFrom150(): void
    {
        $result = [];
        (new RFor(['numero' => 150, 'resultados' => 0]))
            ->whileTrue(function ($loop) {
                return $loop->resultados < 10;
            })->doThis(function ($loop) use (&$result) {
                $result[] = $loop->numero;
            })->andThen(function ($loop) {
                $loop->numero += 2;
                $loop->resultados++;
            })->run();

        self::assertEquals([150, 152, 154, 156, 158, 160, 162, 164, 166, 168], $result);
    }
}

E ao rodar os testes novamente, tudo passou!

* ... comitei!

Conclusão

É possível sim fazer uma implementação do for seguindo uma semântica clara no código. A questão é que isso não é benéfico para o desempenho da sua aplicação... Então usa o for mesmo, tá ok?!

Ah, Kiko, e a refatoração?

Meu amigo, já deu meia-noite aqui HAHAHAHA. Deixo a refatoração em aberto pra quem curtiu o desafio, ok?! É só fazer um fork do meu repositório de coding dojo, desenvolver e mandar o PR! Pode ficar a vontade.

E por hoje é só!! Curtiu? Comenta e compartilha!! Só pra deixar claro, eu não vou ficar fazendo desafios com frequência, mas aceito propostas nos comentários ou no privado, fica a vontade.

Inté!!

EDIT 22/10/2021

Algumas pessoas me fizeram perguntas no privado e resolvi manter as respostas aqui. Quaisquer dúvidas que tiverem sobre o artigo, podem perguntar! Pode ser a dúvida de outra pessoa... E sanando, eu edito pra colocar aqui.

1 - Qual versão do PHP você usou no repositório, Kiko?

PHP 7.4. E o motivo é bem simples: eu já tinha configurado aquele repositório nessa versão há muito tempo. Acho que vale a pena fazer um PR pra migrar pro PHP 8... Teríamos muita redução de código.

2 - Por que usou closure ao invés de arrow functions, Kiko?

Porque ainda não falamos sobre funções aqui no blog. Minha intenção era escrever códigos mais fáceis de ler pra quem já acompanha meus artigos. Mas pra galera mais avançada, dá pra fazer declarações mais simples com arrow functions nos callables onde não há modificação de valores externos à função. O arrow function captura variáveis externas somente para leituras. Portanto, aquele contador dos 10 primeiros números primos a partir de 150 poderia ser mais simples:

$result = [];
(new RFor(['numero' => 150, 'capturas' => 0]))
    ->whileTrue(fn ($loop) => $loop->capturas < 10)
    ->doThis(function ($loop) use (&$result) {
        $result[] = $loop->numero; // precisa ser closure para alterar a variável $result
    })
    ->andThen(fn ($loop) => ($loop->numero += 2) & ($loop->capturas++))
    ->run();

Não dá pra fazer 100% com arrow functions, exceto se a gente não for afetar valores externos, beleza?

Maaaaaaass....

Dá pra dar um jeitinho e usar 100% sim. Se a gente modificar um pouco a usabilidade do for e incluir a captura de resultados como um dado interno da estrutura orientada a objeto, nós podemos manipular os dados internamente. O array push não funciona dentro do array function, mas o __set sim. Então bastaria fazer:

$for = (new RFor(['numero' => 150, 'result' => []]))
    ->whileTrue(fn ($loop) => count($loop->result) < 10)
    ->doThis(fn ($loop) => $loop->result = array_merge($loop->result, [$loop->numero]))
    ->andThen(fn ($loop) => ($loop->numero += 2));
$for->run();
$result = $for->result; // [150, 152, 154, 156, 158, 160, 162, 164, 166, 168]

Apesar das funções ficarem mais legíveis, o que acontece dentro do doThis ficou horrível, né? $array = array_merge($array, [$algumaCoisa]) é a mesma coisa que $array[] = $algumaCoisa. Mas só porque estamos dentro de um arrow function, não dá para usar a segunda forma.

Ter de explicar tudo isso acho que já conta como motivo para não ter escrito dessa forma, certo?

3 - Se o callable inserido no método andThen é sempre executado depois do doThis, qual a necessidade de separar esses métodos, Kiko? Não era melhor manter um só e o dev faz tudo em um callable só?

O desafio era implementar um for e, no caso dele, isso fica separado. Por isso manti desse jeito!

4 - Li seu próximo artigo (foreach), como seria a implementação dele?

Se usarmos o RFor pra implementarmos um RForeach, seria um pouco complexo:

<?php
class RForeach
{
    private array $elements;
    private array $callables;

    public function __construct(iterable $elements)
    {
        $this->elements = (array) $elements;
    }

    public function getElements(): array
    {
        return $this->elements;
    }

    public function doThis(callable $action): self
    {
        $this->callables['action'] = $action;
        return $this;
    }

    public function run(): void
    {
        $keys = array_keys($this->elements);
        $action = $this->callables['action'];
        $for = new RFor([
            'index' => 0,
            'key' => $keys[0],
        ]);
        $for->whileTrue(fn ($loop) => $loop->index < count($keys))
            ->doThis(fn ($loop) => $action($this->elements[$loop->key]))
            ->andThen(fn ($loop) => $loop->key = $keys[++$loop->index % count($keys)]);
        $for->run();
    }
}

Fique a vontade para testar ;) Mas sem dúvida ainda prefiro usar for e foreach. Trabalho da zorra...

E por enquanto foi só isso, façam mais perguntas!

PHPcoding challengechallenge