Wednesday, February 20, 2013

Fibonacci Generator

I was reading up on various types of morphism recently. While I was disappointed in the examples, as they were showing off bad practice, even if they were just an example, I got an idea. While I do have a post showing off a similar bad example with calculating a Fibonacci number, I have since refined it into a faster and more efficient method and an explanation to it you can find here.

My main focus of interest was looking at catamorphism and anamorphism. In the process of reading up, I came across other types of morphisms that while were mathematically interesting, I only saw bad programming being shown emerging from the ideas.

To explain in the simplest way possible, catamorphism is a generator and the opposite of anamorphism, which is a fold. Generators are functions that produce data on-call, using the generated data to provide more data upon the next call. This can create an infinite data type or have an end. Counting can be catamorphic in nature. For the explanation, let's look at a Python generator.

def counting(x):
    while 1:
        yield x
        x += 1

This is the equivalent to this Haskell code.

counting x = [x..]

The Python code has a bit of a more robust description to it, but the idea is the same for both, they will count from x on up until forever. Anamorphism includes things like the sum function, a list of stuff goes in, and it's all folded together with a function (in the case of sum, adding) until one result remains.

Now to the cool part and what this all means. This all means that with the magic of generators, there is an easy way to create a fibonacci generator. This is a simple one-liner in Haskell and as far as I can tell, can outdo the crappy version of the recursive Fibonacci shown everywhere else.

fibgen a b = a : (fibgen b (a + b))

That's all there is to it. The idea is you supply the first two numbers and it does the rest, forever and ever. So if you want the numbers from it, just take them. Now I suppose I can be nice and give something similar in Python, although to be honest it will look pretty much like the counting function I made.

def fibgen(a, b):
    while 1:
        yield a
        a, b = b, a + b

With only some very small tweaking, I turned the counting function into a Fibonacci generator. Now, like magic, we have an easy way to cycle through a sequence of Fibonacci numbers. I want to try to work on various problems more in this manor for when list processing or other related activities that require sequential computations, I feel it simplifies the process and gives a more elegant solution (or if nothing else, it looks cool).

No comments:

Post a Comment

Tag Cloud

.NET (2) A+ (5) ad ds (1) addon (4) Android (4) anonymous functions (1) application (9) arduino (1) artificial intelligence (1) backup (1) bash (6) camera (2) certifications (3) comptia (5) css (2) customize (11) encryption (3) error (13) exploit (5) ftp (1) funny (4) gadget (4) games (3) GUI (5) hardware (16) haskell (6) help (14) HTML (3) imaging (2) irc (1) it (1) java (2) javascript (13) jobs (1) Linux (19) lua (1) Mac (4) malware (1) math (6) msp (1) network (13) perl (2) php (3) plugin (2) powershell (8) privacy (2) programming (24) python (10) radio (2) regex (3) repair (2) security (16) sound (2) speakers (2) ssh (1) story (5) Techs from the Crypt (5) telnet (1) tools (13) troubleshooting (11) tutorial (9) Ubuntu (4) Unix (2) virtualization (2) web design (6) Windows (16) world of warcraft (1) wow (1) wx (1)