Keith's Blog

Darcs: No server, no problem...

2010-04-26T20:23:00.000-07:00

I was explaining to someone I work with today how darcs could be used for collaboration without having a public repo server. I haven't seen this work flow described elsewhere so maybe it will be useful to someone. There are a couple of reasons you might want to do version control sans-server.

Your local IT department frowns upon setting up public facing servers and you have collaborators that live outside the firewall
You don't have a spare server or domain name
You just don't want to bother with it

But this approach still only makes sense if your code is private (if your code is open source the simplest thing for you to do is upload your repo to patch-tag and follow the typical work flow). For the purposes of this example let's imagine that Bill Gates and Steve Jobs want to collaborate on an Android App for finding and sharing info about yard sales.

Example Sans-Server Workflow:
Bill starts hacking on his app "YardSale!" and decides to track it with darcs:

billg ~/yardsale_working> darcs init
billg ~/yardsale_working> darcs add --recursive *
billg ~/yardsale_working> darcs record --all

Bill tells Steve about his idea and Steve wants to help out so Bill creates a proxy repo which will act as a kind of stand-in for a public repository (it should be clear why soon). And sends the patches to Steve.

billg ~/> mkdir yardsale_proxy
billg ~/> cd yardsale_proxy
billg ~/yardsale_proxy> darcs init
billg ~/yardsale_proxy> cd ../yardsale_working
billg ~/yardsale_working> darcs send --to=steve@apple.com --remote-repo=../yardsale_proxy
billg ~/yardsale_working> darcs push ../yardsale_proxy

--remote-repo tells darcs to send any patches that are not in yardsale_proxy. Since yardsale_proxy is now empty, it mean send everything! Steve now needs to create his own proxy repo and apply Bill's patch file:

stevej ~/> mkdir yardsale_proxy
stevej ~/> cd yardsale_proxy
stevej ~/yardsale_proxy> darcs init
stevej ~/yardsale_proxy> darcs apply bills-initial-patches.dpatch
stevej ~/yardsale_proxy> cd ..
stevej ~/> darcs get yardsale_proxy yardsale_working

Steve works on integrating YardSale with google maps in his yardsale_working directory. When he's ready to share these changes with Bill he does something like:

stevej ~/yardsale_working> darcs record
stevej ~/yardsale_working> darcs send --to=bill@microsoft.com
stevej ~/yardsale_working> darcs push

The send command knows to compare yardsale_working to yardsale_proxy and prepare and send a patch email based on the differences it finds. Those differences are of course all of Steve's patches that Bill hasn't seen yet. Also notice that we didn't need to explicitly supply --remote-repo this time because darcs is smart enough to use the last "get" repo by default. The push just updates the proxy repo so that next time Steve does a send no old patches are sent again. Don't worry though. If you forget to push darcs is smart enough to ignore redundant patches.

Bill gets the email and downloads the patch file. Now he needs to apply the patch file to the proxy repo and pull those changes into the working repo:

billg ~/yardsale_proxy> darcs apply google-maps-integration.dpatch
billg ~/yardsale_proxy> cd ../yardsale_working
billg ~/yardsale_working> darcs pull

Now Bill and Steve are synched up with the same patches. You can probably see how this would work pretty much the same way with a group of people sharing patches. darcs is cool!

Edit: reworked the workflow (why do I always realize there is a better way after hitting Publish Post??)

TxtSushi 0.5.1

2010-03-07T13:56:00.000-08:00

I've just released TxtSushi 0.5.1 on hackage. The only reason for this release was to update the license from GPL to BSD (there are no new features or fixes).

I initially released under GPL because I wasn't really sure where I wanted to go with TxtSushi and I knew it was easier to go from GPL to a more liberal license than to move in the other direction. A recent thread on licensing on haskell cafe convinced me that BSD is the way to go.

Getting Started with F# and OpenGL on OS X

2010-01-30T15:36:00.000-08:00

I am exploring programming with F# using mono on OS X. I'm thinking about using F# for a computer vision project and so I wanted to start out by playing around with some example code to see how it all works. This post is just to document the steps to get up and running. I'm a complete newbie to F# and mono so please give feedback if there are better ways to go about what I'm doing. I'd also like to eventually have a build environment that works well with mono on OS X and MS Visual Studio. Please leave a comment if you have any advice on this.

