Mathematics, Haskell, and little bit of Linux
Here I am trying to crank out something for the ICFP Programming Contest and I have a huge host of OpenGL problems with my new laptop. This stuff should come in handy for all those people out there with a Lenovo R61 running Gentoo Linux with Mesa 6.5… all two of them.
Anyhow, no math or programming in this post, I'm afraid, just good old-fashioned system debugging. (more…)
Filed under: Linux by Kenn
No Comments »
I recently gave a little demonstration entitled "What is Defunctionalization?" for UCSC TWIGS (the acronym, stolen from a similar seminar in the the U. Mass. math department, stands for The "What Is … ?" Graduate Seminar). The inspiration for this talk was just to present what I'd learned after Conor McBride's brilliant presentation at POPL'08 drove me to put the words "Olivier Danvy defunctionalize continuation" into Google.
I coded the simplest examples from
in literate Haskell for the audience, and also showed off QuickCheck a little to make sure the translation was correct (finding one error, if I recall).
This blog post is a merging of my talk outline and new stuff that came up live. Try loading it up in GHCi or Haskell-mode and running the examples and QuickCheck properties. (more…)
Filed under: Haskell, Mathematics, Reading by Kenn
No Comments »
The call is out for submissions to the next issue of The Monad.Reader! To get an idea of the content (and because Don Stewart told us all to read every past issue) I cracked open Issue 10, which has a nice tutorial by B Pope on the GHCi debugger.
But having just finished a post using open recursion, it immediately cried out to me that open-recursive functions already have some debugging hooks for tracing/breakpoints/etc. Naturally, some complications arose, and I got to try out some other cool ideas from the literature.
To combine the State in which I store the memoization table with the IO I use for debugging, I use
And then to reduce the plumbing overhead I use
This post is, as usual, a literate Haskell file so load it up in GHCi or Emacs Haskell-mode and see what happens. (more…)
Filed under: Haskell, Mathematics by Kenn
2 Comments »
As an exercise, since my reading group was discussing model checking this week, I implemented the classic model checker for CTL specifications from the 1986 paper
The "efficient algorithm" presented in the paper is, upon reflection, merely a memoized traversal of the state machine, so I combined it with a modified version of
which actually eliminated an auxilliary function from the algorithm, yielding an efficiently-executable 20-line Haskell specification of the meaning of CTL (which is probably clearer than my English prose explanation, and certainly more fun to play with).
This post is, as usual, literate Haskell. Load it up in GHCi, Haskell-mode, or compile it with ghc --make and try it out. Maybe you can convince my state space exploration not to terminate 
(more…)
Filed under: Haskell, Mathematics, Reading by Kenn
1 Comment »
I recently got a tablet to input handwritten math for slideshow presentations, but instead of using a note-taking program (Jarnal, Xournal, Gournal) I decided that I wanted the full power of image manipulation of a program like Gimp or Inkscape. Neither of these, though, has the level of support for multi-page documents that you find in note-taking software. But Inkscape uses SVG as its native file format, so I wrote this Haskell script to transform the layers of an Inkscape SVG file into the slides of a PDF presentation. I use the HaXml library to manipulate the SVG, the Inkscape command-line interface to convert each page to PDF, and pdftk to glue the whole thing back together.
As usual, this post is a literate Haskell file, so you can try it out by saving it to Inkscape.lhs, compiling with ghc --make Inkscape, grabbing the source file for the images above, and running ./Inkscape < demo.svg. The output will appear in Slides.pdf (and your directory will be polluted with temp files, so be aware).
(more…)
Filed under: Haskell, LaTeX, Linux, Mathematics by Kenn
4 Comments »
I'm reading the very fun Measure, Topology, and Fractal Geometry by GA Edgar, and thought I'd hack up some of the examples in Haskell. So this post implements cursor graphics in OpenGL in (I think) DSEL style, demonstrating the StateT and Writer monad gadgets from the
standard library and a cool "novel representation of lists" due to R Hughes. On the fractal side, the examples will hopefully convince you that fractals are not just cute pictures, but extremely important illustrations that the real numbers are weird.
As usual, you can save this post to Fractals.lhs and compile it with ghc --make Fractals (more…)
Filed under: Haskell, Mathematics by Kenn
6 Comments »
This is a question posed in my randomized algorithms class. If you are routing in a network whose connectivity looks "more or less" like a convex figure, what does the congestion look like? A quick way to make an educated guess is to draw a bunch of random line segments in such a convex shape and see where the colors get the brightest:
This post is literate Haskell that will output that image, so save it to something like Congestion.lhs and run ghc --make Congestion.lhs. (more…)
Filed under: Haskell, Mathematics by Kenn
No Comments »
I read a lot, perhaps to the detriment of my eventual graduation plans. Recently, I've been enjoying books of "recreational mathematics." This is a combined review of all such books I've read recently. (more…)
Filed under: Mathematics, Reading by Kenn
No Comments »
The Knuth-Bendix completion procedure (when it succeeds) transforms a
collection of equations into a confluent, terminating rewrite
system. Sometimes the procedure fails, and sometimes does not
terminate, but The Handbook of Computational Group Theory by D Holt
remarked that even in this case it generates an infinite set of
rewrite rules that are complete, and An Introduction to Knuth-Bendix
Completion by AJJ Dick also mentions that in the nonterminating case
one can derive a semi-decision procedure for equality checking. I naturally had to hack
this up in Haskell, to create an infinite set of rewrite rules as a
lazy list. This illustrates the very real software engineering
benefit of decoupling creation and consumption of infinite data. As
usual, this post is a valid literate Haskell file, so save it so
something like KnuthBendix.lhs and compile with ghc --make
KnuthBendix or load it up with ghci KnuthBendix.lhs
(more…)
Filed under: Haskell, Mathematics by Kenn
No Comments »
Any isometry of the plane has a unique normal form as the composition of a translation, rotation and reflection. This note computes this normal form and tests the implementation using the QuickCheck automated testing tool for Haskell. To generate random test data, I use another characterization of isometries as products of up to three reflections. This post is a valid literate Haskell file, so save it to something like Isometries.lhs and run ghc --make Isometries. Then check it with quickCheck +names Isometries.lhs.
(more…)
Filed under: Haskell, Mathematics by Kenn
No Comments »
