Tag Archives: Haskell

Playing with Factorials, Haskell, and Perl

I’m currently making may way through a book called “Seven Languages in Seven Weeks” by Bruce A. Tate.  So far it’s been an interesting read, but I’m far from finished.

One of the things in the book that caught my eye was a recursive factorial function in Haskell, which seemed so simple, that I had to see what it would look like in perl.

So I wrote up the following perl snippets to calculate factorials.  There are, of course, multiple ways to do it as I’ll describe below.  There are also (likely) many other ways which I haven’t thought of, so if you have an interesting solution, please share.

One of the things that really caught my attention was how simplistic the syntax was for writing somthing so complex.  Recursion is a fairly simple idea once you’ve seen it in action – a function that executes itself.  However, the implementation of recursion in a given programming language can be somewhat difficult to comprehend, especially for new programmers or those without programming experience.

Although I haven’t dived into Haskell quite yet, it seems to make implementing a factorial function so simple, that I kind of stumbled when trying to understand it, thinking I was missing something.. but it was all there in front of me!

Firstly, let’s clarify what a factorial is (from wikipedia):

In mathematics, the factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n. For example,

5 ! = 5 \times 4 \times 3 \times 2 \times 1 = 120 \

 

So the factorial of 5 is 120.  Or 5! = 120.   Lets look at the Haskell example from the book.

let fact x = if x == 0 then 1 else fact (x - 1) * x

The above line is saying “if x is 0, then the factorial is 1 – otherwise, call myself with (x – 1), multiplied by x”

Lets look at this in ghci (the Haskell console):

[jbl@watchtower tmp]$ ghci
GHCi, version 7.0.3: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Loading package ffi-1.0 ... linking ... done.
Prelude> let fact x = if x == 0 then 1 else fact (x - 1) * x
Prelude> fact 5
120
Prelude>

After seeing how easy it was to implement the recursive factorial function in Haskell, here are my attempts in perl.

Firstly, using a loop:

#!/usr/bin/env perl
 
use strict;
use warnings;
use feature "say";
 
my $nni = $ARGV[0] ? $ARGV[0] : 5;
 
for my $i ( 1..($nni - 1) )
{
    $nni = $nni * $i;
    say $nni;
}

This first example doesn’t implement a function, and is really just bad (but still working) code. It requires that your base number be global and alterable, in this case $nni.

Now, lets try it with an actual function:

#!/usr/bin/env perl
 
use strict;
use warnings;
use feature "say";
 
my $nni = $ARGV[0] ? $ARGV[0] : 5;
 
sub fact 
{ 
    my ($nni) = @_;
    return !$nni ? 1 : fact( $nni - 1 ) * $nni;
}
 
say fact($nni);

This second method works similarly to the Haskell implementation. It implements a function that calls itself, without any looping required.

However, it’s still not as concise as the Haskell version, so lets try again:

#!/usr/bin/env perl
 
use strict;
use warnings;
use feature "say";
 
my $nni = $ARGV[0] ? $ARGV[0] : 5;
my $fact;
$fact = sub { my ($nni) = @_; !$nni ? 1 : $fact->( $nni - 1 ) * $nni };
say $fact->($nni);

Aha, now we’re getting somewhere. In this third example, the fact() function is anonymous, and we’re assigning it to $fact via reference. This allows us to use $fact like an object with a single method that does the factorial calculation.

Although this is pretty much as concise as I was able to get it while taking readability into account, here’s a final example that goes a step further:

#!/usr/bin/env perl
 
use strict;
use warnings;
use feature "say";
 
my ($nni, $fact);
$nni = $ARGV[0] ? $ARGV[0] : 5;
$fact = sub { !$_[0] ? 1 : $fact->( $_[0] - 1 ) * $_[0] };
say $fact->($nni);

This last example uses perl’s pre-defined variable @_ which automatically holds a list of function arguments by default. I usually avoid doing this, since it hurts readability, especially for those who don’t live and breathe perl on a daily basis.

