Tenho saudades de Ornatos…
Ornatos Violeta
27 11 2007Comments : 1 Comment »
Tags: music, ornatos violeta, Português, video
Categories : Uncategorized
Gauss aritmetic serie
25 11 2007Last year I had Algorithms and Complexity classes and sometimes we had to make the asymptotic analysis of some algorithms. There we used many times the following summation:
Back in then I didn’t care about what was behind that formula. Currently I am reading the Knuth book Concrete Mathematics, and there was the explanation…
In fact Gauss is who discovered this expression. There is a famous story about how Gauss discovered it:
In primary school his teacher, J.G. Büttner, tried to occupy pupils by making them add up the integers from 1 to 100. The young Gauss produced the correct answer within seconds by a flash of mathematical insight, to the astonishment of his teacher and his assistant Martin Bartels. Gauss had realized that pairwise addition of terms from opposite ends of the list yielded identical intermediate sums: 1 + 100 = 101, 2 + 99 = 101, 3 + 98 = 101, and so on, for a total sum of 50 × 101 = 5050
I think that’s only a story, nothing more. Like others stories that said that Einstein was terrible in math at school.
Anyway, Gauss was really a brilliant mind in many fields and won a Copley Medal in 1838, the highest award of Royal Society of London.
If you don’t understand the definition in the previous quotation, here is the mathematical proof:
(click in the image to see it better)
I think the image is pretty clear, brilliant indeed!
Comments : 4 Comments »
Tags: arithmetic progression, English, gauss, mathematics
Categories : Uncategorized
foldr the magic function
20 11 2007Recursion
In Haskell we essentially use recursion, this mean defining a function using itself definition.
A recursive function is, for example the factorial:
in haskell we define it like that:
fact 0 = 1 fact n = n * fact (n-1)
As you can see Haskell is authentic mathematic, pure functional language.
My point here is to show you the magic of the function in Haskell, so I will assume that you already know Haskell, and maybe are accustomed to use function.
ok…
Seeing the magic
The definition of the function could be something like this:
length [] = 0 length (h:t) = 1 + length t
The definition of the function could be something like this:
sum [] = 0 sum (h:t) = h + sum t
And the definition of the function could be something like this:
mult [] = 1 mult (h:t) = h * mult t
As you can see in all three definitions we have a pattern and we can generalize it:
functionName [] = stopCase functionName (h:t) = constant operator (functionName t)
We always need the stopping case of the function!
And the same happens in other functions like :
reverse [] = [] reverse (h:t) = reverse t ++ [h]
In this case we have:
functionName [] = stopCase functionName (h:t) = (functionName t) operator constant
So, we will always use the function applied to the tail of the list!
If we use some of lambda notation we can see one more pattern, the real one:
sum [] = 0 sum (h:t) = (a b -> a + b) h (sum t) reverse [] = [] reverse (h:t) = (a b -> b ++ [a]) h (reverse t)
Our lambdas functions have arity 2, because those are the parts in which we can see the lists (head + tail).
Now we can generalize even more, considering have arity 2:
functionName [] = stopCase functionName (h:t) = function h (functionName t)
well, that’s not right for Haskell. Because it doesn’t know what represents, that’s because the definition of doesn’t receive that argument. And the same happens with .
functionName function stopCase [] = stopCase functionName function stopCase (h:t) = function h (functionName function stopCase t)
Et voilá.
In fact the last definition is the true one for . Easy right?
Functions with foldr’s
Well… Now we can redefine previous functions just with foldr’s:
length l = foldr (a b -> 1 + b) 0 l sum l = foldr (+) 0 l mult l = foldr (*) 1 l reverse l = foldr (a b -> b ++ [a]) [] l
And all the functions over list’s…
and l = foldr (&&) True l or l = foldr (||) False l
More magic
Foldr is more magical than this, it is one catamorphism! A Catamorphism over this data type:
data [a] = [] | a : [a]
Haskell List’s!
That means that functions “knows” the recursive pattern over List’s.
Foldr also allows you to use Pointfree notation, witch I like. Formal explanation.
length = foldr (a b -> 1 + b) 0
More foldr’s
We can also write foldr’s functions to every data type that we create, and “explain” how recursive patterns works for our new data type:
data BTree a where Empty :: BTree a Node :: a -> BTree a -> BTree a -> BTree a foldrBTree :: (a -> b -> b -> b) -> b -> BTree a -> b foldrBTree op k Empty = k foldrBTree op k (Node a l r) = op a (foldrBTree op k l) (foldrBTree op k r)
Now if we have a Binary Tree and want to know how many nodes it has, we just have to do this:
countNodes = foldrBTree (\a nodesLeft nodesRight ->a+nodesLeft+nodesRight) 0
If we want to know how many Empty’s our tree has:
countEmpty = foldrBTree (\_ nodesLeft nodesRight -> nodesLeft + nodesRight) 1
and so on…
Fold’s are really a genuine help for your code.
Later on I will talk more about catamorphisms…
Comments : 20 Comments »
Tags: catamorphism, code, English, foldr, GADT, haskell, howto, lambda, pointfree, recursion
Categories : Uncategorized
Bunny suicides
11 11 2007Confesso que não gosto de cartoons, mas esta série do Bunny Suicides é das coisas mais hilariantes que já vi. Geralmente cartoons de uma única imagem em que o actor principal é um (ou mais) coelhinho(s) inofensivo(s) (ao contrário do dos Monty Python) que arranja das mais surpreendentes técnicas e instrumentos com o propósito de se matar. Só isto já me parece genial!
Martelos, saca-rolhas, cigarros, arcadas de edificios, foguetes, lanças, livros do Harry Potter, agrafadores, balões e até um moinho de vento. Tudo com o proposito de acabar com a sua existência. LOLZ… Muito humor negro e alguma referência a acontecimentos culturais e históricos.
Bunny Suicides foi criado pelo brilhante Andry Riley (à esquerda), cartoonista e guionista de sitcoms Britânico. The Book of Bunny Suicides foi o livro lançado por Andry em 2003, em 2004 lançou Return of the Bunny Suicides. Ambos foram um sucesso e continuam a ser até ao dia de hoje. A editora dos livros parece que não levou a bem (como seria de esperar) a publicação ilegal de conteúdo dos livros na web (como também seria de esperar). Por isso deixo apenas como referência um desses casos.
Comments : 2 Comments »
Tags: Andy Riley, bunny suicides, humor, Português
Categories : Uncategorized
CeSIUM entrevista
10 11 2007Acabei de encontrar esta foto na net e não pude deixar de a meter aqui, na altura nem soube onde tinha sido publicada. Já nem me lembrava deste dia. Que grande foto!
Parte dos elementos do CeSIUM.
Comments : 1 Comment »
Tags: cesium, Português, uminho
Categories : Uncategorized
Workshop introducao ao LaTeX@UMinho
10 11 2007Correu altamente a workshop de LaTeX organizada pelo CAOS. Mais um sucesso de toda a equipa que trabalha no CAOS. Foi um dia cheio de partilha de conhecimento. Eu mais o Nuno ficamos incrédulos com o grupo heterogéneo de participantes que tínhamos; dois professores do Departamento de Estudos Germanísticos, um aluno de doutoramento, alunos de Opetometria e Ciências da Visão, vários alunos de Física e ainda, como seria de esperar, alunos de LEI. Rapidamente me apercebi que tinha um desafio nas mãos, ensinar uma linguagem a pessoas que nunca na vida tinham/irão ver código.
Decidi que quem tinha de se aperceber do potencial do LaTeX eram eles mesmos, por isso omiti, propositadamente, alguns pormenores que posteriormente eles se iam apercebendo e vendo a real filosofia do LaTeX.
A workshop foi evoluindo naturalmente, todos ficaram entusiasmados com a história do LaTeX e o verdadeiro desafio aproximava-se; fazer documentos! Rapidamente chegamos aos exercícios e o entusiasmo foi geral. Rapidamente se instalou o MiKTeX para Windows e mais algumas aplicações para MAC, enquanto isto os Linux user’s esperavam impacientemente (lolz).
Os exercícios correram todos muito bem, toda a gente conseguiu fazer os exercícios propostos e alguns até já começavam a explorar com o que já tinham aprendido até à altura. Foi muito bom!
Às 19:00 estava terminado, olhamos um para o outro e parecia que tínhamos sido agredidos violentamente por um batalhão das GOE em pleno Departamento de informática.
Estávamos cansados, mas confesso que adorei dar esta workshop e o Nuno Veloso idem.
Código da apresentação e exercícios, tar.gz com tudo.
Reacções do Nuno Veloso relativamente ao evento.
Comments : 4 Comments »
Tags: beamer, caos, cesium, code, LaTeX, Português, uminho
Categories : Uncategorized