Arquivos Mensais: outubro 2009

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