Sunday, March 24, 2013

Anamorphism

Anamorphism is the opposite of catamorphism. Since catamorphism is folding, then anamorphism can be considered unfolding. So let's first look at the mechanics for unfolding.

To unfold, we return a sequence of data. This sequence does not need to be finite. The amount returned can be dynamic or static or infinite. Things like list comprehension and generators are some quick examples of unfolding. In Python, xrange and range are anamorphic in a way.

The usefulness of unfolding is that we can get a series of data about some information without even needing to know anything about it before hand. Some useful math you can do with this would be things like getting all the divisors of a number. I have used anamorphism for generating Fibonacci numbers in sequence as well.

divisors :: Integral a => a -> [a]
divisors n = [i | i <- [1..(n `div` 2)], rem n i == 0]

fibgen :: Num a => a -> a -> [a]
fibgen a b = a : (fibgen b (a + b))

The divisors function returns a finite sequence of data whereas the fibgen returns an infinite amount. Also note that divisors is using list comprehension whereas fibgen is a normal function.

That is about all there is to anamorphism, an unfolding of data. Even replicating data can be an anamorphism. Oh, and an anamorphism can even take lists of data or multiple lists of data and return a list of data, like zipping two lists together.

Friday, March 22, 2013

Catamorphism

Many types of morphism concepts exist in programming, and catamorphism is one of them. Catamorphism is a functional style and is basically a fold. The idea is you take a sequence of data and sequentially go through it, folding data in on itself until you end up with a different value. The folding is usually recursive in nature and one thing to be careful of is not to fold causing exponential growth.

One thing to remember is that when using a lazy fold, it is not immediately calculated, making it a little less catamorphic by nature having an intermediate step with thunks*. Strict folding causes immediate evaluation. The basic theory is that a fold is catamorphic. So how does this work?

Let's say we have a list of data:
[1, 2, 7, 5, 3]

Now let's say we want to multiply all that data together. Using a (strict) fold, this is what will happen.

* [1, 2, 7, 5, 3]
1 * [2, 7, 5, 3]
(1 * 2) => 2 * [7, 5, 3]
(2 * 7) => 14 * [5, 3]
(14 * 5) => 70 * [3]
(70 * 3) => 210

Thus the data folds in on itself around the function, in this case multiplying. In Haskell, this would look like

foldl1' (*) [1, 2, 7, 5, 3]

Looking at other examples, they also seem to include fancy mapping stuff and function composition, but that is overlooking the basic theory. On Wikipedia, the example is this.

data Tree a = Leaf a
            | Branch (Tree a) (Tree a)
 
type TreeAlgebra a r = (a -> r, r -> r -> r)
 
foldTree :: TreeAlgebra a r -> Tree a -> r
foldTree (f, g) (Leaf x)     = f x
foldTree (f, g) (Branch l r) = g (foldTree (f, g) l) (foldTree (f, g) r)
 
treeDepth :: TreeAlgebra a Integer
treeDepth = (const 1, \l r -> 1 + max l r)
 
sumTree :: (Num a) => TreeAlgebra a a
sumTree = (id, (+))

After much examining, the idea behind it is to map some function to all the items in the list, then fold them all on some function. Examples on the Haskell wiki follow suit, only using functors and function composition (fmap and the period). The end result is a fold, the difference being some form of mapping can also occur over the data. On a normal list, this can be achieved and summed up as such.

cata f g xs = foldl1' f $ fmap g xs

With this, we apply function g to all members of list xs, then fold the mapped result on f. This could then be expanded to get the exact same results as we achieved before, or to do other things.

-- The same as we did before with foldl1'
cata (*) id [1, 2, 7, 5, 3]

-- To get the length of a string
cata (+) (const 1) "Hello!"

This can be further expanded by throwing some functors into the mix, but the very end result is data is folded in on itself around a function to get a result. The cata function I created is to make a very general purpose fold, however any function that folds down on itself is catamorphic.

So a catamorphism is folding, no matter how simple or complex the route to get to it is. It can also use a right fold, I just prefer a left fold. When it does something more than folding, it could be hylomorphic or metamorphic.

* Lazy folds

When using a lazy fold, what happens can change. Since lazy is more "on demand" evaluation, you end up with something that looks like this.

* [1, 2, 7, 5, 3]
1 * 2 * [7, 5, 3]
1 * 2 * 7 * [5, 3]
1 * 2 * 7 * 5 * [3]
1 * 2 * 7 * 5 * 3
2 * 7 * 5 * 3
14 * 5 * 3
70 * 3
210