Initially I installed mono 2.6.1. using the OS X Intel installer which worked without any issues.
Next I downloaded and unzipped the F# 1.9.7.8 zip file from the F# downloads page. The zip file contains a convenient install-mono.sh script so all you have to do is
```
chmod +x install-mono.sh && sudo ./install-mono.sh
```
I decided to create bash scripts for the compiler and interpreter just for the sake of convenience:
```
mv FSharp-1.9.7.8 ~/bin/
```
The contents of ~/bin/fsc.bash:
```
#!/bin/bash

mono `dirname $0`/FSharp-1.9.7.8/bin/fsc.exe "$@"
```
... and likewise the contents of ~/fsi.bash:
```
#!/bin/bash

mono `dirname $0`/FSharp-1.9.7.8/bin/fsi.exe "$@"
```

OK great, we now have a working F# compiler and interpreter on OS X (make sure that ~/bin is on your $PATH though... you already knew that didn't you?). OK now let's try to work with one of the F# Samples to make sure things are working as expected. We can build and run the Samples101 example with this command:

fsc.bash --resource:SampleForm.resx \
    sample.fs sampleform.fs Beginners.fs \
    intermediate.fs program.fs
mono program.exe

hmm... almost there. It looks like there is a hard-coded "..\..\" that gets inserted in source code path. A minor code change in sample.fs fixes that:

60c60,61
<         let dir = System.IO.Path.Combine(appdir, @"..\..\")
---
>         //let dir = System.IO.Path.Combine(appdir, @"..\..\")
>         let dir = appdir

... now for a second try:

That's better. OK, now let's see about getting an OpenGL example running.

First I downloaded the TAO Framework (version 2.1.0) which provides .NET bindings to OpenGL and other API's for gaming

You can install all of the libraries into mono's global registry by:

cd $TAO_HOME/bin
for file in *.dll; do sudo gacutil -i $file; done

hmm, I get the following error while trying to install FreeType:

Installed Tao.FreeType.dll into the gac (/Library/Frameworks/Mono.framework/Versions/2.6.1/lib/mono/gac)

** (/Library/Frameworks/Mono.framework/Versions/2.6.1/lib/mono/2.0/gacutil.exe:253): WARNING **:
Error parsing  \x87\xa0: Error on line 3 char 46: 'libglfw.so"' is not a valid name: '"'

I'm going to ignore this for now since it doesn't seem to matter for my simple example code.

OK now let's translate the simplest TAO example to F# and see about getting it to run. This is a translation of the $TAO_HOME/source/examples/Redbook/Hello.cs example which is under the MIT License (see license text at end of post). Apologies for the lack of syntax hilighting:

open System
open Tao.FreeGlut
open Tao.OpenGl

let init () =
    // Select clearing color
    Gl.glClearColor (0.0f, 0.0f, 0.0f, 0.0f);

    // Initialize viewing values
    Gl.glMatrixMode Gl.GL_PROJECTION;
    Gl.glLoadIdentity ();
    Gl.glOrtho (0.0, 1.0, 0.0, 1.0, -1.0, 1.0)

let display () =
    // Clear all pixels.
    Gl.glClear Gl.GL_COLOR_BUFFER_BIT;

    // Draw white polygon (rectangle) with corners at (0.25, 0.25, 0.0) and
    // (0.75, 0.75, 0.0).
    Gl.glColor3f (1.0f, 1.0f, 1.0f);
    Gl.glBegin Gl.GL_POLYGON;
        Gl.glVertex3f (0.25f, 0.25f, 0.0f);
        Gl.glVertex3f (0.75f, 0.25f, 0.0f);
        Gl.glVertex3f (0.75f, 0.75f, 0.0f);
        Gl.glVertex3f (0.25f, 0.75f, 0.0f);
    Gl.glEnd ();

    // Don't wait!  Start processing buffered OpenGL routines.
    Gl.glFlush ()

// Declares initial window size, position, and display mode (single buffer and
// RGBA).  Open window with "Hello" in its title bar.  Call initialization
// routines.  Register callback function to display graphics.  Enter main loop
// and process events.
let main =
    Glut.glutInit ();
    Glut.glutInitDisplayMode (Glut.GLUT_SINGLE ||| Glut.GLUT_RGB);
    Glut.glutInitWindowSize (250, 250);
    Glut.glutInitWindowPosition (100, 100);
    ignore (Glut.glutCreateWindow "Hello");
    init ();
    Glut.glutDisplayFunc (new Glut.DisplayCallback(display));
    Glut.glutMainLoop ()

[<STAThread>]
do main

Now I just compile and run with:

fsc.bash -I $TAO_HOME/bin -r Tao.OpenGl.dll -r Tao.FreeGlut.dll hello.fs
mono hello.exe

Hey, it works! That wasn't so painful.

MIT License Copyright 2003-2005 Tao Framework Team http://www.taoframework.com All rights reserved. Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions: The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software. THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

Simple Recipe for Static Domain Hosting With Blog

2010-01-10T10:13:00.000-08:00

Hopefully this post will help save someone time looking for similar hosting. My current hosting requirements are really simple. I need:

static site hosting for keithsheppard.name
blog hosting for blog.keithsheppard.name

Luckily blogger lets you use your own domain which takes care of blog.keithsheppard.name so I just need to find a static hosting service for keithsheppard.name. When I went looking for hosting though almost everything I found allows you to run at least PHP, perl scripts along with a MySQL database and costs $5/month or more. Using these hosts means that you have to pay for the extra resources, security and maintenance that goes along with allowing scripts and DB's to run. Another problem is that the cheaper services are often under-resourced which means added down time for you.

After a lot of trial and error I found hurricane electric $1/month static site hosting which has just worked with no problems worth mentioning. As a bonus you transfer your files using scp instead of the lame web-based file managers a lot of the other hosts make you use. HE also throws in a free domain name but I have my domain under dotster and I like keeping the hosting and name registration separate (that costs me an extra $15/year). So for what it's worth, this configuration has worked well for me.

TxtSushi 0.5.0

2009-12-30T17:09:00.000-08:00

Hiya! I've uploaded TxtSushi 0.5.0 to hackage and there are quite a few changes. I still need to update the documentation on http://keithsheppard.name/txt-sushi which probably won't happen for a week or so (Edit: I have made the updates) but I'll summarize the changes here:

generalized the JOIN syntax to allow joins on arbitrary expressions (you used to only be able to join on column IDs). This test script demonstrates a join on a simple expression
added initial support for the "for x in [col1 .. col4] yield expr" syntax. See this test script for an example of how it works.
parser now works with UNIX, DOS and Mac newlines no matter which OS you're working on
added integrated help for all SQL functions and operators. Use "tssql -help" to get a list of all functions and operators. Use "tssql -help sum" to get help on the SUM function
added many new function definitions
Grouped data syntax generalization: you can now group tables multiple times (via nested selects) and join those grouped tables to other tables (grouped or not). You can even mix grouped and non-grouped columns in the same expression.
Many bug fixes and code simplifications (still learning how to write good Haskell). Most notably it is now very easy to extend tssql with new SQL functions and operations. Here's an example of what it takes to add a new function.
added support for bool constants in SQL expressions
improved error messages
Declared the "classic join" performance bug a feature :-)
and most importantly: changed the synopsis to "The SQL link in your *NIX chain"

