Friday, September 28, 2012

Haskell Network not found (Ubuntu)

So for a bit recently, I've been looking into Haskell. I really want to get into some functional programming. On thing I like doing is network programming because it actually gives me something extra to interact with than my own I/O or bugging a friend to help out or check something out. So I gave a quick glance at sockets and wanted to just see what the types look like on ghci, and of course it cannot find anything related to the network package.

> import Network.Socket

:
    Could not find module `Network.Socket':
      it is not a module in the current program, or in any known package.
Leaving GHCi.
$ ghc-pkg field network exposed-modules
ghc-pkg: cannot find package network

After a few minutes of banging my head against my desk, I say screw the gui package manager and just poke around with apt-cache search. Manage to find the library and for some reason, it was not installed by default. So here's what lead me to the package and the quick and easy fix for it.

$ apt-cache search haskell | grep network
libghc6-network-dev - Haskell network library for GHC
libghc6-network-doc - Haskell network library for GHC; documentation
libghc6-network-prof - Haskell network library for GHC; profiling libraries
$ sudo apt-get install libghc6-network-dev

Then problem solved, hoped over to ghci and it's there.

$ ghc-pkg field network exposed-modules
exposed-modules: Network Network.BSD Network.Socket.Internal
                 Network.Socket Network.URI
$ ghci
> :t Network.Socket.socket
Network.Socket.socket
  :: Network.Socket.Internal.Family
     -> Network.Socket.SocketType
     -> Network.Socket.ProtocolNumber
     -> IO Network.Socket.Socket
> 

So yeah, if you run into this, there you go. I think everyone looking into this can probably figure it out on their own, but if not, hopefully this helps. Edited the command stuff to just remove some information and lots of text in between.

Thursday, September 20, 2012

Recursive Fibonacci

So after bashing my head against the wall working on Fibonacci recursively and thinking "why on earth is this so slow," I realized the solution was reducing everything to a lot of ones and adding them all up. While addition and basic arithmetic for a CPU is exceptionally fast, this was slow due to the magnitude, and would cause way too much recursion for it to even be considered a correct solution. So I searched the web figuring someone far smarter than myself would have not only realized this, but come up with a real solution for it. Sure enough, I found one. The solution they used was in C, so I found it a bit ugly as it required two function calls (so you can call it with one argument). So I converted it to Haskell.

Before posting, the short explanation is this. Fibonacci numbers are found by adding up the previous two numbers. This is not to say you should call it inappropriately like this.

fib :: Integer-> Integer
fib 0 = 0
fib 1 = 1
fib x = fib (x - 1) + fib (x - 2)

However, this is often the solution I see in tutorials about recursion and very legitimate sources. I feel the reasoning for this is to use only one function call and as little code as possible to make an "elegant", or at least readable solution. The solution I found, while it is not the prettiest thing, it is far more efficient and very fast and after taking some time to really read it, makes far more sense true to the derivation of Fibonacci numbers. So here is the solution I found and converted to Haskell.

fib :: Integer-> Integer
fib 0 = 0
fib n =
    let
        fib2 1 _ n2 = n2
        fib2 x n1 n2 = fib2 (x - 1) n2 (n1 + n2)
    in
        fib2 n 0 1

Credit to the solution here. Glad to see people finding valid recursive solutions and letting people like myself know there's a better way.

Sunday, September 16, 2012

class vs namespace vs struct

I think one of the hardest concepts to get through to newer programmers is what classes are compared to a namespace or structure. More often than not I hear people asking if a class is just a struct with functions. I have also seen an explanation in a structured program claiming namespaces were like classes and object oriented. While all three of these things can on some level emulate one another, I would like to try and clarify the way to correctly use them, as well as how to emulate one another, which is used for languages that do not have such features.

First thing, namespaces and structs are not objects despite other languages accessing them like such. These are methods for structuring programs and data, not creating objects, which is what classes do. So the question may arise, what is an object? Well, the term is almost exactly the same as the plain English word without any context. Objects, excluding static, are individual things to interact with and manipulate attributes. Until you instantiate, or create a new object from a class, you can only interact with static methods. In a language like Java, all the methods of the Math object are static. This means the method does not rely on an instance, meaning it cannot get or alter any attributes of the object itself. In fact, you can use them without making an instance of the class. I believe this is where the confusion arises making people think a class is a struct, only with functions.

When you make a class, the idea is to create a base for an object, like a mold. So let's say we want to make a ball. First we would make a ball class.

class Ball(object):
    def __init__(self, color):
        self.color = color
    def getColor(self):
        return self.color
    def setColor(self, color):
        self.color = color

With this, we can now create a ball of any color we want. Let us make a red ball.

red_ball = Ball("red")

So now we have a red ball. We can change the color of the ball by red_ball.setColor("blue"), and completely throw off the name scheme I did. As such, the idea is we created a ball and now manipulate it through its functions. While it is true we could do this with a struct, the bottom line is we would not have an object, but instead we would have a data structure. Objects also have inheritance and polymorphism. Inheritance would be when you make a class based on another class, thus any functions and attributes from that class are inherited. In my code, I already included some inheritance by making my class based off of object. This allows access to various attributes that would otherwise not be accessible. Here is another class based off of our Ball class.

class BounceyBall(Ball):
    def setBounceLevel(self, level):
        self.bounceLevel = level
    def getBounceLevel(self):
        return self.bounceLevel

Now you may notice I do not declare all the other functions, however they will be accessible. Thus I would create a BounceyBall the same I created a normal ball. There are also further things you can do such as creating wrapper classes and decorators, but those are way out of scope for the basics. Polymorphism on the other hand, it hard to grasp but very simple. It is basically overwriting a method on a class to use the same base class but create different objects. Here's a quick example copy-pasta style because it would take a while to type out my own.

class Animal:
    def __init__(self, name):    # Constructor of the class
        self.name = name
    def talk(self):              # Abstract method, defined by convention only
        raise NotImplementedError("Subclass must implement abstract method")
 
class Cat(Animal):
    def talk(self):
        return 'Meow!'
 
class Dog(Animal):
    def talk(self):
        return 'Woof! Woof!'
 
animals = [Cat('Missy'),
           Dog('Lassie')]
 
for animal in animals:
    print animal.name + ': ' + animal.talk()
 
# prints the following:
#
# Missy: Meow!
# Lassie: Woof! Woof!

There is mention of an abstract method. This is something that is just there because it needs to be, and must be declared in all descendant classes. Python is a bit loose on these, languages like Java have much more enforcement in such things.

So these are all features that separate classes from structs and namespaces. Now what makes a struct so special? Well a struct is a structured data type. Structs give you the ability to create data down to the binary value and call on them with individual names. With a struct you could store 8 flags in a single byte. A struct packs multiple pieces of data into 1 variable. This can include even pointers. While you can do the same with a class, you cannot show this much control over the data itself. Structs can also use function pointers, which can be similar to a class, however it will be a static function.

Finally to namespaces. Namespaces are a way to separate functions and variables, usually in different files, to prevent clashing or redefining something. They are not objects or structs, but code accessed by a name. They can be used like static classes, but not structs. Namespaces can also house classes.

Now how do you decide when to use which? Well, first you see what the language you are using has to offer. Assuming you have all three, here is how you decide. If you are making a piece of code to represent an object, like a character in a game, use a class. If you are creating a grouping of data, use a struct. If you are creating a grouping of functions and possibly variables, you can use either a namespace (preferably) or a static class.

There are many other language specific details, however these are just my thoughts and conclusions on the matter. To fully utilize a language, learn all of its features and what advantages they have so your code will not only work, but will be efficient.

Saturday, September 8, 2012

Recursion

I've been on another functional programming kick, although I have moved over to OCaml for reasons of performance and still having object oriented sides to it. Either way, it allows recursion, which can make life easier on a lot of things. So I've been working on making things with recursion. Easiest place to start was the challenges over on Project Euler. So I looked at the first two challenges and did them.

Now I want to cover some of the problems I ran into so hopefully someone can be helped by it.  So my first problem always seems to be setting up a limit. The reason this can be a problem is sometimes I forget it's easier to work backwards, especially considering in the end recursion is walked through backwards. The limit can be viewed as similar to the conditional for a loop. Without this conditional, it would go on forever. I find limits a bit easier to do in haskell, but for now I will use Ocaml for practice and show a C equivalent. To do an easy one, let's do Fibonacci number recursively.

let rec fib number =
  match number with
      x when x < 1 -> 0
    | 1 -> 1
    | _ -> fib (number - 1) + fib (number - 2)
;;

In this, I laid out two limits, one is to handle should something just act funny, there is a way to do this a little bit shorter if I want to take away that safeguard, however I will leave it there. The first limit is anything less than one will result in a 0 and the second one is that a one will give you a one. The point of a limit is to show where recursion should end and instead give a value. The final piece is for default behavior and will be where the recursion is. The hard part to follow is in the end you get a whole bunch of ones that are then added together as apposed to the actual numbers. In C, it would look like this.

// With recursion
int fib(int number) {
  if (number < 1) return 0;
  else if (number == 1) return 1;
  else return fib(number - 1) + fib(number - 2);
}
// Without recursion
int fib_loop(int number) {
  int x=0, y=1, z=0;
  for(register int i = 1; i <= number; i++) {
    z = x + y;
    x = y;
    y = z;
  }
  return z;
}

With looping, it is slightly longer and perhaps clearer. In situations like this, the solution of which is best is to use whichever fits the language better. The main thing to note different is the variable tracking. Without recursion, variables need to be tracked and handled. With recursion, you can apply a function to the same arguments without needed to track them. This makes code more modular with a stable interface.

Another catch I ran in to was trying to work backwards based on the return type. The thing with OCaml is there is no return statement. When looking at the C version, it becomes much more clear as to what results where. When confused about the return, remember everything falls back to the limits. When it comes to recursion, all limits must return the same type, even if you work in a language that would allow mixed types. Also all recursive functions must return a value.

Now the end advantage of functional programming style is a more modular code, which means you can reuse a lot of stuff and avoid large, specialized functions. Even in the short time I have been reading about OCaml, I have made a couple functions that I liked in other languages that weren't already included and have recycled them to try out other ways of doing things.

Something else with recursion you may notice is that it is simply repeating the same thing over and over until the some limit hits an end point which will result in the answer. A quick way to make something recursively is to break it down into the smallest steps. Then you can divide everything up in a way that it will repeat the same task to get the answer, all without looping. This is not to say looping is pointless, it is just that with recursion you need only design and interface and apply the logic rather than map out variables and track everything. Here are a couple more recursive functions in OCaml.

(* Add up all items in a list of integers *)
let rec sum l =
  match l with
      [] -> 0
    | [last] -> last
    | head::tail -> head + sum tail
;;
(* create a list of integers in a range *)
let range lower upper =
  let rec mk head tail =
    if head < lower then tail
    else mk (pred head) (head::tail)
  in
  mk upper []
;;

Now the first function, sum, actually starts at the very last item in the list and adds it backwards, this is shown in the limit I call "last" which was named to clarify that. An empty list is also in there because an empty list can be passed to it. The second function, range, creates a list, starting with the last element. Here you may also notice I use a recursive function inside the function because we do not use variables. Instead we use the outer function to create the inner function in a sense. Similarly, a lambda style could be used, however is not because this was easier for me.

In my opinion, I think recursion is a very solid method to do a lot of things and wish it was a bit more developed for other languages. However, I am reading about unrestricted recursion and how to apply it with C, so when I manage to wrap my head around that I will hopefully be able to make use of both imperative and functional means in a way I can use the best solution for each case (so hopefully shorter and clearer code).

Tag Cloud

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