This may not reflect exactly what happens but is the general idea of lazy evaluation as apposed to strict. The catch is that tail recursion optimization can change the nature to prevent this expansion and tracking of extra information, in other words, evaluate as it goes since part can be evaluated and is not needed for the outcome. It's just something to keep conscious of so your fold doesn't swallow your computer's memory whole.

Thursday, March 21, 2013

Polymorphism

Back when I first started programming, I was originally working in Java. One of the concepts we touched on was polymorphism. For a long time after that when I moved on to other languages, I never really understood what it was or how to use it. Then one day it just clicked, it all made sense (the basic idea of it, at least), and I saw how to use it. People I help who are just learning to program get caught on concepts like these, and fall to misconceptions making the idea seem useless and they go about in some strange manor of doing things that could be simplified. So, what is polymorphism?

To understand polymorphism, you must first understand inheritance. For the moment, we will look at object oriented programming. Inheritance is when you create a class that extends another class. The inheritance part is when it inherits the methods of the class it is extending. Let us look at a quick example in Python.

class Parent (object):
    def parentMethod(self):
        pass

class Child (Parent):
    def childMethod(self):
        pass

In this example, the Child class extends the Parent class. The parent extends the object in Python, which is just something you should do when making a base class. The Parent class has the method parentMethod. This method is also in the Child class due to inheritance because Child extends the Parent class. However, Parent does not contain the childMethod, as this is something that was created in the Child class. Some languages also support multiple inheritances,  but don't worry about that until you get down basic inheritance.

If you're wondering how this could be in anyway useful, the best example I can think of is game entities. By creating a base mob class, you could then use inheritance to quickly create different types of mobs, but still keep a basic framework, shortening your code and keeping it clean and easy to maintain.

So, how does this tie into polymorphism? Well, polymorphism involves overriding inherited methods. So after we extend a class, we then override a method that was inherited, thus changing it slightly, yet still remaining the same. It is a bit confusing, so let's see an example. Since polymorphism always reminds me of when I played WoW, let's turn a person into a sheep.

class Person (object):
    def __init__(self):
        self.position = 0

    def walk(self):
        self.position += 1

    def talk(self):
        print "Hello!"

class Sheep (Person):
    def talk(self):
        print "Ba-a-a-a-ah!"

We now turned a person into a sheep. Like a person, a sheep can walk. Unlike a person, sheep don't speak words like we do, they make sheep sounds, so clearly we needed to change what they would say when they talk. Thus, the person and a sheep both walk and talk, the difference here is what they say.

The use in this is to allow extending a base class, but without being restricted to the default behaviour of the base class. So if we go back to the game example, we have a mob base. Now let's say we want to make a boss mob, but to do so, that would require changing part of the base mob just for the boss. Well, rather than say ignoring that one method and copy-pasting it into all the other mobs or creating some intermediate mob class just for one method, we can just polymorph the boss class.

Polymorphism also isn't specific to object oriented programming, although that is where it seems to be the most prevalent. Haskell also support polymorphism, however this is in relation to typeclasses as apposed to objects. This concept is very similar, and looks something like this.

data Tree a = Empty | Node {
    nodeValue :: a,
    nodeLeft :: Tree a,
    nodeRight :: Tree a
} deriving (Show)

instance (Eq a) => Eq (Tree a) where
    Empty                   == Empty                = True
    Node {nodeValue = x}    == Node {nodeValue = y} = x == y
    _                       == _                    = False

The deriving part is where I am just extending a type class, but for where the way it does so is less than ideal, you create and instance. An instance is where you create custom behaviour by overriding the default functions of the type class. This means a function of a type class can be used on custom data type, so you do not need to create all your own functions, this makes code a bit more versatile and friendly.

Tag Cloud

.NET (1) A+ (1) addon (6) Android (3) anonymous functions (5) application (9) arduino (1) artificial intelligence (2) bash (3) c (7) camera (1) certifications (1) cobol (1) comptia (2) computing (2) css (2) customize (15) encryption (2) error (15) exploit (13) ftp (2) gadget (2) games (2) Gtk (1) GUI (5) hardware (6) haskell (15) help (5) HTML (4) irc (1) java (5) javascript (20) Linux (18) Mac (4) malware (1) math (8) network (5) objects (2) OCaml (1) perl (4) php (8) plugin (6) programming (42) python (24) radio (1) regex (3) security (21) sound (1) speakers (1) ssh (1) telnet (1) tools (11) troubleshooting (1) Ubuntu (3) Unix (4) virtualization (1) web design (14) Windows (6) wx (2)