Haskell: Operações Recursivas em Listas

Fala galera, tudo tranquilo?

Hoje o assunto é bem bacana, venho fazendo uma listinha de exercícios marotos em Scala, e estou aprendendendo muito. Hoje o assunto é recursividade, de novo esse assunto? Sim isso está mudando minha vida ou mesmo a forma como penso. (Exagerando rs)

Então, vamos fazer em Haskell?

A ideia é simples, quero deixar bem claro e simples as operações em listas imutáveis usando recursividade, já expliquei algo sobre listas imutáveis aqui.

Bom, vamos começar com um problema, que tal fazermos um map* em uma lista.

* = Para quem não sabe, mapear uma lista é transformar cada valor da lista atual, em um valor que passará através de uma determinada função.

Crie um novo arquivo, double.hs, como não falo há pouco de tempo de Haskell, nos meus primeiros posts, você consegue ver como instalar o interpretador Hugs.

Vamos ao double.hs:

double [] = []
double (head:tail) = head * 2 : double tail

Bom, isso aí já torna a compreensão pouco simples, mas vou explicar, entenda:  double [] = [] é a nossa guarda, ou seja, um ponto onde devemos parar a execução da função. Já falei muito a respeito em posts mais antigos.
Já na segunda linha, vemos algo novo, mas acredito ser bem expressivo, double (head:tail), ali estamos separando a cabeça da lista, de seu corpo, faremos uma operação na cabeça (head *2) e concatenaremos com o corpo, mas passando o corpo como argumento da função double, repetiremos esse processo novamente, isso é incrível e simples.

Para exercitar, primeiro vamos deixar nosso double mais genérico, pois podemos querer fazer outros tipos de map em lista, crie um arquivo mapear.hs:

mapear f [] = []
mapear f (x:xs) = (f x) : mapear f xs

Pronto, agora nossa função está apta a receber outras funções a serem aplicadas a lista, você pode testar no Hugs.

Vá ao seu terminal, caminhe até o diretório do arquivo e digite: hugs mapear.hs

Para construir listas em Haskell, você pode usar de duas formas:

[1,1,2,3,5,8]
1 : 1 : 2 : 3 : 5 : 8 : []

Agora é só passar os parâmetros para sua função: mapear (*2) (1 : 2 : 3 : [])

Use os parênteses para "separar" os argumentos. Tudo certo! (Ou deveria estar).

Vamos evoluir mais um pouco, outra das operações básicas que podem ser efetuadas com lista é o Filter, onde você filtra os elementos da lista e só extraí o que "passar pelo filtro". Basicamente vamos passar uma validação para cada elemento da lista, e como fazer? Crie um arquivo filtro.hs e vamos codar nele:

filtro :: (a -> Bool) -> [a] -> [a] 
filtro f [] = []
filtro f (x:xs) | f x = x : filtro f xs
                | otherwise = filtro f xs

Trabalhamos com quase a mesma forma de aplicar a função do mapear, porém fizemos uma verificação, onde:

•  | é a nossa verificação;
• caso f x retorne false:
• devolvemos só  filtro f xs;
•  caso f x retorne true:
• concatenamos a cabeça x ao filtro f xs;

Ou seja, como vamos navegando na lista, cada hora a cabeça é o elemento posterior, isso é muito simples. Já falei de estruturas de verificação.

O desafio de hoje é meio trabalhoso, caso a preguiça domine vai ter que esperar eu fazer aqui também pra disponibilizar no Github. Você deve implementar um Flatten, ou seja, caso receba uma lista de listas, deve devolver uma lista contendo todos os elementos das listas internas.

É isso aí gente, qualquer dúvida comente abaixo ou email-me: abner.terribili@lambda3.com.br.

Java, C# : Imutabilidade

Fala galera, tudo tranquilo?