Have fun and please send me your bug reports!

TxtSushi 0.4.0

2009-10-04T14:39:00.000-07:00

I have just uploaded version 0.4.0 of TxtSushi with the following changes:

General code improvements: fixed any -Wall warnings, improved help messages and SQL parser error messages
External sort: added an -external-sort option to tssql which tells tssql to sort on disk for JOIN and ORDER BY. This was tested on a 10G CSV file and it worked but it took 10 hours on my macbook! I think that this can be improved.
Nested select: TxtSushi now allows nested select statements
Classic joins: added support for older style join syntax. These joins are still unoptimized though so their time complexity is row_count^2 rather than the row_count(log row_count) complexity when using the INNER JOIN syntax
Transpose utilities: added transposecsv and transposetab utilities which will print a transposed version of the given table

Fellow Haskell Hackers Wanted:

I think TxtSushi fills a unique niche in the *NIX toolchain for tabular data. On one side you have python, perl, sed, awk which are all great for general purpose text processing but it takes a lot of hand rolled code to do table filtering/joining/transformation and it gets even worse if you want to be able to deal correctly with quoted fields. On the other side you have real databases which allow you to do all of these things but which tend to be heavyweight solutions that require data import/export and don't want anything to do with your other *NIX commands. TxtSushi is different because it takes your text tables (or event STDIN) as they are and doesn't want to be anything more than an SQL link in your *NIX tool chain.

The two long term goals that I have for TxtSushi are to improve it to the point where it is generally available on *NIX distro package managers and that it is "owned" and developed by a group instead of just me. These two goals really go together since I may not be able to do all of the work required to mature TxtSushi by myself. I thought about keeping these goals to myself until I could get to the point where the core architecture are solidified and the remaining work would amount to developing and integrating modules into the existing architecture, but I think things are just moving too slowly with me hacking alone. So, if you are interested in hacking TxtSushi with me let me know!

Off the top of my head here are some relatively self-contained contributions that can be made:

