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.
Tags: Functional Programming, Haskell
Posted in Programming | No Comments »
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.
Tags: Functional Programming, Haskell, Math
Posted in Programming | 2 Comments »
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.
Tags: Functional Programming, Haskell, Tilting at Windmills
Posted in Eccentric, Programming | 2 Comments »