Você já teve interesse de conhecer como são as implementações de Listas ? (List do C#, Java)

Basicamente, as interfaces(List) definem os tipos de operações que podem ser realizadas nas Lista. Vou escrever algo bem bacana, faremos uma implementação de Lista Imutável.

Imutabilidade
Basicamente, é uma característica de um objeto permanecer o mesmo sempre. Quer saber mais sobre Imutabilidade: Bruno Nardini http://www.brunonardini.com.br/artigos/favoreca-a-imutabilidade-e-a-simplicidade

A classe String, tanto do Java quanto C# , encapsula alguns métodos de manipulação de String, como o toUpperCase() (C# = ToUpper()), que têm o objetivo de converter sua string para maiúsculo. Porém por baixo dos panos, o que acontece é você receberá uma nova instância, com o conteúdo de sua string antiga convertida para maiúsculo. (Você pode verificar isso nos links acima)

Já definido o que é Imutabilidade, vamos ao conceito básico de Listas Ligadas (Linked List). (http://www.caelum.com.br/apostila-java-estrutura-dados/listas-ligadas/#5-1-solucao-classica-de-lista-ligada)

Uma Lista Ligada é uma lista onde o elemento atual "aponta"(tem o endereço) para/do o seu próximo irmão, analisem a fotografia abaixo:

Um conceito simples, agora vamos a prática, assim podemos misturar os dois conceitos! (Imutabilidade e Linked List). No exemplo vai rolar um pouco Generics, se já sabe legal, caso não: http://en.wikipedia.org/wiki/Generic_programming#Generics_in_Java .

Primeiro, vamos criar uma interface para nossas listas, para isso, crie um projeto novo no Eclipse, dê um nome e vamos lá:

New -> Interface

public interface List {
    T cabeca();
    List cauda();
    List adicionaNoComeco(T elemento);
    T pegaPosicao(int position);
    List removePrimeiraPosicao();
}

Bom e o que é cabeça e cauda?
Cabeça é o elemento superior de nossa lista, ou seja a head da Lista.
Cauda é todo o restante da lista, é composta por sua cabeça e outra cauda, e assim respectivamente.

Nosso método adicionaNoComeco(T elemento) recebe um parâmetro e retorna uma nova Lista com o respectivo elemento adicionado. Bem parecido com o método removePrimeiraPosicao() que remove o primeiro elemento e retorna a cauda da lista.

Bom vamos as implementações, vamos criar uma nova classe, que podemos chamar de No, ou seja, serão os respectivos nós de nossa Lista:

public class No implements List {
    private final T cabeca;
    private final List cauda;

    public No(T cabeca, List cauda) {
        this.cabeca = cabeca;
        this.cauda = cauda;
    }
    @Override
    public T cabeca() {
        return cabeca;
    }
    @Override
    public List cauda() {
        return cauda;
    }
    @Override
    public List adicionaNoComeco(T elemento) {
        return new No(elemento, this);
    }
    @Override
    public T pegaPosicao(int position) {
        if (position == 0)
            return cabeca();

        return cauda.pegaPosicao(position - 1);
     }
    @Override
    public List removePrimeiraPosicao() {
    return cauda();
    }
}

Entenda:
Ao criar um No, nós receberemos a cabeça (elemento) e sua respectiva cauda (List). Fora o método pegaPosicao, o restante é bem trivial, por isso não entrarei em maiores detalhes.

pegaPosicao(T elemento)
Esse método faz uso recursivo de si próprio, ou seja, ele percorre a cauda, caso o posicao não seja 0, e recursivamente ele vai caminhando de cabeça em cabeça, das caudas, para encontrar o elemento desejado. Bem simples e objetivo.

Certo, feito isso, fica simples entender algumas coisas, a primeira de todas, como será o fim de nossa lista?
Temos que saber onde a Lista tem seu final e como o fazemos?

Faremos outra implementação de List, que agora chamaremos de Nil, será o fim de nossa lista.

public class Nil implements List {
    @Override
    public T cabeca() {
        throw new RuntimeException("Lista Vazia");
    }
    @Override
    public List cauda() {
        throw new RuntimeException("Lista Vazia");
    }
    @Override
    public List adicionaNoComeco(T elemento) {
        return new No(elemento, this);
    }
    @Override
    public T pegaPosicao(int position) {
        throw new RuntimeException("A lista não possui elementos");
    }
    @Override
    public List removePrimeiraPosicao() {
        throw new RuntimeException(
        "Impossível remover elementos de uma lista vazia");
    }
}

O Nil, que como dito acima, tem o objetivo de ser o fim da lista, a única coisa que podemos escrever interessante ao seu respeito é que a reescrita do método adicionaNoComeco vai retornar uma nova instância de No, ou seja, iniciaremos uma lista.

Feito isso, temos um Container, o List, que armazena valores e possui funções para alterar os dados internos, isso nos ajuda muito com a Imutabilidade, nos sentimos mais seguros e sabemos que nosso objeto não será um mutante, que pode perder/alterar seus valores em tempo de execução.

Bom galera, o conceito de hoje foi bem bacana e construtivo, é o que tenho mais feito no meu treinamento com o Jonas, aqui na Lambda3. Espero que tenha ficado claro.

Para os C# manjadores, no meu Github tem um exemplo parecido escrito em C#. Para os Javas, deixarei outro repositório no GitHub já com os testes implementados.

Qualquer dúvida ou sugestão email-me: abner.terribili@lambda3.com.br ou comente abaixo!

Valeu galera!