Oddwording

Tem corrido por aí uma brincadeira chamada oddwording (do inglês odd words, «palavras ímpares»).

A idéia é pegar uma frase, indexar as palavras a partir de zero e inverter as palavras de índice ímpar.

Fiz três códigos: Python, Lua e Haskell.

Python

Dos três é o menor. Precisei criar apenas uma função oddword(). Essa função gera um reiterador.

Para começar, vamos ao cabeçalho Python padrão:

# -*- coding: UTF-8 -*-

import re
import os, sys

O módulo re (expressões regulares) será usado para quebrar a frase em palavras.

A idéia da função é partir a frase em uma lista de palavras. Será usada uma variável odd, que marca verdadeiro quando o índice for ímpar. Quando for par, retorna a palavra, quando for ímpar, retorna a inversão da palavra:

def oddword(phr):
    odd = False
    for w in re.findall(r'\S+', phr):
        if odd:
            yield w[::-1] + " "
            odd = False
        else:
            yield w + " "
            odd = True
    yield "\n"

Essa função já faz tudo. Vamos a uma «main» que demonstre seu funcionamento:

if __name__ == "__main__":
    print("Digite uma frase:")
    sys.stdout.write("> ")
    ph = sys.stdin.readline().strip()

    while ph:
        wordproc = oddword(ph)
        while True:
            try:
                word = wordproc.next()
                sys.stdout.write(word)
            except StopIteration:
                break

        print("Digite uma frase:")
        sys.stdout.write("> ")
        ph = sys.stdin.readline().strip()

[update 2007-05-11]
O Carlos Eduardo sugeriu nos comentários o uso de list comprehension.

Então o código Python fica assim:

import re
import os, sys

oddword = lambda fr: " ".join([
    (i%2 and e[::-1] or e)
    for i, e in enumerate(re.findall(r'\S+', fr))
])

print("Digite uma frase:")
sys.stdout.write("> ")
ph = sys.stdin.readline().strip()

while ph:
    print(oddword(ph))

    print("Digite uma frase:")
    sys.stdout.write("> ")
    ph = sys.stdin.readline().strip()

[/update]

Lua

Na verdade comecei fazendo em Lua.

A primeira coisa que fiz foi a função para inverter cada palavra. Comecei com um algoritmo reiterativo estilo C:

function inv(s)
    local ns = ""
    local i
    for i = 1, #s do
        ns = s:sub(i, i) .. ns
    end
    return ns
end

Mas esse código é pouco inteligível. Então, depois de fazer em Haskell, pensei que eu poderia implementar o algoritmo recursivo de Haskell em Lua.

Antes que alguém venha me dizer que recursividade é menos eficiente do que reiteratividade, isso é válido para algoritmos em árvore. Para recursões lineares, o algoritmo recursivo é quase tão eficiente quanto o reiterativo, só que mais claro. Aliás, pretendo escrever outro artigo sobre eficiência de algoritmos.

A função reiterativa ficou assim:

function inv(s)
    if #s == 0 then
        return ""
    else
        return inv(s:sub(2)) .. s:sub(1, 1)
    end
end

A função oddword() em Lua funciona da mesma forma que em Python, mas usando corrotina.

Em Python, a função para «picotar» a string em palavras é re.findall(), em Lua é string.gmatch() (que retorna um reiterador em vez de um lista):

function oddword(phr)
    local co = coroutine.wrap(function ()
        local w
        local odd = false
        for w in phr:gmatch "%S+" do
            if odd then
                coroutine.yield(inv(w) .. " ")
                odd = false
            else
                coroutine.yield(w .. " ")
                odd = true
            end
        end
        coroutine.yield "\n"
    end)

    return co
end

A variável odd funciona da mesma forma que em Python.

O código exemplo:

local ph
print "Digite uma frase:"
io.write "> "
ph = io.read()

while #ph > 0 do
    local word
    local wordproc = oddword(ph)

    word = wordproc()
    while word do
        io.write(word)
        word = wordproc()
    end

    print "Digite uma frase:"
    io.write "> "
    ph = io.read()
end

Haskell

Programação funcional é uma coisa maravilhosa. Certa vez estava conversando com o Torcato, e ele me disse que seu código melhorou muito depois que ele começou a estudar Haskell com mais seriedade. Então me toquei que o meu também.

A programação funcional força o programador a ter bons hábitos de programação, como estruturar o código em funções simples, top-down, usar reiteração de forma eficiente e memoização.

Em função disso infelizmente o código em Haskell é o mais longo. =(

O código começa com o cabeçalho padrão:

module Main where

import IO

Poderia ter feito diferente… poderia ter criado um módulo OddWord e importá-lo no programa principal. Mas preferi fazer assim para ficar mais simples.

Como há um ciclo que se repete, foi criada uma função para tanto, deixando a «main» muito pequeninha:

main = mainloop

Onde mainloop é a função que faz o ciclo. O que essa função faz? Chama outra (readString) que lê a frase. Se a frase for vazia, sai, se não, faz oddwording na frase, exibe o resultado e volta ao princípio.

Ah! Essa função não recebe nem retorna dados (IO ()).

mainloop :: IO ()
mainloop = do
    ph <- readString
    if ph == ""
        then
            return ()
        else do
            let nph = oddword ph
            putStrLn nph
            mainloop

A função para ler uma string é simples:

readString :: IO String
readString = do
    putStrLn "Digite uma frase:"
    putStr "> "
    s <- getLine
    return s

A função oddword precisa:

1. Converter a frase para uma lista de palavras (strToList);
2. Inverter as palavras de índice ímpar (invodd);
3. Converter a lista de palavras de volta para uma string única (listToStr).

Há um pipe simples para concatenar as funções em Haskell: $.

Portanto, a função oddword será simplesmente:

oddword :: String -> String
oddword s = listToStr $ invodd $ strToList s

Agora precisamos definir as funções usadas.

A primeira, strToList, precisa receber uma string, percorrer ela procurando por ocorrências de espaço, retornando uma lista das strings entre os espaços:

strToList :: String -> [String]
strToList "" = []
strToList s  = (take spi s) : (strToList (drop (incr spi) s))
    where spi = nextspace s

Ops…! Chamamos duas funções que não existem (incr e nextspace)… então vamos precisar defini-las.

A função para retornar um valor incrementado é estupidamente simples, e há duas formas.

Uma é usando lambda:

incr :: Int -> Int
incr = \x = x + 1

A outra é usando preenchimento parcial de parâmetros ([update 2007-05-11]acho que é construção parcial ou algo assim[/update]):

incr :: Int -> Int
incr = (+ 1)

Ambos funcionam igualmente. Tanto faz usar uma ou outra.

A função para identificar o próximo espaço deve retornar zero se encontrar um espaço, se não, 1 mais o retorno da mesma função para a string começando na próxima posição:

nextspace :: String -> Int
nextspace ""     = 0
nextspace (x:xs) =
    if x == ' '
        then
            0
        else
            1 + (nextspace xs)

A próxima função a ser avaliada é listToStr, que é mais simples: deve apenas concatenar os elementos usando espaço como separador:

listToStr :: [String] -> String
listToStr []     = ""
listToStr (x:xs) = x ++ " " ++ (listToStr xs)

Falta apenas uma função… que na verdade vai virar três. =P

A idéia da invodd é inverter só os índices ímpares. Como o índice inicial é considerado par, ela não pode inverter o elemento, e deve chamar uma função que inverta o próximo elemento (cujo índice é ímpar).

Essa nova função (inveven) deve inverter o elemento atual e chamar invodd para o próximo elemento (par):

invodd :: Ord a => [[a]] -> [[a]]
invodd []     = []
invodd (x:xs) = x : (inveven xs)

inveven :: Ord a => [[a]] -> [[a]]
inveven []     = []
inveven (x:xs) = (inv x) : (invodd xs)

Faltou só a função de inversão! Ela é extremamente simples e funciona da mesma forma que a função de inversão em Lua (aliás, lembrando, fiz a função em Lua a partir da função em Haskell):

inv :: Ord a => [a] -> [a]
inv []     = []
inv (x:xs) = (inv xs) ++ [x]

Está feita!!! É só compilar e ver funcionando.


Terminei a brincadeira.

Ah sim! É bom citar que o Walter me disse que a brincadeira começou no Dr. Dobbs.

[]'s
Rodrigo Cacilhas