It’s a sunny day in your advanced symbolic programming class. Your teacher has just started going over monads—in Scheme, though—and you sit in the back of the classroom snarking about little tidbits of knowledge you know from Haskell. Suddenly, the teacher says (quite earnestly too), “Edward here seems to know a lot about monads. Why don’t we have him come up and teach them to the class?” Suddenly, you’re up expounding types to people who have never used Haskell before and failing utterly to explain to people how the continuation monad works. Only after several iterations do you manage to partially rewrite the presentation in a form that doesn’t assume fluency in Haskell. You’ve fallen into the expert trap.
Read more...
> {-# LANGUAGE GeneralizedNewtypeDeriving #-}
> import Control.Comonad
> import Data.List
That scary Control.Comonad import from category-extras is going to be the subject of today’s post. We’re going to look at one possible implementation of comonads for non-empty lists that model causal time-invariant systems, systems whose outputs depend only on inputs that are in the past. We will see that computation in these systems follows a comonadic structure and that one instance of this structure strongly enforces causality and weakly enforces time-invariance.
Read more...
I present here a few pieces of folklore, well known to those practiced in Haskell, that I’ve found to be really useful techniques when analyzing code whose types don’t seem to make any sense. We’ll build practical techniques for reasoning about types, to be able to derive the type of fmap fmap fmap by ourselves. Note that you could just ask GHCI what the type is, but that would spoil the fun! (More seriously, working out the example by hand, just like a good problem set, helps develop intuition for what might be happening.)
Read more...
> import Data.List
> import Control.Monad
The following question appeared as part of a numbers-based puzzle in the 2010 MIT Mystery Hunt:
His final level on Wizard of Wor was equal to the smallest number that can be written as the sum of 4 non-zero squares in exactly 9 ways
I’d like to explore constraint search in Haskell to solve this problem. The hope is to find a (search) program that directly reflects the problem as posed, and also gives us an answer!
Read more...
Editorial. Today we interrupt our regularly scheduled programming to bring you a guest post by Oleg Kiselyov, reinterpreting our previous post about nested loops and continuations with exceptions.
Hello!
I noticed your recent article about nested loops and continuations. I should have commented on it using the provided form, but I was not sure how formatting would come out. The comment includes a lot of code. Please feel free to post the code in whole or in part, or do anything else with it.
Read more...
The bread and butter of an imperative programmer is the loop. Coming from a C/assembly perspective, a loop is simply a structured goto which jumps back to a set location if some condition is not met. Frequently, this loop ranges over the elements of some list data structure. In C, you might be doing pointer arithmetic over the elements of an array or following pointers on a linked list until you get NULL; in Python and other higher-level languages you get the for x in xs construct which neatly abstracts this functionality. Inside of a loop, you also have access to the flow control operators break and continue, which are also highly structured gotos. An even more compact form of loops and nested loops are list comprehensions, which don’t permit those flow operators.
Read more...
Typeclasses matter. In fact, I’ll go as far to say that they have the capacity to replace what is traditional object-oriented programming. To understand why, however, we have to review the traditionally recognized benefits of object-oriented programming:
- Organization. For C-inspired languages that don’t have a module system, this is so incredibly important; without a discipline for organizing code finding the location of any given function is difficult unless you are intimately familiar with the problem domain. With object-oriented programming, all of these aspects are obvious: classes map into obvious filenames, methods go in obvious places, and overall organization is a function of how well the object model is designed, not how well thought out the include files were.
- Encapsulation. Objects were the first widely utilized method of hiding data and code from clients. Declare something
private or protected, and you have compile-time guarantees that your clients won’t have their grubby fingers all over your innards. Used properly, modularity follows. - Polymorphism. The ability to change behavior based on data is a powerful idea dating back to the days of
(void *), which can lead to incomprehensible code flow but more often is a more elegant and concise way of writing complicated interactions than a giant switch statement. These benefits compound in situations that multiple dispatch is appropriate, and interfaces can lead to compile-time assurances that a particular class does what it says it does. - Inheritance. While a problematic facet of object-oriented programming (especially when manifest as multiple inheritance), inheritance is still an extremely powerful mechanism of code reuse in object-oriented designs. Subclasses get a default implementation for methods, as well as the ability to break through a level of encapsulation and use
protected methods.
Typeclasses directly fulfill some of these requirements, while others are achieved due to Haskell’s strict types and module system.
Read more...
Language selection is a contentious thing, and often a compromise between “pick the right language for the job” and “use as few languages as possible to increase mindshare.” Google, for example, limits the programming languages their employees are allowed to use; and I have come to associate picking whatever language you want for your own projects as irresponsible, having once been told, “Yeah… that project was written in X and no one besides the guy who wrote it knows X… probably not a good use of your time to work on it.” Of course, I’ve been quite culpable of this myself; I wrote the member dues tracking system for the Assassins’ Guild in Haskell, and unless a miracle happens I am kind of doubtful future maintainers will be able to deal with it.
Read more...
I’ve been busy at work over this winter break working on an article for The Monad Reader, entitled “Adventures in Three Monads.” The material will overlap the second part of my IAP talk Haskell Typeclasses that I will be delivering under the auspices of SIPB IAP.
The article itself is a literate Haskell file, and contains sample code I’ve cribbed from the various Haskell applications I’ve written over my year long flirtations with the language: included is code and explanation for the probabilistic Turing machine I built in order to brute-force a 6.004 assignment. (To the course staff: the code is incomplete enough that it’s not equivalent to publishing all of the solutions; intrepid readers will still have to write a search function themselves.)
Read more...