To my surprise, it would seem that Haskell has Perl beat (at least in this example) as far as readability + conciseness is concerned.

I haven’t spent much time playing golf here to reduce the number of lines or characters beyond the last example, but if anyone does come up with a tighter solution, please let me know!


Edit (20111005T22:43:50): Here’s a version I found that uses the Math::BigInt module

#!/usr/bin/env perl
 
use strict;
use warnings;
use feature "say";
use Math::BigInt lib=>'GMP';
 
my $b = Math::BigInt->new($ARGV[0]);
say $b->bfac();

This version is likely much faster, since the Math::BigInt package is intended to be used in situations where large integers are being handled.

Here’s the post I found with examples written in other languages as well: Factorial Challenge: Python, Perl, Ruby, and C

Xmonad: For Hardcore Desktop User Interface Efficiency

Long time linux/unix hackers know of the plethora of window managers and user interfaces that have been and currently are available for Linux and BSD operating systems.  I’ve had great times in the past trying out different window managers such as Elightenment, Sawfish, Black Box, IceWM, xfwm, KDE, Gnome,  and others.  These days the two most popular which are shipped with the more popular distributions (Fedora, Ubuntu) are KDE and Gnome.

However, I remember back in the day when I was using a Enlightenment, or Ratpoison, doing strange and cool things (at the time) like applying transparencies to your windows and modifying the the window borders to be anything but normal and square.

I used to share screenshots of my desktop with others who are also into “desktop eyecandy”, where I’d have floating or docked window maker panels, and monitoring applets anchored to the desktop as if they were part of the background wallpaper.. and this was around 1999.  It was fun times.

One of the more interesting things that I was into at the time was increasing the efficiency and usability of my desktop by trying to reduce the need to reach for my mouse.  I’ve been very accustomed to this already being user of vi and the GNU Screen terminal multiplexor, but the window managers never seemed to try to attain the same level “hacker cool”.  That is, of course until I came across Ratpoision. Ratpoison was exactly what the name implied, a window manager that killed your dependency on the mouse (or rat).  It was awesome, but it wasn’t scalable and didn’t evolve much to keep up with modern technological advancements and requirements such as multi-monitor support.

I recently thought that those days were long lost, until I recently had the urge to streamline my desktop environment.  I now have a 28″ Monitor, and was certain there was a better way to interact with the desktop than the standard Ubuntu/Gnome environment.  So I went looking.  I started looking of course at things I was already familiar with – I looked up Ratpoision to see if there were any major improvements over the years.

I took a look at a Ratpoison again, but it was showing it’s age.  I looked at it’s successor, Stumpwm, but I didn’t feel the love.  Then I tried out Xmonad, created by Spencer Janssen, Don Stewart, and Jason Creighton – and written in Haskell.  I immediately fell in love.

If you haven’t used GNU Screen, Gnome Multi-Terminal, Ratpoision, or any minimalist Window Manager before, then it will be hard to explain why Xmonad is worth your time.  Instead, visit the Xmonad website here: http://www.xmonad.org/

Here are some suggestions on how get Xmonad working on Ubuntu 8.10:

Install Xmonad:

apt-get install xmonad

We’re going to create another X window session, so that we don’t mess with your existing one. That way, if you don’t like Xmonad, you can go back to using your existing window manager without worrying about breaking your configuration.

Set up your second X window session. Press “ctrl + alt + f2” – this will take you to the command-line terminal where you will start your second X session. Start the session using following command:

xinit -- :1 vt12

This will start up another X session which will sit at virtual terminal 12 – meaning that you have to press ‘ctrl-alt-F12′ to get to it.

Once at your new X session, you should see nothing more than an plain old xterm window. Type “xmonad’, and the terminal window should now be maximized. Xmonad is now running.

Type ‘man xmonad’ to view the help documentation on how to use it.  It’s pretty straight forward, and a joy to use!