Satoshi Nakamura has published a Japanese translation of the Typeclassopedia. I don’t read any Japanese, but it sure looks cool, and I hope this will be a great resource for Japanese learners of Haskell. A big thank you to Satoshi for his hard work; the Typeclassopedia is certainly not short!
New Haskell diagrams library
April 30, 2008For the past week or so I’ve been working on an embedded domain-specific language for rendering simple diagrams with Haskell, and I’m excited to actually release version 0.1 today! You can now find it on Hackage. Version 0.1 is still fairly primitive, and there are a bunch more planned features, but you can already use it to create some pretty pictures. Here are a few examples.
We’ll start with a basic ‘hello world’ type diagram: a two-by-five rectangle, no frills:
module Main where import Graphics.Rendering.Diagrams main = renderToPng "hello.png" 100 100 (rect 2 5)
OK, not too exciting, but at least it was easy. Here’s another silly example that shows off a few more available features:
module Main where
import Graphics.Rendering.Diagrams
shapes :: Diagram
shapes = hcat [ fc blue $ circle 10
, (fc goldenrod . lc green . lw 3 $ poly 5 10)
## (fc red . rotate (1/10) $ rect 4 4)
, fc grey . lw 0 . scaleY 3 $ circle 5
]
main = renderToPng "shapes.png" 200 200 shapes
Hopefully, this example is fairly self-explanatory. We can alter the appearance of diagrams by applying functions to them like fc (fill color), lc (line color), lw (line width), rotate, and scaleY. We can superimpose two diagrams with ##. And we can lay out a list of diagrams horizontally with hcat. There are many other combinators along similar lines, with various options for distributing and aligning subdiagrams.
Now for a couple cooler examples. How about a Sierpinski triangle?
module Main where
import Graphics.Rendering.Diagrams
import Graphics.Rendering.Diagrams.Types
import qualified Graphics.Rendering.Cairo as C
import Graphics.Rendering.Diagrams.Shapes (draw)
data EqTri = EqTri deriving Show
instance ShapeClass EqTri where
shapeSize _ = (2, sqrt 3)
renderShape _ = do
c $ C.moveTo 1 s
c $ C.lineTo 0 (-s)
c $ C.lineTo (-1) s
c $ C.closePath
draw
where s = sqrt 3 / 2
sierpinski :: Int -> Diagram
sierpinski 0 = fc black $ lw 0 $
shape EqTri
sierpinski n = vcatA hcenter [ s
, s <> s]
where s = sierpinski (n-1)
main = renderToPng "sierpinski.png" 300 300 (sierpinski 6)
This example illustrates a couple key points. One is that the library is easy to extend with new shapes. The built-in poly function is too general to provide a nice equilateral triangle for use in making a sierpinski triangle (its bounding box is too large, which would lead to ugly spaces in the diagram), so we can define our own shape just by making an instance of ShapeClass, and using the Cairo library to draw a path defining the shape. This is probably not the best way to accomplish this particular task — future versions of the diagrams library will include easier ways — but it’s a nice example of how easy it is to extend the basic library functionality.
The other key point is how much power we get for free from the fact that this is an embedded DSL. We can use the full power of Haskell to define a recursive function for computing sierpinski triangle diagrams.
For a final example, here are some nice Ford circles:
module Main where
import Graphics.Rendering.Diagrams
import Data.Ratio
import System.Random
(<+>) :: Rational -> Rational -> Rational
r1 <+> r2 = (numerator r1 + numerator r2) % (denominator r1 + denominator r2)
farey :: Integer -> [Rational]
farey 0 = [0%1, 1%1]
farey n = insertMediants (farey (n-1))
insertMediants :: [Rational] -> [Rational]
insertMediants [] = []
insertMediants [x] = [x]
insertMediants (x:y:zs) = x : (x <+> y) : insertMediants (y:zs)
fordCircles :: Integer -> [Diagram]
fordCircles n = map toCircle (filter ((<= n) . denominator) $ farey n)
toCircle r = translateX r' $
circle (1 / (2 * d'^2))
where r' = fromRational r
d' = fromIntegral (denominator r)
dia :: [Color] -> Diagram
dia colors = view (0,-1/2) (1,0) $
unionA hcenter bottom $
zipWith fc colors (fordCircles 20)
randomColors :: [Double] -> [Color]
randomColors (r:g:b:ds) = rgb r g b : randomColors ds
main :: IO ()
main = do
g <- newStdGen
let rs = randoms g
renderToPng "ford.png" 400 205 (dia $ randomColors rs)
Plans for future versions of the library include:
- text objects
- settable backgrounds and better support for transparency
- support for line join style and dashing
- more primitive shapes: special triangles, ellipses, bezier curves, lines, arrows…
- more layouts: grid, tree, circle…
- constraint-based placement of objects, e.g. to connect diagrams with arrows
- more output modes: ps, svg, pdf
- and more!
If this looks interesting to you, I hope you’ll download the library and play around with it! (Note that it does require the Cairo bindings, which are packaged as part of gtk2hs, which is unfortunately not yet Cabalized.) I would be happy to receive any and all feedback, including feature suggestions, bug reports, and pretty pictures. If you’re interested in contributing code, the darcs repository can be found at http://code.haskell.org/diagrams/.
Enjoy!
FringeDC talk
March 27, 2008My FringeDC talk has now been uploaded to Google video! A huge thanks to Conrad Barski, who took the effort to actually record the video and then wrangle it into digital form. Without further ado:
The slides are here if you’d like to follow along.
In general I’m pretty happy with how it turned out. This is one of the first “real” talks I’ve given, though (although I did teach high school for two years), so I definitely learned a lot and have some good ideas for improving the next talk I give.
Comments or questions welcome!
ETA: the Java bug mentioned in the video was just fixed today! w00t!
Gobby, Haskell, and patch theory
February 4, 2008On a couple of occasions over the past few days, I’ve had the pleasure of editing code with other #haskellers, using the collaborative text editor gobby. It was quite a lot of fun, and (somewhat surprisingly, to me at least) rather effective. It could stand a good chance of becoming one of my preferred methods for collaborative programming.
Except.
Except that gobby doesn’t support undo! It doesn’t even have a way to go “back in time” to a previous version of a document (unless you have it saved locally, of course). This is, quite plainly, a huge show-stopper, and I don’t say that just in theory: I ran into this issue head-on after only a few hours of use. I wanted to delete a bunch of double quotes, so did a search-and-replace. It was taking too long to click “replace” for each double quote character, so I clicked “replace all”, thinking it would only replace double quotes from the current location to the end of the file. Well, as you can probably guess, it deleted all the double quotes everywhere in the file. Oops. Ten minutes of tracking down missing quotes ensued, and I don’t even want to imagine what it would have been like without the help of the typechecker.
This was ten minutes of wasted time. I should have been able to just hit “undo” and get on with life.
So, why doesn’t gobby have undo? I looked at their bug tracker, and sure enough, this has been a requested feature since 2005. But it’s never been done, since undo in a collaborative-editing context is a hard problem. Apparently someone is sorta-kinda working on an implementation, that works in some cases…
A hard problem, eh? What hard problems need is good theory. Well, gee goshums! If only there was some sort of theory of concurrent editing…
So, the upshot of all of this is that I am seriously considering writing a gobby clone in Haskell with some sweet, sweet patch theory goodness. (Other killer features under possible consideration: hpaste and darcs integration, a Yi frontend, integrated compilation/error annotations, chat support that doesn’t suck…) I do have a lot more thoughts on the particulars of how this might work, but I won’t write more about the specifics here since that’s not really the point of this post.
The point is that although I said “seriously considering”, in actuality I’m not sure exactly how serious I really am. This would be a pretty big project, and I certainly couldn’t get anywhere close to pulling it off myself. I’m not even sure that I understand all of what it would require; I’d be particularly clueless about the networking and UI stuff. I just think that it would be pretty sweet, and a great application of Haskell’s strengths. Mostly at this point I’m looking for feedback. What do you think? Is this an awesome idea? Is it a stupid idea? Most importantly, would you be interested in working on it?
A word to the wise
December 19, 2007If you only implement the less than operator in a custom Ord instance (on the theory that “I know I only need to implement one operation to get defaults for the others, and less than makes sense, since you can get anything using less than and equals”), the compiler gives zero warnings (even with -Wall) and trying to compare anything will send your program into nasty infinite recursion. It turns out that you have to implement less than or equal to (or the ‘compare’ function), not less than. Says so in the docs for Ord, of course, but… sigh.
In related news, the new ghci debugger is quite helpful. =)
And in unrelated news, I’m finally done with grad school and fellowship applications!!
a plea for accountability
October 29, 2007I really need to be finishing up this NSF graduate fellowship application. Chatting in #haskell is not helping. If you see me in #haskell anytime in the next few days, please have lambdabot slap me with a trout.
Higher-dimensional enumeration
October 1, 2007The other day in the #haskell IRC channel, some of us were playing around with generalizing Haskell list enumeration syntax:
Prelude> [1..5] [1,2,3,4,5]
First, we defined the (…) operator to perform enumeration, so it can be partially applied. (Unfortunately, we can’t define a (..) operator for this purpose, since it’s reserved syntax.)
Prelude> let x ... y = [x..y] Prelude> map (...4) [1,3,7] [[1,2,3,4],[3,4],[]]
So, how to generalize? Someone typed this:
Prelude> let x .... y = map (x...) (x...y) Prelude> 1 .... 3 [[1],[1,2],[1,2,3]]
Interesting! And what about five dots? Unfortunately, this doesn’t work:
Prelude> let x ..... y = map (x...) (x....y)
<interactive>:1:28:
Occurs check: cannot construct the infinite type: a = [a]
Expected type: [a]
Inferred type: [[a]]
In the second argument of `map', namely `(x .... y)'
In the expression: map ((x ...)) (x .... y)
Of course, the problem is that (x …. y) has type [[a]], so we can’t just use map (x…), we have to map twice in order to reach the proper depth:
Prelude> let x ..... y = map (map (x...)) (x .... y) Prelude> 1 ..... 3 [[[1]],[[1],[1,2]],[[1],[1,2],[1,2,3]]]
We could keep going, although it gets increasingly difficult to tell apart the number of dots.
x ...... y = (map . map . map) (x...) (x ..... y) x ....... y = (map . map . map . map) (x...) (x ...... y) ...
Let’s take a step back and think about what is going on here. First, (1…3) just means we are counting from 1 up to 3: [1,2,3]. At the next level, (1 .... 3) means we are counting up to (1 … 3) = [1,2,3]: first [1], then [1,2], then [1,2,3]. So (1 .... 3) = [[1],[1,2],[1,2,3]]. We can illustrate it thus:
1
1 2
1 2 3
Then (1 ..... 3) means we’re counting up to THAT: first [[1]], then [[1],[1,2]], then [[1],[1,2],[1,2,3]]. Any guesses on a nice visualization? That’s right, it’s a tetrahedron!
In general, continuing this procedure gives us higher- and higher-dimensional simplices. From this perspective, an expression like [1..5] is really giving us discrete points on a 1-simplex, i.e. a line. Now, the big question: can we generalize the operators (…), (….), (…..), etc. into a single higher-order function which can compute this “simplicial enumeration of order n”, for any given n > 0?
At first blush this doesn’t seem possible. For one thing, there’s a problem with assigning a type to this hypothetical higher-order enumeration function: each of the enumeration operators we made returns a different type! (…) returns [a], (....) returns [[a]], and so on. So we’d have to unify the infinite family of types [a], [[a]], [[[a]]], etc. into a single type. Secondly, there’s the problem that each specific enumeration operator uses a different number of calls to map in its implementation. We could try to copy and paste some code from Oleg involving overlapping instances and crazy typeclasses… but (in this instance) there’s a better way.
What we’d like to do is create a type which encompasses [a], [[a]], [[[a]]], and so on. A good first try might be:
data DeepList a = List [a] | Deep [DeepList a]
which says that a DeepList of ‘a’ is either a list of ‘a’, or a list of DeepLists of ‘a’. Sounds good, right? Unfortunately, there is a subtle problem with this definition: lists in different parts of a DeepList value may have different depths. For example, the following is a perfectly legitimate value of type DeepList Int:
Deep [List [1,2,3], Deep [List [1,6], List [4]]]
If we remove the Deep and List constructors, however, this corresponds to the ill-typed list value [[1,2,3], [[1,6], [4]]]. Since we only want values corresponding to nested list types, this ability to have different-depth lists in different parts of the tree won’t do. How can we force different branches to all have the same depth?
To the rescue come non-regular types — that is, recursive parameterized types where the type parameters on the right side are not the same as on the left. In particular, we can use a Bush type defined as follows:
data Bush a = Leaves [a] | Trunk (Bush [a])
This definition is very similar to that of DeepList, but the key difference is that a Bush may consist of a Bush of lists of ‘a’, rather than a list of Bushes of ‘a’. Every occurrence of the Trunk constructor adds one more nested layer to the type parameter, until finally a Leaves constructor is reached, followed by a suitably-nested list. For example, here are some values of type (Bush Int):
Leaves [1,2,3] Trunk (Leaves [[1,2], [6,7]]) Trunk (Trunk (Leaves [[[5],[6,8,9],[]],[[6,19],[20]]]))
You can check that something like Trunk (Leaves [1,2,3]) gives a type error.
So, our higher-order enumeration function can return a Bush. But how will we deal with the (map . map …)’s? Actually, this is easier than it looks: all we need to do is make Bush a Functor, since that’s really what’s going on: we just want to be able to map (x…) over the result of the enumeration one dimension lower, whatever that might happen to mean. So, here we go:
import Data.List data Bush a = Trunk (Bush [a]) | Leaves [a] instance (Show a) => Show (Bush a) where -- show Bush values without the constructors show (Leaves l) = show l show (Trunk b) = show b instance Functor Bush where fmap f (Trunk b) = Trunk $ fmap (map f) b -- add another map fmap f (Leaves l) = Leaves $ map f l flatten :: Bush a -> [a] -- flatten a Bush into a single list flatten (Leaves l) = l flatten (Trunk b) = concat $ flatten b x ... y = [x..y]
And now our higher-order enumeration function (which we’ll call simplex, for reasons which are hopefully clear) is easy to write:
simplex :: (Enum t, Integral a) => a -> t -> t -> Bush t simplex n _ _ | n < 1 = Leaves [] simplex 1 x y = Leaves (x...y) simplex n x y = Trunk $ fmap (x...) (simplex (n-1) x y)
Let’s try it out:
*Main> simplex 1 1 3 [1,2,3] *Main> simplex 2 1 3 [[1],[1,2],[1,2,3]] *Main> simplex 3 1 3 [[[1]],[[1],[1,2]],[[1],[1,2],[1,2,3]]]
It works! Finally, I’ll leave the explanation of the following QuickCheck properties as an exercise for the reader:
simplex' :: (Integral a, Integral t) => a -> t -> Bush t
simplex' n x = simplex n 1 x
fac :: (Integral t) => t -> t
fac n = product [1..n]
binom :: Integer -> Integer -> Integer
binom n k | n < k = 0
| k < 0 = 0
| otherwise = (fac n) `div` (fac k * fac (n-k))
prop_simplex k n = (k > 0) ==>
(genericLength . flatten . simplex' k $ n) == binom (n + k - 1) k
prop_simplex_components k n = (k > 0) ==>
(map genericLength . group . sort . flatten . simplex' k $ n) == map (flip binom (k-1)) [k+n-2,k+n-3..(k-1)]
Posted by Brent
Posted by Brent
Posted by Brent 


