22/07/2010
Computer science is a fascinating and maddening thing. Even the most seemingly-esoteric topics turn out to be fundamental. Go out to the fringes of CS and you find yourself smack in the middle of Philosophy. You try to understand a single point and you suddenly find yourself embracing everything.
So this post comes from that infinitely-recursive rabbit hole of wikipedia topics I’ve been falling down for the last few weeks, and you can probably expect a few more like this one; I’ll try to keep focused.
We begin (as do All Good Things) with the Untyped Lambda Calculus:
Read the rest of this article »
24/03/2010
We don’t usually give much thought to Numeric data types beyond whether we want to work with integers or decimal numbers. And that is a shame! In this post I’ll look at how we can actually do arithmetic operations lazily, and in the process hopefully reveal a bit about haskell’s numeric classes.
module LazyArithmetic
where
We will be using Lennart Augustsson’s numbers library which can be installed from hackage with cabal-install:
$> cabal install numbers
import Data.Number.Natural
import Data.List(genericLength)
Consider two functions: the Prelude function sum and genericLength from the List library:
genericLength :: (Num i) => [b] -> i
sum :: (Num a) => [a] -> a
…two simple functions that have the potential to be very expensive, depending on the length of the list and the values of the elements.
Read the rest of this article »
23/02/2010
I’ve been making notes when I have time, on the “17 x 17 challenge” posted a couple months back by Bill Gasarch. I’ve been sketching out algorithms for the problem and wanted to quickly produce some optimal rectangle free subsets to check my work and look at. So the code below answers the following question:
Imagine an n x n grid. You can color cells of the grid such that no rectangle overlayed on the grid will have all four corners colored. Find a grid with the maximum possible colored cells.
Read the rest of this article »
