Determinant in Haskell

In linear algebra, the determinant is quite a useful operation that can be done on matrices. To further my understanding of Haskell, I decided to program a solver for systems of equations. One of the best ways to do this dynamically is through Cramer's Rule which needs to be able to calculate determinants. So, here's my recursive code for finding determinants:

determinant :: (Num a, Fractional a) => [[a]] -> a

determinant [[x]] = x
determinant mat =
 sum [(-1)^i*x*(determinant (getRest i mat)) | (i, x) <- zip [0..] (head mat)]

So, in this code, the base case is a 1x1 matrix. The getRest function simply returns the matrix without the head row (topmost) and without the \(i\)th column.

The code and tests are available on my github.

Creating a Sine Function in Haskell

Using Taylor Series derivation I found the following infinite sum expression for sin:
\[
  \sin \left(x \right) = \sum_{i = 1}^{\infty} \frac{x^{2 i - 1}}{\left( 2 i - 1 \right)!} \left( -1 \right)^{i - 1}
\]
The exact derivation is available as a PDF on github.

The translation of this sum into Haskell code was simple:

sin' :: (Num a, Fractional a) => a -> a
sin' x = sum [sinTerm x i | i <- [1..33]]


sinTerm :: (Num a, Fractional a) => a -> Integer -> a
sinTerm x i = (x^oddTerm / fromIntegral (factorial oddTerm))*(-1)^(i-1)
  where oddTerm = 2*i - 1

So, this code is pretty straight forward, if you wanted to get more accuracy on the results you could change "33" to be some greater value (33 says that we will sum up 33-1=32 terms of the taylor series).

Of course this code references factorial which is defined simply as:

factorial :: Integer -> Integer
factorial 1 = 1
factorial n = n * factorial (n-1)

As usual, code and tests are available on github.

Haskell DSA: Quick Sort

Haskell continues to astound me! I have never implemented the quicksort as simply and, frankly, elegantly as this:

quickSort :: (Ord a) => [a] -> [a]

quickSort [] = []
quickSort (x:xs) = quickSort lesser ++ [x] ++ quickSort greater
 where lesser = [e | e <- xs, e < x]
       greater = [e | e <- xs, e >= x]

Here's a quick, line-by-line for anyone who's interested.

• quickSort :: (Ord a) => [a] -> [a]
  The optional (gotta love that word in programming) function definition. It basically says that quickSort is a function that takes a list of objects, [a] and returns another list of a. Ord a means that a is ordinal, or, as far as we're concerned, sortable
• quickSort [] = []
  The first pattern we're trying to match -- if we're given an empty list, return an empty list!
• quickSort (x:xs) = quickSort lesser ++ [x] ++ quickSort greater
  This line does a few cool things: (1) split up a passed list into a first element and remainder, then (2) return the lower ordered elements and the higher sorted on either sides of the first element!
• where less = [e | e <- xs, e < x]
      greater = [e | e <- xs, e >= x]
  This where clause uses list comprehensions to build and define the lists of lower and higher ordered values. Note that the higher values are also (if the case may be) equal to the head of the list (also know as the pivot).

Maybe, Just and Nothing (More Bragging on Haskell)

Man, this Haskell thing is pretty cool. One of (in my opinion) the most annoying things that a programming paradigm can do is consider unexpected behavior to be normal behavior. For instance, most list searches return -1 when the element you are looking for does not exist. Does returning -1 makes sense? No... Not really. Well, anyways, Haskell defeats this type of thing with the following line (this comes with the standard library):

data Maybe a = Nothing | Just a  

Basically all it means is, there's this data type called Maybe (remember, uppercase means constant) and when it is given a type it may just return it or it may return nothing!

This tool is one of the coolest things I have seen in Haskell, thus far. What is the power in this? You can make functions with expected behavior! For instance, consider this quick, binary search I built:

binarySearch :: Ord a => [a] -> a -> Int -> Int -> Maybe Int

binarySearch l e beg last
 | lookat == e = Just i
 | i == (length l)-1 || i == 0 = Nothing
 | lookat < e = (binarySearch l e i last)
 | lookat > e = (binarySearch l e beg i)
 where i = quot (beg+last) 2
       lookat = l !! i

The Maybe, Just and Nothing allow the function to be loose enough that the function can respond with ,"I couldn't find what you were looking for; I found nothing!" This seems to be a huge plus of Haskell. I don't know of many strongly-typed languages that allow this level of Dynamicity.

Functional Fibonaccis in Haskell

Lately, I've been learning my first functional programming language: Haskell. Thus far, it is truly awesome! Look at the following Fibonacci function (I know it's a dead-horse example):

nthFib :: (Integral a) => a -> a
nthFib 1 = 1
nthFib 2 = 1
nthFib n = nthFib (n-1) + nthFib (n-2) 

So, "What makes this simple Fibonacci example so awesome?" you may ask. Well, there are a few things I really like about it, but the main thing is that it actually looks like the mathematical definition for the Fibonacci Series! Also, that first line looks a lot like "nthFib: Z -> Z", you know, that good-old-mathy notation meaning, "nthFib is a function that maps an integer to an integer" (I know, I know, the first 'a' should be a natural number, I'm still getting there). But this is wicked stuff!