Planet Haskell
Paul Potts: Newegg Makes Good
Today is the shortest day of the year. It takes a lot of caffeine and St. John's Wort to keep me functioning this time of year. I think the barista at the local Caribou Coffee realized I needed a triple espresso and so I got a free upgrade. Either that or she was thinking "you know, we don't see you in here often enough... you're just not quite as addicted as we'd like you to be!"
This year really was a challenge -- illness, death, and mayhem all around us. Let's hope 2008 is better!
Bryan O'Sullivan: BLDGBLOG interviews Kim Stanley Robinson
Here is an absolute treat: a long, lively interview with Kim Stanley Robinson, conducted on one of my favourite blogs, BLDGBLOG.
At its best (the Three Californias trilogy, Antarctica), Robinson’s writing is at once haunting and beautifully evocative of a sense of place.
Mark Jason Dominus: Another trivial utility: accumulate
k1 v1 k1 v2 k2 v3 k1 v4 k2 v5 k3 v6 and writes it out in this format:
k1 v1 v2 v4 k2 v3 v5 k3 v6 I wanted it this time because I had a bunch of files that included some duplicates, and wanted to get rid of the duplicates. So:
md5sum * | accumulate | perl -lane 'unlink @F[2..$#F]' (Incidentally, people sometimes argue that Perl's .. operator should count backwards when the left operand exceeds the right one. These people are wrong. There is only one argument that needs to be made to refute this idea; maybe it is the only argument that can be made. And examples of it abound. The code above is one such example.)
I'm afraid of insulting you by showing the source code for accumulate, because of course it is so very trivial, and you could write it in five minutes, as I did. But who knows; maybe seeing the source has some value:
#!/usr/bin/perl use Getopt::Std; my %opt = (k => 1, v => 2); getopts('k:v:', \%opt) or usage(); for (qw(k v)) { $opt{$_} -= 1 if $opt{$_} > 0; } while (<>) { chomp; my @F = split; push @{$K{$F[$opt{k}]}}, $F[$opt{v}]; } for my $k (keys %K) { print "$k @{$K{$k}}\n"; } It's tempting to add a -F option to tell it that the input is not delimited by white space, or an option to change the output format, or blah blah blah, but I managed to restrain myself, mostly.
Several years ago I wrote a conference tutorial about the contents of my ~/bin directory. The clearest conclusion that transpired from my analysis was that the utilities I write have too many features that I don't use. The second-clearest was that I waste too much time writing custom argument-parsing code instead of using Getopt::Std. I've tried to learn from this. One thing I found later is that a good way to sublimate the urge to put in some feature is to put in the option to enable it, and to document it, but to leave the feature itself unimplemented. This might work for you too if you have the same problem.
I did put in -k and -v options to control which input columns are accumulated. These default to the first and second columns, naturally. Maybe this was a waste of time, since it occurs to me now that accumulate -k k -v v could be replaced by cut -fk,v | accumulate, if only cut didn't suck quite so badly. Of course one could use awk {print "$k $v" } | accumulate to escape cut's suckage. And some solution of this type obviates the need for accumulate's putative -F option also. Well, I digress.
The accumulate program itself reminds me of a much more ambitious project I worked on for a while between 1998 and 2001, as does the yucky line:
push @{$K{$F[$opt{k}]}}, $F[$opt{v}]; The ambitious project was tentatively named "twingler".
Beginning Perl programmers often have trouble with compound data structures because Perl's syntax for the nested structures is so horrendous. Suppose, for example, that you have a reference to a two-dimensional array $aref, and you want to produce a hash, such that each value in the array appears as a key in the hash, associated with a list of strings in the form "m,n" indicating where in the array that value appeared. Well, of course it is obviously nothing more than:
for my $a1 (0 .. $#$aref) { for my $a2 (0 .. $#{$aref->[$a1]}) { push @{$hash{$aref->[$a1][$a2]}}, "$a1,$a2"; } } Obviously. <sarcasm>Geez, a child could see that.</sarcasm>
The idea of twingler was that you would specify the transformation you wanted declaratively, and it would then write the appropriate Perl code to perform the transformation. The interesting part of this project is figuring out the language for specifying the transformation. It must be complex enough to be able to express most of the interesting transformations that people commonly want, but if it isn't at the same time much simpler than Perl itself, it isn't worth using. Nobody will see any point in learning a new declarative language for expressing Perl data transformations unless it is itself simpler to use than just writing the Perl would have been.
There are some hard problems here: What do people need? What subset of this can be expressed simply? How can we design a simple, limited language that people can use to express their needs? Can the language actually be compiled to Perl?
I had to face similar sorts of problems when I was writing linogram, but in the case of linogram I was more successful. I tinkered with twingler for some time and made several pages of (typed) notes but never came up with anything I was really happy with.
At one point I abandoned the idea of a declarative language, in favor of just having the program take a sample input and a corresponding sample output, and deduce the appropriate transformation from there. For example, you would put in:
[ [ A, B ], [ C, B ], [ D, E ] ] and { B => [A, C], E => [D], } and it would generate: for my $a1 (@$input) { my ($e1, $e2) = @$a1; push @{$output{$e2}}, $e1; } And then presumably you could eyeball this, and if what you really wanted was @{$a1}[0, -1] instead of @$a1 you could tinker it into the form you needed without too much extra trouble. This is much nicer from a user-experience point of view, but at the same time it seems more difficult to implement.
I had some ideas. One idea was to have it generate a bunch of expressions for mapping single elements from the input to the output, and then to try to unify those expressions. But as I said, I never did figure it out.
It's a shame, because it would have been pretty cool if I had gotten it to work.
The MIT CS grad students' handbook used to say something about how you always need to have several projects going on at once, because two-thirds of all research projects end in failure. The people you see who seem to have one success after another actually have three projects going on all the time, and you only see the successes. This is a nice example of that.
Mark Jason Dominus: Strangest Asian knockoff yet
Good plates have the name of the maker on the back. These were made by Villeroy & Boch. Some time later, we visited the Villeroy & Boch outlet in Woodbury, New York, and I found the pattern I wanted, "Pasadena". The cool circular plates from Striped Bass were only for sale to restaurants, but the standard ones were octagonal, which is also pretty cool. So I bought a set. (57% off list price! Whee!)
(The picture gets much bigger when you click it.)
They no longer make these plates. If you broke one, and wanted a replacement, you could buy one online for $43.99. Ouch! But there is another option, if you are not too fussy.
Many years after I bought my dishes, I was shopping in one of the big Asian grocery stores on Washington Avenue. They have a kitchenware aisle. I found this plate:
The real VB plate is made of porcelain. The Washington Avenue knockoff is made of plastic.
Of course I bought it. It is hilarious! And it only cost two dollars.
Mark Jason Dominus: Happy birthday Perl!
Brent Yorgey: Brent
On December 28 I’ll be hosting the Carnival of Mathematics over at my other blog, The Math Less Traveled. If you have any interesting math-related posts you’d like to submit (CS-related posts are fine—even encouraged—as long as there’s some sort of mathematical content!), that would be sweet.
Kenn Knowles: Infinite lazy Knuth-Bendix completion for monoids in Haskell
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…)
David R. MacIver: Type classes in Scala
I mentioned in a recent post that Scala could emulate Haskell type classes with its implicit defs and first class modules.
In actual fact, the situation is much happier than that. Implicit defs + first class modules give you significantly more than Haskell type classes (although with a tiny loss of type safety). At least, much more than Haskell 98. In particular, multiparameter type classes and associated types come for free. You also gain a number of other advantages, such as type class instantiation scopes lexically, so you can redefine type classes locally.
So, how does all this work? I'll begin with a general introduction to this style of programming with no real reference to Haskell, and then I'll tie this back in to encoding Haskell type classes at the end of it.
Here's a class that's familiar to anyone who has written non-trivial Java:
trait Comparator[T]{
def compare(x : T, y : T) : Int;
}
trait Comparable[T]{
def compareTo(t : T);
}
Now, let's define the following method:
def sort[T](array : Array[T])(implicit cmp : Comparator[T]) = stuff
So our sort method can either have a comparator passed to it explicitly or it will pull one from the surrounding environment. For example we could do:
object SortArgs{
implicit val alphabetical = new Comparator[String]{
def compare(x : String, y : String) = x.compareTo(y);
}
def main(args : Array[String]){
println(sort(args));
}
}
Will pick up the alphabetical instance.
It would be nice if we could also have defined the more general version:
object SortArgs{
implicit def naturalOrder[T : Comparable] = new Comparator[T]{
def compare(x : T, y : T) = x.compareTo(y);
}
def main(args : Array[String]){
println(sort(args));
}
}
But this doesn't seem to work. :-/ Hopefully this will be fixed - it seems like wrong behaviour. Matt Hellige came up with the following workaround, but it's not very nice:
object Sorting{
trait Comparator[T]{
def compare(x : T, y : T) : Int;
}
def sort[T](arr : Array[T])()(implicit cmp : () => Comparator[T]) = null;
implicit def naturalOrder[T : Comparable]() : Comparator[T] = null;
implicit def lexicographical[T]() (implicit cmp : () => Comparator[T]) :
Comparator[List[T]] = null;
def main(args : Array[String]){
sort(args);
sort(args.map(List(_)))
sort(args.map(List(_)).map(List(_)))
}
}
Moreover I haven't the faintest notion of why it works. :-)
However we can also chain implicit defs:
implicit def lexicographicalOrder[T] (implicit cmp : Comparator[T]) : Comparator[List[T]] = stuff;
So now the following code *does* work:
def main(args : Array[String]){
sort(args);
sort(args.map(List(_)))
sort(args.map(List(_)).map(List(_)))
}
}
An amazingly nice feature of this which some encodings of type classes miss is that you don't need an instance of a type to select on that type. Take for example the following:
object BinaryDemo{
import java.io._;
trait Binary[T]{
def put(t : T, stream : OutputStream);
def get(stream : InputStream) : T;
}
implicit val utf8 : Binary[String] = null;
implicit def binaryOption[T] (implicit bin : Binary[T]) : Binary[Option[T]] = null;
val myStream : InputStream = null;
def readText(implicit bin : Binary[Option[String]]) : Option[String] = bin.get(myStream);
readText match{
case None => println("I found nothing. :(");
case Some(x) => println("I found" + x);
}
}
Unfortunately this example betrays a weakness in our encoding. I can't just randomly call "get" like in Haskell's Data.Binary - because I need to invoke it on an instance of Binary[T] I need to ensure at the method level that one is available. There doesn't appear to be a good way of getting access to implicits from the enclosing scope directly.
However, here's a silly hack:
def fromScope[T] (implicit t : T) = t;
And we get:
fromScope[Binary[Option[String]].get(myStream) match{
case None => println("I found nothing. :(");
case Some(x) => println("I found" + x);
}
}
This works just as well with multiple type parameters. For example, if we wanted to port Java's AtomicArray classes without wrapping everything (although admittedly wrapping everything would be more idiomatic Scala) we could do the following:
object ArrayDemo{
import java.util.concurrent.atomic._;
trait AtomicArray[S, T]{
def get(s : S, i : Int) : T;
def set(s : S, i : Int, t : T);
def compareAndSet(s : S, i : Int, expected : T, update : T);
}
implicit val long = new AtomicArray[AtomicLongArray, Long]{
def get(s : AtomicLongArray, i : Int) = s.get(i);
def set(s : AtomicLongArray, i : Int, t : Long) = s.set(i, t);
def compareAndSet(s : AtomicLongArray, i : Int, expected : Long, update : Long) = s.compareAndSet(i, expected, update);
}
}
So, that's multi-parameter type classes. But one thing you'll notice about the above encoding is that it's a bloody nuisance to invoke - you need to know the type of the array class you're using, which is annoying. Far better would be if the trait took care of that. In Haskell terms this would be an associated type.
No problem.
object ArrayDemo{
import java.util.concurrent.atomic._;
trait AtomicArray[T]{
type S;
def get(s : S, i : Int) : T;
def set(s : S, i : Int, t : T);
def compareAndSet(s : S, i : Int, expected : T, update : T);
}
implicit val long = new AtomicArray[Long]{
type S = AtomicLongArray;
def get(s : AtomicLongArray, i : Int) = s.get(i);
def set(s : AtomicLongArray, i : Int, t : Long) = s.set(i, t);
def compareAndSet(s : AtomicLongArray, i : Int, expected : Long, update : Long) = s.compareAndSet(i, expected, update);
}
}
Scala's classes can have abstract types. So we just encode associated types as those.
So, to recap on our encoding:
class Foo a where
bar :: a
baz :: a -> a
becomes
trait Foo[A]{
def bar : A;
def baz(a : A) : A;
}
instance Foo Bar where
stuff
becomes
implicit Foo[Bar] bar = new Foo[A]{
stuff
}
instance (Foo a) => Foo [a]
becomes
implicit def[T] (implicit foo : Foo[A]) : Foo[List[A]];
And for invoking:
foo = bar
becomes
val yuck = fromScope[Foo[A]].bar
So it's a more verbose encoding, but not a terrible one. And it has some abstraction advantages too. For example:
sortBy :: (a -> a -> Ord) -> [a] -> [a]
sortBy = stuff;
sort :: (Ord a) => [a] -> [a]
becomes
def sort[A](xs : List[A])(implicit cmp : Comparator[A]);
Because our type classes are a form of implicit object passing, we can also use them with *explicit* object passing. Thus we can redefine behaviour much more nicely to behave equally well with an ordered type and explicitly provided comparison functions.
This has disadvantages too - you need to be more careful to ensure that you can't accidentally use two instances of the type class. This isn't a major burden though. The general solution is that when you have something which needs to maintain type class consistency between invocations you pass it an instance at construction type. Take for example Haskell's Data.Set. In Haskell getting a new Set (Set.empty) works for any type but almost all the functions for building sets have a constraint that the type belongs to Ord. In Scala you would require an Ord instance to be passed for Set construction but after that would not need one (analagous to Java's TreeSet providing a constructor that takes a Comparator).
One thing I haven't covered is type classes which abstract over type constructors rather than types. The reason I haven't covered them is that I've yet to peek into that corner of Scala's type system. However, I assume they work as Tony Morris has done some stuff with monads in Scala. Also, see this paper (which I've not read yet)
Mikael Johansson (Syzygy-): Calling all San Diego participants and Californians
I’ll be in San Diego for the AMS-MAA Joint Mathematics Meetings, January 5-11. I would be happy to meet up with cool people, blog readers, blog writers and what not - regardless of whether you actually will participate in the meeting or not. Drop me an email (contact data in the [about] page here) and we’ll coordinate something.
David R. MacIver: Random thoughts on OO
Suppose I told you there were two major areas of your code that were deeply intertwined. Each is intimately connected to the other and it was almost impossible to tell where one started and the other began, yet the two were really very different.
Doesn't sound very modular, does it? Practically the antithesis of good OO practice.
Suppose I now told you those two areas were "behaviour" and "data".
Don't mind me. Just thinking out loud...
Adam Turoff: More thoughts on rewriting software
I started writing about when it is acceptable to consider rewriting a software project a few months back (part one and two). I remain convinced that it is occasionally economically sound to toss a problematic codebase and start anew. There are dozens of pesky little details to consider, like:
- Is the code horrifically overcomplicated, or just aesthetically unpleasing?
- How soon before the new system can replace the old?
- How soon before there's a net benefit to the rewrite?
- Are you rewriting to address fundamental flaws, or adopt this week's fashionable language/library/architecture/buzzword?
- Do you understand the problem the code attempts to solve? Really? Really?
- Since the project began, is there a new piece of off-the-shelf piece of software that makes a lot of this pain simply go away?
Steve Yegge looks at the problem from a different angle in his essay Code's Worst Enemy. (See Reginald Braithwaite's synopsis if you want to read just the choice quotes.) Steve argues that code size is easily the riskiest element in a project:
My minority opinion is that a mountain of code is the worst thing that can befall a person, a team, a company. I believe that code weight wrecks projects and companies, that it forces rewrites after a certain size, and that smart teams will do everything in their power to keep their code base from becoming a mountain. Tools or no tools. That's what I believe.Steve's essay focuses on behaviors endemic among many Java programmers that lead to large codebases that only get larger. As codebases grow, they become difficult to manage, both in terms of the tools we use to build software from the code (IDEs and the like), as well as the cognitive load needed to keep track of what 20,000 pages of code do on a 1 million line project.
The issues aren't specific to Java, or even Java programmers. Rather, they stem from an idea that the size of a code base has no impact on the overall health of a project.
The solution? Be concise. Do what it takes to keep a project small and manageable.
Of course, there are many ways to achieve this goal. One way is to rewrite large, overgrown projects and rebuild them from scratch. This could be done in the same language (building upon the skills of the developers currently on the project), or porting the project to a new language. Another strategy involves splitting a large project into two or more isolated projects with clearly defined interfaces and responsibilities. Many more alternatives exist that don't involve ignoring the problem and letting a 1 million line project fester into a 5 million line project.
Interestingly, Jeff Atwood touched upon the issue as well, in his essay Nobody Cares What Your Code Looks Like. Jeff re-examines the great Bugzilla rewrite, when the team at Netscape decided in 1998 to convert the code from Tcl to Perl. The goal was ostensibly to encourage more contributions, since few people would be interested in learning Tcl to make contributions to Bugzilla. Nine years later, and the Bugzilla team considers Perl to be its biggest liability, because Perl is stagnating, and Perl culture values the ability of every Perl programmer to speak a slightly different dialect of Perl. Newer projects written in PHP, Python, Java and Ruby outcompete Bugzilla because (in a couple cases) they are comparable to Bugzilla today (without taking nine years of development to reach that plateau), and can deliver new features faster than the Bugzilla team can.
Nevertheless, Jeff stresses that although it may be ugly, harder to customize and extend, Bugzilla works. And it has worked for nearly a decade. And numerous large projects use it, and have no intentions to switch to the new bug tracker of the week anytime soon. So what if the code is ugly?
There's a lesson here, and I don't think it's Jeff's idea that nobody cares what your code looks like. Jeff is right that delivering value to customers is always most important, whether they are paying customers that keep your company in business, or users who rely on your open source project to supply a critical piece of infrastructure. He's also right that customers couldn't care less if your code uses Factories, Decorators and Iterators, or Closures, Catamorphisms and Currying. It is a disservice to your customers if you force them to wait while you rewrite your software from a static language (like Java) to a dynamic language (like Ruby), because dynamic languages are all the rage this year. Are you going to go through the same song and dance when type inferencing becomes popular? Massive concurrency?
While customers don't care about how a product is written, they do care about the effects of that choice. If your software crashes a lot, needs frequent security patches and occasionally corrupts data, well, maybe you shouldn't have written your timesheet application in C. If your rendering application is slow, uses ludicrous amounts of memory, then maybe you shouldn't have written it in Ruby. If your application provides a key piece of infrastructure, and there's literally no one who could replace you if you get hit by a bus, then maybe you shouldn't have written it in APL.
And if your application is written in a manner that leads to a huge codebase that makes it hard to find and fix bugs, costly to extend and requires a floor full of programmers to maintain, maybe you owe it to your customer to find a way to reduce the size of your codebase and deliver more value. Because sooner or later, that customer just might find a similar application, built with a smaller codebase and less internal complexity that's cheaper own and faster to customize and fix. And when it becomes too costly or too painful to maintain your application, they will switch.
Paul Potts: Newegg Screws Up
They took the order for a camera, case, memory cards, and card reader. I paid with PayPal; everything went through normally. The package went out; it is supposed to be delivered today. I wanted to make sure of that, since we're obviously getting pretty close to Christmas, and my family is also planning on going out of town. In fact, we're taking the train out of town to see family. The plan was for my son to enjoy taking pictures of the trip. So it has to be here, or there wasn't much point.
Today, the day that my UPS package I've been tracking is scheduled for delivery, I got a note saying that it was all just a joke... the package I've been tracking doesn't actually have a camera in it, and I should get a refund in two or three days. Oh, it does have a cheap little camera case in it, which I threw in just because they were shipping me the camera anyway. Which means I just paid $5.24 to ship a $10 camera case.
I'm scrambling to try find the camera locally. I'm fortunate in that my finances aren't that tight right now, but if they were, I'd be completely screwed, because i wouldn't be able to charge the replacement camera on my debit card until the PayPal refund went through.
I can't recall any company I've ever ordered from screwing up an order in quite this way. I mean, I've had items cancelled on me at the last minute, or delayed, but I've never, ever been charged for an item that was not actually shipped. I'm a bit boggled by just what kind of a failure in their IT infrastructure allowed the charge to go through. Wow!
Magnus Therning: Mail!
Yes, I think there’s an opening for an email client, it doesn’t have to be written in Haskell of course, but if I ever get my arse into gear it will be. Especially now that mutt-ng seems to have stalled in development, and even though mutt still is being developed I’ve gotten too spoilt by using mutt-ng exclusively for the last year or so. I’ve looked extensively at sup and it’s sweet, but due to some recent changes in what kind of machines I have access to on the web it doesn’t quite fit me anymore.
What would my ideal email client look like?
- GMail as backend, accessed through Python’s libgmail. Hopefully it won’t be too difficult to write a Haskell module to deliver this part, but using Python to begin with is absolutely acceptable.
- Haskell for the frontend, specifically using vty for the UI.
- Vim, Yi, or any other old terminal-based editor to write email.
I’m confident vty has enough functionality. I’ve played with libgmail enough to be confident it offers enough access to mail data to do most everything I want from a client (the missing part is sending PGP/MIME messages, but sending mail through Google’s SMTP server is a workable solution). I’ve just started looking at options for mail parsing in Haskell, identifying three and already discarding one…
Yes, it’s all vapourware at this point, but hey, I can dream, right?
Ulisses Costa: Catamorphisms in Haskell
Lately I have had many works to do at university, therefore I’m sorry for the non regularity of my post’s.
By the way, I also liked to announce that this is my first conscientious post at Planet Haskell.
Catamorphisms is the way that we can explain in one function how recursive patterns works in some data type.
Here I will use Point-Free notation because what matters here is to show the data flow and the composition of functions.
Point-Free style is used to think in data flow terms, and very useful to program verification, applying formalism to our code.
In point-free style of programming programs are expressed as combinations of simpler functions. This notation is known as write functions without their arguments. Pointwise is the normal form how we write a function.
Couple of examples of point-free notation:
1)
2)
f = (*10).(+2) -- point-free f n = (n+2)*10 -- pointwise ClarificationsFirst of all to define a function, for example f:
I say:
or
or
I will assume that you are familiarized with infix notation, *const*, *either*, *uncurry* and composition (.) function.
TypesIn Haskell we have this definition for lists:
data [a] = [] | a : [a]Let’s create the same, but more convenient. Consider the following isomorphic type for lists:
data List a = Empty | Node(a,List a) deriving ShowTo represent [1,2,3] we wrote Node(1,Node(2,Node(3,Empty))).
As you can see, to construct a (List a) we have two options, Empty or Node.
Formally we represent the constructor Empty as 1.
And we use (+) to say that our two possibilities are 1 or Node.
We could see Node as a the following function:
Node :: (a,List a) -> List aSo typologically we have 1 + (a,List a).
We use (*) to define that two things occurs in parallel, like tuples do, so we can redefine it:
1 + (a * List a)
Now we can say that (List a) is isomorphic to (1 + a * List a).
This is something to say that (List a) and (1 + a * List a) keep the same information without any change or any loss.
Let *A, B, C, D* be Inductive data types (sets) and *out, cata, rec* functions.
We will write using the composition of *out, cata, rec* functions.
That way we are breaking our problem in small ones.
So, in the end we will have the following definition for :
The function that we want is *cata(g)*, and that function is over (List a) so we have:
cata :: (D -> C) -> List a -> CType A is (List a).
Maybe this isn’t clear yet, let’s start with function *out*
outThe function outList is responsible to create the isomorphism between (1 + a * List a) and (List a), so the code could be something like this:
outList :: List a -> Either () (a,List a) outList Empty = Left () outList (Node t) = Right tIn haskell we represent the type 1 as (), (+) as Either and (*) as (,).
So, type B is (1 + a * List a).
function gThe function g is also known as *gen*, here is where we said the step that pattern do.
Imagine that we want to insert all the values of (List a) into [a]:
-- pointwise g :: Either () (a,[a]) -> [a] g (Left()) = [] g (Right(a,h)) = a:h -- pointfree g = either (const []) (uncurry (:))We represent cata(g) as .
Now we can be more specific with our graphic:
Here we have to get a function *rec* that transform (1 + (a * List a)) into (1 + (a * [a])).
That function, general rec, will be:
recg f g h = f -|- (g >< h) where (f -|- g) x = either (Left . f) (Right . g) x (f >< g) x = ((f . fst) x , (g . snd) x)With that function we can say exactly what to do with type (1), (a), and (List a) in domain of *rec*.
So we want something like this:
rec g = recG id id glike that we said that (1 + (a * _)) will be the same in the counter domain (1 + (a * _)) of *rec*.
Now we need a function that receive a (List a) and give us a [a]…
Yes, that function is …
So, the final graphic became:
cataFinally we gonna to define the function *cata(g)*:
cata g = outList . rec (cata g) . gwhere g is our *gen* function,
g = either (const []) (uncurry (:))And our objective:
List2HaskellList = cata $ either (const []) (uncurry (:)) More catamorphismsImagine we have the following data type:
data NList a where Leaf :: a -> NList a NNode :: a -> [NList a] -> NList a*out*, *rec*, and *cata* became:
out (Leaf a) = Left a out (NNode a l) = Right (a,l)Using the previous definitions of (-|-) and (>)
rec f = id -|- (id >< map f) cata g = out . rec (cata g) . gImagging that g has type:
g :: Either a (a,[[a]]) -> [a]And the graphic for this cata became:
ConclusionI’ve talked about cata’s without any formalism, the idea was to explain to someone who didn’t know.
I will talk more about catamorphisms and how to calculate programs with them.
In the future I will like to talk about anamorphisms too. And Later on I will talk about point-free over non recursive functions.
Brent Yorgey: Brent
If 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!!
Mikael Johansson (Syzygy-): The year 2007 in review
From each month, the first sentence of the first post.
January: I decided on a whim to look in at the Dilbertblog, where the top post at the moment has Scott Adams calling all atheists that discuss on the net irrational, using a rather neat strawman carbon copy of most discussions of faith between believers (i.e. mostly Christians) and atheists he has seen on the web.
February: The second carnival of mathematics is up over at Good Math, Bad Math.
March: I just met up with the workgroup in the Deutsche Mathematikervereinigung (German Association of Mathematicians) with interest spanning “Information and Communication” - which turns out to mean that they care about libraries, about communicative tools for mathematicians, and spend their time thinking about these things, and meeting at conferences.
April: The website/forumsite Mathetreff, run by the Bezirksregierung (region government) Düsseldorf, just performed a mail interview with me.
May: In about 23 hours, I’ll step on to the train in Jena, heading for T’bilisi, Georgia.
June: Too harried to blog.
July: … or another bout of more-or-less shameless self-promotion.
August: Trying to make the time until my flight leaves tomorrow go by, I played around a bit with the proof assistant Coq.
September: No mathematical content today.
Note: The first september post consisted of a CAS interaction dump. Not fun to quote, so I took the second post.
October: In a conversation on IRC, I started prodding at low-order wreath products.
November: In a recent column at The Chronicle of Higher Education, the columnist writes:
December: I just received my first ever referee’s report.
In conclusion - living in Germany affects me adversely. The number of first sentences that span the entire first paragraph of the posts I’ve been looking at is staggering.
Tom Moertel: PXSL Tools 1.0: Your ticket out of XML Hell
XML is fine for representing document-like things, but when it’s twisted to represent build recipes, configuration files, and little programming languages, it opens the gates to XML Hell. Once the gates are opened, the demons of cargo-cult thinking are loosed upon the world, where they are free to trick innocent programmers into working with grotesquely twisted XML documents – something no human mind was designed to comprehend. Ensnared, these programmers are slowly drawn into the depths of XML Hell, from which their lamentations echo across the universe.
When the demons of cargo-cult thinking come for you, don’t be ensnared! Instead, be prepared – with PXSL – the Parsimonious XML Shorthand Language (pronounced “pixel”).
What’s PXSL? It’s a luxurious, thermonuclear smoking jacket that you can slip on using a convenient preprocessor. Use it whenever you see grotesque XML on the horizon. Within PXSL’s plush (and stylish) protection, you can create all the nasty, twisted XML that may be demanded of you, but you need not descend into XML Hell to do it. Instead, you can work from the comfort of a well-stocked lounge, where clarity and conciseness are always on tap.
For example, here’s a snippet from an XSLT stylesheet, in the original XML:
<xsl:template match="/"> <xsl:for-each select="//*/@src|//*/@href"> <xsl:value-of select="."/> <xsl:text> </xsl:text> </xsl:for-each> </xsl:template>And here’s the same snippet, written in PXSL:
template / for-each //*/@src|//*/@href value-of . text << >>Isn’t that refreshing?
Why PXSL?There are lots of XML shorthands available. (The PXSL FAQ lists about ten of them.) So why choose PXSL? Here’s why:
- PXSL lets you intermix PXSL and XML syntax in one document. Feel free to use whichever syntax works best for each portion of your documents. (See the PXSL documentation for some examples.)
- PXSL is customizable with application-specific shortcuts. (The PXSL snippet above, for example, uses XSLT shortcuts. Again, the PXSL documentation has examples.)
- PXSL has a powerful macro system that lets you build complicated document structures safely and conveniently. (Read about macros in the PXSL documentation. For an advanced example of what you can do with PXSL macros, see this article on refactoring XSLT one-offs into clean, maintainable code.)
Also, PXSL is battle tested. It was first released in 2003 and has been saving people from XML Hell since. People who try it seem to like it:
- I think PXSL could do wonders for soothing my irrational hatred for all things XML. —kowey
- Impressive… I converted some of my files from XML to PXSL and the readability was much improved. —chris
- Quite aside from the fact that XSLT is finally somewhat readable, the fact that you’ve added a serious macro system means that some serious scripting of XML can occur. I’m very impressed. —invisible
The next time you’re headed for XML Hell, why not give the venerable PXSL a try? You might just find that you like it, too.
This public service announcement was brought to you in celebration of the 1.0 release of the pxsl-tools package. The PXSL-to-XML compiler pxslcc is written in Haskell and uses the cross-platform Haskell Cabal build/package system to let you use PXSL just about anywhere.
Eric Kow (kowey): mail?
When's the mail client coming? I'm asking this in the random speculative sense, not in the "gimme a Haskell mail client now" sense. What would a Haskell mail client look like? I'm guessing that plugins will play a nice role, extensibility and all. Being able to handle really large mailboxes (a big "archive" folder) would be nice. Perhaps Sup would be good inspiration. Come to think of it, maybe the client should be implemented in Cat, just for the name...
"Alpheccar": A Web Monad
In my last post, I was writing about the use of coproduct of free monads to do content-type dispatching in a web monad. It was working but it was not the right approach. I changed everything and introduced a lattice of lists at the type level to track hierarchical dependencies between formats and do content-type dispatching thanks to type information. I also added a few other features to my Web Monad.
Philip Wadler: Johnny Ball: A Betrayal of Science
The beginning of his talk was a beautiful introduction to square laws in the work of Galileo, Kepler, and Newton, with some lovely audience-participation demonstrations showing the value of experiment. Unfortunately, this was belied by the second half, a rant in denial of climate change that included statements such as 'The greens don't want modern society to work so they've decided to demonize carbon' and 'Carbon makes up only 1/3000 of the gases in the atmosphere. Can that have such a big effect? I don't think so'. No mention of the IPCC or the scientific consensus that contradicts his view.
The danger in this is that he may leave youngsters feeling that scientific disputes are similar to political disputes, with no understanding of how the scientific method can establish truth independent of popular opinion.
I gather his hosts, the University of Edinburgh and the Royal Society of Edinburgh, had no idea he was going to go off on this tangent. Going by the first half of his talk, he used to be capable of giving a truly wonderful introduction to science for young people. But now he should not be let near them; he has betrayed his trust.