Streams (listas infinitas) em C

Ultimamente tenho feito duas coisas: lido sobre Haskell e não postado no blog (além das outras coisas do dia-a-dia, claro).

Programas em Haskell são preguiçosos. Isso significa que quando uma variável é definida, ela só será computada quando seu valor for necessário. Assim, se fizermos um programa similar ao de baixo, fatorial de 1000 nunca será calculado, já que o seu valor não é necessário para calcular 1+1.

x = factorial 1000
putStrLn $ show (1+1)

Extrapolando essa mesma ideia* para outras definições, podemos definir uma lista de infinitos uns:

uns = repeat 1

Ou então com todos os números naturais:

naturais = [1..]

Com um pouco mais de perspicácia, é possível criar listas contendo todos os números de Fibonacci, ou então todos os fatoriais:

fibs = 1:1: (zipWith (+) fibs (tail fibs))
facs = 1:(zipWith (*) facs [1..])

Se quisermos 10 elementos de cada, fazemos:

dezFibs = take 10 fibs
dezFacs = take 10 facs

Essa implementação é bastante eficiente : se precisamos do fatorial de 10 e logo em seguida o de 11, não precisamos calcular 11×10×9×…×1, basta calcular 11×10!, que já havia sido computado. Melhor ainda : se uma hora precisarmos do fatorial de 7, ele já estará calculado, pronto para ser utilizado.

Agora sim a parte interessante, em que C entra nessa história. Embora minha implementação não seja nem de longe tão interessante como a utilizada pelo Haskell, ela serve de base para mostrar como uma implementação de stream ou listas infinitas pode ser feita em C.

A grande diferença entre listas e streams é que não trabalharemos com a idéia de um ponteiro para o próximo elemento, mas sim com uma expressão que ao ser executada nos dará o próximo elemento. Ou seja, ao invés de um ponteiro para outro elemento do mesmo tipo, nós temos um ponteiro para uma função.

typedef struct {
    int i;
    int (*cont)(int);
} stream;

Isso altera a forma como acessamos o próximo elemento. Não podemos mais utilizar o famoso ptr = ptr->prox porque estaremos apontando para uma função. Por isso, abstraí o processo de chamar a função com o valor da stream em uma função chamada proximo, que retorna uma nova struct com seu valor i atualizado pela função cont, o que dá a impressão de que avançamos na lista.

stream proximo(stream inicio)
{
    stream tmp;

    tmp.i = (*inicio.cont)(inicio.i);
    tmp.cont = inicio.cont;

    return(tmp);
}

Para exemplificar o uso de streams, criei a função pega que é similar à função take no Haskell, mas que no caso não retorna os valores, só os imprime.

void pega(int elementos, stream inicio)
{
    int i;
    stream atual = inicio;

    for(i = 0; i < elementos; i++)
    {
        printf("%d\n",atual.i);
        atual = proximo(atual);
    }
    printf(".\n.\n.\n\n");
}

Por fim, criei duas streams e duas funções auxiliares (que falta fazem expressões lambda). O código completo se encontra abaixo:

#include <stdlib.h>
#include <stdio.h>

typedef struct {
    int i;
    int (*cont)(int);
} stream;

stream proximo(stream inicio)
{
    stream tmp;

    tmp.i = (*inicio.cont)(inicio.i);
    tmp.cont = inicio.cont;

    return(tmp);
}

int soma_um(int i)
{
    return(i+1);
}

int repete(int i)
{
    return(i);
}

void pega(int elementos, stream inicio)
{
    int i;
    stream atual = inicio;

    for(i = 0; i < elementos; i++)
    {
        printf("%d\n",atual.i);
        atual = proximo(atual);
    }
    printf(".\n.\n.\n\n");
}       

int main(int argc, char *argv[])
{
    stream naturais, identidade;

    naturais.i = 1;
    naturais.cont = &soma_um;

    identidade.i = 1;
    identidade.cont = &repete;

    pega(10, naturais);
    pega(10, identidade);
    return 0;
}

*eu escrevi “idéia” mas aparentemente os verificadores ortográficos já aderiram todos às novas regras ortográficas… fica assim mesmo.

Publicidade

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair /  Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair /  Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair /  Alterar )

Conectando a %s

%d blogueiros gostam disto: