quinta-feira, 10 de maio de 2007

Oddwording

Poliedro 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
blog comments powered by Disqus