Extensible SQL Functions: This one should be fun. The way I implemented SQL functions isn't very pretty. The function parsers are in SQLParser.hs toward the bottom and the SQL Function execution code is in a big function guard toward the bottom of SQLExecution. I think we should have an SQLFunction type which would bundle up both the parsing and execution for a single SQL function/operator. The real payoff is that we could then have an XMonad-like configuration file that allows users to define their own SQL functions (Eg: if a user wants to define a STD_DEV aggregate function, now they can as long as they know haskell).
Improve table parsing: the table parsing code was the first thing I wrote and it shows. It should be replaced by something more like what you find in Real World Haskell: Using Parsec which is much more concise and tolerant of any end-of-line encoding
External sort: The external sort algorithm works but could probably use a more expert Haskell hacker's eye to become efficient (there were a couple of reasons I couldn't just use the external-sort cabal library as-is).
Efficient classic joins: The classic style WHERE joins should be just as efficient as the INNER JOIN joins. If you're interested in this I have an idea for what I think may be the easiest way to do this. See issue 7
Support for SQL Case Statement: See issue 8
Implement window functions like RANK() and ROW_NUMBER(): See issue 11
Test cases? Bug reports? Some other idea you have? ...

If you're curious, the simplest way to browse the source is here http://patch-tag.com/r/keithshep/txt-sushi.

Server Died!

2009-08-12T16:27:00.000-07:00

Update 1: The site is back up and running, hosted by izfree.com

Update 2: izfree.com was not working out so I switched to he.net. It's $1 per month for static file hosting. I'll report back after a while on how he.net is going.

I've been serving up my website on the cheap using dynamic DNS and a spare linux box at home. My linux box just died so my main site is down :-(. Luckily my blog is hosted by blogger which is why it's still doing fine.

I don't suppose anyone knows a good way to host a web site for free assuming all the content is just static pages? I need to be able to come with my own domain name too. I think I'm going to have to finally break down and actually spend money on hosting.

Bird Tracks Through Math Land: Gaussian Elimination with Back Substitution

2009-07-22T20:31:00.001-07:00

Last time we went over some basic matrix operations and this time around we will talk about how Gaussian Elimination works starting with the concepts and working into an implementation using Haskell. Gaussian Elimination is an algorithm that can be used to solve a system of linear equations. Let's forget about matrices for a now and just get a feel for how this works with equations. Suppose you are given the following linear equations:

2x  + y  + z = 1    (L1)
4x  + 3y + z = -1   (L2)
-2x + 2y + z = 7    (L3)

and you are asked to solve for x, y and z. Gaussian Elimination gives you a systematic way of finding the solution. The first major step is to "zero out" the lower triangle of coefficients. So we want the x coefficient from L2 to be 0 and we want the x and y coefficients from L3 to be zero.

Step 1.1: We'll zero out the x coefficient in L2 by subtracting 2*L1 giving us L2'

