I hope you never need this. But if you do, you can get it from me on github here.
It’s a little craptacular at the moment, but it works. I will maintain and enhance it depending on demand.
Posts Tagged ‘Functional Programming’
Dec
01
2009
Functional vs. Imperative Red-Black Tree Insertion
MarkCC posted an insert algorithm for red-black trees in Haskell yesterday. Now I don't want to come across as anything resembling an expert here but I felt honor-bound to raise the point that there is a far simpler algorithm described in Chris Okasaki's 1999 paper Red-Black Trees in a Functional Setting.
It goes basically like this:
data Color = Red | Black deriving (Show, Eq)
data RedBlackTree a =
Empty | Node Color (RedBlackTree a) a (RedBlackTree a)
deriving (Show, Eq)
insert :: Ord a => a -> RedBlackTree a -> RedBlackTree a
insert elem t = makeBlack (insert' elem t)
where makeBlack (Node _ a y b) = Node Black a y b
insert' elem Empty = Node Red Empty elem Empty
insert' elem s@(Node color a y b)
| elem < y = balance color (insert' elem a) y b
| elem > y = balance color a y (insert' elem b)
| otherwise = s
balance Black (Node Red (Node Red a x b) y c) z d =
Node Red (Node Black a x b) y (Node Black c z d)
balance Black (Node Red a x (Node Red b y c)) z d =
Node Red (Node Black a x b) y (Node Black c z d)
balance Black a x (Node Red (Node Red b y c) z d) =
Node Red (Node Black a x b) y (Node Black c z d)
balance Black a x (Node Red b y (Node Red c z d)) =
Node Red (Node Black a x b) y (Node Black c z d)
balance color a x b = Node color a x b
I will not try to replicate the contents of the paper here, it's very short so I encourage you to go read it. The gist of it is as follows.
The reason the Haskell algorithm is simpler is because in functional languages, destructive updates to the tree are impossible. This renders the (relatively complex) optimizations that are commonplace in imperative implementations pointless.
The functional implementation has other advantages, namely: beauty, simplicity, persistence, and all of the other things we choose when we give up pointer manipulation.
Dec
25
2007
Haskell Mandelbrot Set
Some people sing carols every XXX-mas, I get bored and write the Mandelbrot Set program in whatever my favorite language happens to be that year. I thought the brevity of the output this year (Haskell) was kinda neat.
import Graphics.UI.GLUT
import Control.Monad
import Data.Int
import Data.Complex
iterations = 400
x // y = fromIntegral x / fromIntegral y
-- Divides [a] into [[a], [a], ...] with each sublist of length n,
-- except the last sublist which has length <= n.
chunkify n [] = []
chunkify n xs = let (xs', rest) = splitAt n xs
in xs' : chunkify n rest
-- Converts a coordinate in screen space to a vertex.
pix2vert (Size w h) (x, y) = Vertex2 ((3 // w * fromIntegral x) - 2.0)
((2 // h * fromIntegral y) - 1.0)
-- List of all of the vertices that represent screen pixels.
vertices :: IO [Vertex2 GLfloat]
vertices = get windowSize >>= \(Size w h) ->
return $ [pix2vert (Size w h) (x, y) | x <- [0..w-1], y <- [0..h-1]]
-- Gets the color for a number of iterations.
color3 r g b = Color3 r g b
getcolor :: Int -> Color3 Float
getcolor iter | iter == iterations = color3 0 0 0
| otherwise = color3 (amt*0.5) amt (amt*0.5)
where amt = iter // iterations
-- Returns the number of iterations <= the maximum iterations of the
-- Mandelbrot set at the given vertex.
mandel (Vertex2 r i) = length . takeWhile (\z -> magnitude z <= 2) .
take iterations $ iterate (\z -> z^2 + (r :+ i)) 0
-- plots one point.
drawVert v = do color . getcolor $ mandel v
vertex v
-- draws all the vertices in slices (to update the display while drawing).
display' chunks = do mapM_ (\vs -> do renderPrimitive Points $ mapM_ drawVert vs
flush) chunks
displayCallback $= display
-- draws the whole fractal
display = do clear [ ColorBuffer ]
displayCallback $= (vertices >>= display' . chunkify 256)
get currentWindow >>= postRedisplay
main = do
getArgsAndInitialize
initialDisplayMode $= [ SingleBuffered, RGBMode ]
initialWindowSize $= Size 1200 1024
initialWindowPosition $= Position 100 100
createWindow "Mandelbrot"
clearColor $= Color4 0 0 0 0
matrixMode $= Projection
loadIdentity
ortho (-2) 1 (-1) 1 (-1) 1
displayCallback $= display
mainLoop
Screenshot:
Dan McKinley does not claim to be a Haskell expert and definitely doesn't claim to be an expert about Haskell graphics rendering.
Mar
31
2007
New MacBook Pro, Jealous?
I suppose I finally had enough of the carpal tunnel caused by typing '\' to delimit directories (yes, powershell helps a little, but not enough).
Or, I decided I knew enough about Windows for now and needed to branch out.
Or maybe I was just in a rut.
Well, I'm happy about whatever it was that caused me to make my latest impulse purchase.
I've had it less than a week. Great stuff so far:
- Having a unix-based OS to develop on is fantastic. The compilers for the languages I prefer to use in my spare time these days seem to work much better, presumably because many of the people who work on those languages also use Macs. GHC, for one, isn't terribly well supported on Windows.
- It only took me a second to figure out how to swap caps lock and control for emacs.
- It's great to have a terminal that doesn't suck. (Though, it'd be hard to do worse than cmd.exe. I'm aware of several valiant attempts at replacing it, but none compare.)
- GarageBand - watch for my band to make a splash on the indie hate folk scene sometime in 2007. That's a genre I just invented, by the way.
I guess that's mostly developer stuff, which is odd since Apple's marketing actively makes fun of programmers.
I don't see myself ceasing Windows development anytime in the next decade, though, so if you're only here for .NET debugging stuff I wouldn't head for the hills just yet.
Feb
19
2007
The reports of my madness may not be so exaggerated
Sometimes I think my quest to get my functional programming skills up to snuff is turning me into a raving lunatic. I keep writing code that inflicts physical pain when kept to myself. Here's a fresh cut and paste out of my emacs:
applyAll [] = id applyAll fs = foldl1 (.) fs
After writing that, I immediately opened up all of my instant messenger programs in search of an imperative programmer to accost. "Don't you see? Don't you see how beautiful this is?" I would say. They almost never see.
Sep
03
2006
Wheels I Have Wasted Time Re-inventing
This site has been silent for quite a while. My lame excuse for this is as follows.
Sometime around the beginning of the summer I started trying to learn functional programming in earnest. I had some exposure to this in school (ML, if I remember correctly), but not nearly enough, as it turns out. C#'s anonymous methods provided the "eureka" moment that made me want to revisit the topic. I had also been asked to contribute to The Hub, but I had felt like I was lost in the world of F# and that fizzled out altogether (maybe now I might have a few things to say).
So that's my story–I have been exploring strange new(-ish) topics and I've found that I haven't had anything insightful to contribute to the world.
Recently I've been trying to complete a few large projects in Common Lisp. I'm pleasantly surprised to find myself saying that most or all of the highfalutin crap that is spouted about Lisp is true. As to why it isn't the most-used language in the world right now, I am too much of a novice to speculate. But purely from a language standpoint it is certainly making all of the others feel, well, tedious.
Lisp seems to supersede every single neat trick I have ever come up with programming professionally. It either contains them outright, or it makes them trivial through macros or completely unnecessary for some other reason. Let me give you one simple example.
Writing applications in C#, I've occasionally had a singleton or some kind of global object that I wanted to be redefined within a certain call stack. Let's say I have this API:
class Foo
{
public static Foo Default { get; }
}
And I want this to be redefined for a little while while I call some method called Bar(). Impersonation of users is one concrete example of where this is useful.
My neat-trick solution to this problem is to make the implementation of Default use thread local storage (and maybe fall back on a static instance too), then create a "scope" class that allows me to write code that looks like this:
// Original value of SomeOtherFoo out here
using(FooScope s = new FooScope(someOtherFoo))
{
// In here, Foo.Default gives someOtherFoo
Bar();
}
// Original value of SomeOtherFoo out here
(I am skipping over a lot of irritating details here and let me be clear, I don't claim to have invented this. I just mean that I burned a lot of hours arriving at it basically independently of the ten million other programmers who probably recognized the same need and did the same thing. It is purely my own ignorance and stupidity that made "re-discovering" it necessary.)
Anyway, I thought that was clever at the time. But with dynamic scope (as opposed to global scope, which is what static fields have in C#) Lisp has this as part of the language. Writing this:
(let ((*default-foo* some-other-foo)) (bar))
Is basically the same thing with no effort. The Lisp syntax has the added advantage of working with objects other than the ones I author myself.
This reminds me of the first time I was exposed to .NET events. I realized that I had implemented the same god-damned thing in other languages a handful of times (albeit as a less-seasoned programmer) and it never worked as beautifully or as simply.
Naturally, CLOS seems to have some features that I now realize I have been mimicking imperfectly with events. It also has features that will probably replace events in many of the problems where I have applied them. That is an altogether different story.