0x + y - z = -3     (L2')

Step 1.2: We can zero out x in L3 by adding L1 giving us L3'

0x + 3y + 2z = 8    (L3')

Step 1.3: Now we can eliminate y from our modified L3' by subtracting 3*L2' giving us L3'':

0x + 0y + 5z = 17   (L3'')

You'll notice a pattern forming by step 1.3. Because we're multiplying L3' by a factor of L2' both of which already have 0x coefficients we can be sure that any choice we make to zero out the y coefficient will still leave us with a zero x coefficient in L3''.

Lets take a look at our new equations in with zero coefficients under the diagonal (triangular form)

2x + y  + z  = 1    (L1)
0x + y  - z  = -3   (L2')
0x + 0y + 5z = 17   (L3'')

OK cool, now we can use back substitution to solve for z, y and x (in that order).

Step 2.1: Solve for z using L3''

5z = 17
z = 17/5 = 3.4

Step 2.2: Solve for y using L2' and the value of z we just calculated

y - 3.4 = -3
y = 0.4

Step 2.3: Solve for z using L1 along with our calculated z and y:

2x + 0.4 + 3.4 = 1
2x = -2.8
x = -1.4

Done!

Well, sort of... There is one special case that we need to account for. Let's repeat our example after changing the x coefficient in L2 to 6.

2x  + y  + z = 1    (M1)
6x  + 3y + z = -1   (M2)
-2x + 2y + z = 7    (M3)

We can zero out the x column as before

At this point we're supposed to zero out the y coefficient in M3' by adding a multiple of M2' but that's not possible because the y coefficient in M2' is 0. The way we fix this is by having one of the equations below M2' with a non-zero y coefficient take M2's place. In this particular case M3' is our only option.

2x + y  + z  = 1    (M1)
0x + 3y + 2z = 8    (M3')
0x + 0y - 2z = -4   (M2')

And after solving with back substitution:

x = -7/6 = -1.1666
y = 4/3 = 1.333
z = 2

In this case we're done diagonalizing the linear equations (if there were more coefficients to zero out we would just keep going as before).

> module Math.BTTML.GaussianElimination (
>   solveWithGaussAndBackSub,
>   gaussianElimination,
>   backSubstituteUpper,
>   backSubstituteLower) where
>
> import Data.List
> import Math.BTTML.BasicMatrixOps

One last thing before we move into code. All of the coefficients on the left hand side will be represented as a matrix and all of the values on the right hand side will be represented as a column vector. For example, our initial system of linear equations (L1, L2 and L3) can be represented as:

> lCoefMatrix =
>   [[2.0,  1.0, 1.0],
>    [4.0,  3.0, 1.0],
>    [-2.0, 2.0, 1.0]]
>
> lRHSVector = [1.0, -1.0, 7.0]

and our M equations can be represented as

> mCoefMatrix =
>   [[2.0,  1.0, 1.0],
>    [6.0,  3.0, 1.0],
>    [-2.0, 2.0, 1.0]]
>
> mRHSVector = [1.0, -1.0, 7.0]

Now for the code to implement the concepts we just went over.

> solveWithGaussAndBackSub coefMat rhsVec =
>   let (gaussElimCoefMat, gaussElimRHSVec) = gaussianElimination coefMat rhsVec
>   in backSubstituteUpper gaussElimCoefMat gaussElimRHSVec

"zero out" the lower triangle of the given coefficient matrix using the gaussian elimination method

> gaussianElimination :: (Fractional a) => [[a]] -> [a] -> ([[a]], [a])
> gaussianElimination [] [] = ([], [])
> gaussianElimination [] _ = error "Matrix row count is greater than right hand size!"
> gaussianElimination _ [] = error "Matrix row count is less than right hand size!"
> gaussianElimination coefMat rhsVec =
>   let
>       -- work on zeroing out the leftmost coefficients in all equations
>       -- below the top (ie below topCoefs). The ensureNonZeroFirstCoef
>       -- function helps us deal with the special case where the first
>       -- coefficient is zero
>       (topCoefs:otherCoefsMat, topRHSVal:otherRHSVals) =
>           ensureNonZeroFirstCoef coefMat rhsVec
>       zeroOutFactors = map (zeroOutFactor topCoefs) otherCoefsMat
>      
>       zeroOutCoefMatAddends = zipWith (map . (*)) zeroOutFactors (repeat topCoefs)
>       zeroedOutCoefMat = otherCoefsMat `matAdd` zeroOutCoefMatAddends
>      
>       -- now calculate the right-hand-side to go along with the
>       -- zeroed out coefficients
>       zeroOutRHSAddends = map (topRHSVal *) zeroOutFactors
>       zeroedOutRHS = eqZipWith (+) otherRHSVals zeroOutRHSAddends
>      
>       -- now that the leftmost coefs are zero we need to recurse into the
>       -- lower right corner
>       lowerRightMat = map tail zeroedOutCoefMat
>       (newLowerRightMat, newLowerRHS) = gaussianElimination lowerRightMat zeroedOutRHS
>      
>       -- OK now we just have to zip it up like we need
>       newLowerMat = eqZipWith (:) (map head zeroedOutCoefMat) newLowerRightMat
>       finalMat = topCoefs:newLowerMat
>       finalRHS = topRHSVal:newLowerRHS
>   in
>       (finalMat, finalRHS)

this function is just to make sure that the left-most coefficient is non-zero. If the 1st leftmost coefficient is zero in the 1st row then that row is swapped with the 1st row that has a non-zero starting coefficient

> ensureNonZeroFirstCoef coefMat rhsVec =
>   let firstNonZeroIndex = findIndex ((/= 0) . head) coefMat
>   in case firstNonZeroIndex of
>       Just 0  -> (coefMat, rhsVec)
>       Just i  -> (zeroSwap i coefMat, zeroSwap i rhsVec)
>       Nothing -> error "Failed to find non-zero coefficient!"
>   where zeroSwap i xs =
>           let (start, finish) = splitAt i xs
>           in head finish : start ++ tail finish

the zeroOutFactor determines the factor that should be used to zero out the left-most coefficient in otherCoefs

> zeroOutFactor :: (Fractional a) => [a] -> [a] -> a
> zeroOutFactor topCoefs otherCoefs =
>   let topLeftCoef = head topCoefs
>       otherLeftCoef = head otherCoefs
>   in negate $ otherLeftCoef / topLeftCoef

Solve a matrix that is zeroed out below the diagonal using back substitution. This function delegates all the real work to backSubstituteLower.

> backSubstituteUpper upperTriangleMat rhsVec =
>   let
>       -- reverse column and row order in the matrix, then reverse the RHS
>       revMat = reverse $ map reverse upperTriangleMat
>       revRHS = reverse rhsVec
>   in
>       -- now we can back substiture as a lower triangle matrix, reverse
>       -- the result and we're done!
>       reverse $ backSubstituteLower revMat revRHS

solve a matrix that is zeroed out above the diagonal using back substitution

> backSubstituteLower lowerTriangleMat rhsVec = go [] lowerTriangleMat rhsVec
>   where
>       go _ [] [] = []
>       go prevSolutions (matHead:matTail) (rhsHead:rhsTail) =
>           let (solved, (solveNow:solveLater)) = splitAt (length prevSolutions) matHead
>               subRHS = rhsHead - (sum $ eqZipWith (*) prevSolutions solved)
>               solution = subRHS / solveNow
>           in
>               solution:(go (prevSolutions ++ [solution]) matTail rhsTail)
>
>       -- If we haven't hit one of the previous patterns that means that the
>       -- row is different than the RHS count
>       go _ _ _ =
>           error "Matrix row count doesn't match right hand side length!"

That should do it. You can test it by invoking:

> test1 = solveWithGaussAndBackSub lCoefMatrix lRHSVector

> test2 = solveWithGaussAndBackSub mCoefMatrix mRHSVector

MySQL responds to the threat ...

2009-06-19T18:24:00.000-07:00

... posed by TxtSushi's foray into the database market. http://dev.mysql.com/tech-resources/articles/csv-storage-engine.html In all seriousness, this looks like a really nice solution.

HaExcel

2009-06-18T19:13:00.000-07:00

I stumbled upon HaExcel today and thought "Wow! This sounds just like TxtSushi." After looking more closely it has important differences. It handles import/export between spreadsheet and database rather than directly performing queries on a set of spreadsheets. If you're looking to bridge spreadsheets and databases you should give it a look.

BTTML repository

2009-06-13T06:25:00.000-07:00

The BTTML darcs repository is up at http://patch-tag.com/r/bird-tracks-through-math-land/home The blog posts will be updated with the latest version if I make any changes, but you can browse the entire history of modifications from the repository.

Bird Tracks Through Math Land: Basic Matrix Ops

2009-06-12T17:28:00.000-07:00

Math scares me. I hate to say it but it's true. I write software for super smart researchers/scientists who are solving all kinds of complex mathematical problems in computational biology and this discomfort with math has become a limiting factor in how much I can contribute to my group. So, it's time for me to fix the problem.

I don't learn well from just reading books on math. I have tried it. I always end up feeling like I've learned a few rules but I don't really "get" it. I need to have a sense for what the small pieces are and how they all fit together to form a larger system of high level abstractions/components. That's how I build software and it's the only way I am comfortable learning technical concepts. That's what got me thinking about "Bird tracks through math land". The best way for me to learn these concepts is to implement them! If you build something you have to understand it right?

I am going to do this is through a series of Literate Haskell posts. The idea is to take it slow, and explain things as fully as possible. In the end I would like to have a series of math tutorials/notes that also happen to be working code (there is nothing like a compiler to keep you honest!). My hope is that these notes will be almost completely self contained and should not require much more math background than what you get in high school. You will have to be able to read the Haskell source code though (I very highly recommend Learn You a Haskell for anyone new to Haskell).

A bit of background for anyone who is not familiar with Literate Haskell:

Haskell is a purely functional programming language. That means that the output of a function is completely determined by it's inputs (no cheating with hidden state). This aligns closely with the mathematical definition of a function, but is very different from main stream languages like C, Java ...
Haskell's syntax is beautiful and extremely concise. It is nearly as expressive as writing pseudocode which makes it perfect for this kind of project.
You're reading Literate Haskell source right now... Seriously! I wouldn't lie to you. Literate Haskell treats every line that does not start with a '>' (AKA bird track) as a comment. Quoting Dr. Knuth, who conceived Literate Programming "The main idea is to regard a program as a communication to human beings rather than as a set of instructions to a computer." Which is exactly what I am trying to achieve.

The road map for "Bird tracks through math land" is still up in the air, but for now I plan on starting with Linear Algebra and working my way toward its applications in probability and statistics. I am also very interested in Bayesian Networks so I think we'll head down that path later.

OK, enough blah blah. Lets get to it. We'll start by defining the basic matrix operations.

> module Math.BTTML.BasicMatrixOps (
>           dotProd,
>           matAdd,
>           matSub,
>           matMult,
>           eqZipWith,
>           matZipWith) where
>
> import Data.List

Let's define our own version of Haskell's zipWith function. eqZipWith applies the function f to each corresponding pair of elements in the given lists. It is just like Haskell's version, except that eqZipWith requires that the list lengths match.

> eqZipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
> eqZipWith f (x:xs) (y:ys) = (f x y):(eqZipWith f xs ys)
> eqZipWith f [] [] = []
> eqZipWith _ _ _ = error "List sizes should match"

Now let's create a matrix zip function. It applies a function f to each pair of corresponding elements from the two given matrices.

> matZipWith :: (a -> b -> c) -> [[a]] -> [[b]] -> [[c]]
> matZipWith f matrix1 matrix2 = eqZipWith (eqZipWith f) matrix1 matrix2

Subtract matrix1 from matrix2. This is an element-by-element operation.

> matSub :: (Num a) => [[a]] -> [[a]] -> [[a]]
> matSub = matZipWith (-)

Matrix addition works pretty much the same way

> matAdd :: (Num a) => [[a]] -> [[a]] -> [[a]]
> matAdd = matZipWith (+)

The dot product (AKA scalar product) of two vectors is the sum of the product of each pair of elements. The vectors have to be the same length.

> dotProd :: (Num a) => [a] -> [a] -> a
> dotProd vector1 vector2 = sum $ eqZipWith (*) vector1 vector2

The wikipedia page on matrix multiplication is great: http://en.wikipedia.org/wiki/Matrix_multiplication

The most important points are:

The row count of the resulting matrix is determined by the row count of matrix1
The column count of the resulting matrix is determined by the column count of matrix2
element[i, j] of the resulting matrix is calculated by taking the dot product of the ith row vector from matrix1 and the jth column from matrix2. Also note that because these two vectors must be the same length, the column count of matrix1 must equal the row count of matrix2.

In order to simplify the matrix multiplication we will transpose matrix2 (moves element[i,j] to element[j,i]) which makes it trivial to pull out column vectors

> matMult :: (Num a) => [[a]] -> [[a]] -> [[a]]
> matMult matrix1 matrix2 =
>   [[row1 `dotProd` col2 | col2 <- transpose matrix2] | row1 <- matrix1]

Now here are a couple of tests:

> testMat1 =
>   [[2, 0, -1, 1],
>    [1, 2, 0, 1]]

> testMat2 =
>   [[1, 5, -7],
>    [1, 1, 0],
>    [0, -1, 1],
>    [2, 0, 0]]

> testAdd = testMat1 `matAdd` testMat1
> testSub = testAdd `matSub` testMat1
> testMult = testMat1 `matMult` testMat2

Next time we'll solve linear equations with gaussian elimination

Updates: Applied CSS colors and made some code changes suggested by Conal

TxtSushi 0.3.0

2009-05-31T19:17:00.001-07:00

Just released TxtSushi 0.3.0 which adds:

Improved SQL parsing and error reporting
GROUP BY ... HAVING support with several aggregate functions (see home page)
A little utility "namecolumns" which will add sequential column names to a table which is useful if your flat file doesn't have a header with column names.

haskell & music

2009-05-24T06:04:00.000-07:00

This guy created a pretty cool command line interface to make music with text http://yaxu.org/haskell-hack

TxtSushi 0.2

2009-05-21T20:20:00.000-07:00

I just released TxtSushi 0.2 with the following updates:

Improved type coercion. Some of the rules I was using before did not make sense. At some point I will write down what the rules are.
Added some extra functions/operators including a regex matcher. Here is the full list: SUBSTRING, UPPER, LOWER, TRIM, *, /, +, - (binary and unary), =, <> (not equal test), <, <=, >, >=, AND, OR, || (string concatination), =~ (regex matching)

Yay! TxtSushi 0.1

2009-05-16T19:08:00.000-07:00

I just released my first haskell application called TxtSushi. It's basically useful for processing comma-delimited tables with SQL select statements, plus some other small conversion and formatting utilities. Here's an example that I just tried out with real data and ... it works!

wget -q -O - ftp://ftp.informatics.jax.org/pub/reports/MRK_List2.rpt | tabtocsv - \
| tssql -table mgi - \
'select `MGI Accession ID`, Symbol, Chr, trim(`cM Position`)
from mgi where (Chr = 1 or Chr = 8 or Chr = 19) and trim(`cM Position`) = "N/A"
order by Chr+0, Symbol' \
| csvtopretty -

Which gives you:

MGI Accession ID|Symbol                     |Chr|TRIM(cM Position)
MGI:3829209     |100039643                  |1  |N/A
MGI:3823247     |100042382                  |1  |N/A
MGI:3826364     |665246                     |1  |N/A
MGI:3828086     |667118                     |1  |N/A
MGI:3829949     |Bmd5a                      |1  |N/A
MGI:3829954     |Bmd5b                      |1  |N/A
MGI:3829959     |Bmd5c                      |1  |N/A
MGI:3762525     |Drinkcacl24                |1  |N/A
MGI:3762526     |Drinkmgcl21                |1  |N/A
MGI:3762535     |Drinkmgcl24                |1  |N/A
MGI:3762388     |Drinksac5                  |1  |N/A
MGI:3836959     |Mir1927                    |1  |N/A
MGI:3836960     |Mir1928                    |1  |N/A
MGI:3837225     |Mir1981                    |1  |N/A
MGI:98018       |OTTMUSG00000002279         |1  |N/A
MGI:3840135     |OTTMUSG00000020948         |1  |N/A
MGI:3834078     |OTTMUSG00000026591         |1  |N/A
MGI:3826770     |Qrr1                       |1  |N/A
MGI:3826773     |Qrr1d                      |1  |N/A
MGI:3826772     |Qrr1p                      |1  |N/A
MGI:3844119     |Sfp1                       |1  |N/A
MGI:3832320     |T(1E2.1;8B1.2)2Lub         |1  |N/A
MGI:3843694     |Tg(tetO-Chrnb2*V287L)H3Gica|1  |N/A
MGI:3720916     |Tgq9                       |1  |N/A
MGI:3640786     |lrm1                       |1  |N/A
MGI:3822907     |384645                     |8  |N/A
MGI:1924337     |Ankrd11                    |8  |N/A
MGI:3844136     |Arrh1                      |8  |N/A
MGI:3705791     |Defa-ps3                   |8  |N/A
MGI:3837211     |Mir1966                    |8  |N/A
MGI:3837213     |Mir1967                    |8  |N/A
MGI:3837215     |Mir1968                    |8  |N/A
MGI:3837216     |Mir1969                    |8  |N/A
MGI:3833469     |OTTMUSG00000016477         |8  |N/A
MGI:3833836     |OTTMUSG00000031120         |8  |N/A
MGI:3844123     |Sfp3                       |8  |N/A
MGI:3628904     |T(Tp(1E2.1);8B1.2)2Lub     |8  |N/A
MGI:3720925     |Tgq18                      |8  |N/A
MGI:3640782     |gpg6                       |8  |N/A
MGI:88396       |Chrm1                      |19 |N/A
MGI:3762554     |Drinkqhcl2                 |19 |N/A
MGI:3762516     |Drinksac2                  |19 |N/A
MGI:3720096     |Hdlq59                     |19 |N/A
MGI:3837023     |Mir1950                    |19 |N/A
MGI:1914960     |Polr2g                     |19 |N/A
MGI:3843453     |Prdt5                      |19 |N/A
MGI:3828068     |Tgq29                      |19 |N/A

I created this because it is something that will be useful to my work (flat files are just about everywhere you turn in bioinformatics), but I'm really hoping that this will be something that is generally useful to other people.

Happy to be in Maine

2009-05-06T18:58:00.000-07:00

I moved to Maine over a year ago and it is a great place to live for a lot of reasons, but today it's an even better place to live. The governor just signed a bill that makes gay marriage legal! It is also really encouraging to know that this change is taking place within the elected branches of government which shows that we are seeing a popular shift. It looks like opponents to gay marriage are trying to organize a "peoples veto" so we have to keep pushing forward whether that just means talking to friends and family to explain how you feel or possibly volunteering time or money to organizations like EqualityMaine. Also, those of us lucky enough to see things changing in our own states need to keep doing what we can to change things for gay and lesbian families in the rest of the country.

Learning about monads: some suggestions

2009-05-02T21:15:00.001-07:00

So, I'm relatively new to Haskell, and I have to say that monads were a part of the language that took me a while to get comfortable with. This post is not a tutorial... there are already many monad tutorials out on the web that do a better job than I would. Instead this post contains a few of my "lessons learned" about how to best use your time when you are learning monads.

My biggest suggestion is that you understand that there is nothing "special" about monad types. In my initial attempts to learn monads a lot of the material I read left me with the impression that monads somehow play by different rules than the rest of the Haskell language. The monad class is a plain old Haskell class that just happens to define an interface that is very useful for implementing a particular design pattern that shows up often with things like IO and error propagation.
Don't expect to fully understand monads until you feel comfortable with higher-order functions (functions that take functions as arguments) and Haskell's type system (classes). The Learn You a Haskell tutorial is a lot of fun and provides a good introduction to these prerequisites.
The "do" notation is useful for formatting reasons but it can also help to reinforce the idea that monads are somehow special. I recomend that you start learning how to use the >> and >>= functions for monads sooner rather than later so that you will see how monads work in a way that is consistent with the rest of Haskell.
I also think its useful to read some opinions that are critical of monad tutorials so that you can make better decisions about how to spend your time. See: Brent's post on monad tutorials and a blog post on why monad tutorials are awful.

Hello World

2009-04-28T20:18:00.000-07:00

I'll be blogging on life and software. See ya!