Posted by Daniel Lyons
Mon, 12 May 2008 15:17:00 GMT
Over the weekend I wrote the same program in three (almost four) languages: Haskell, Common Lisp, Erlang and almost Prolog.
I have an informal result I want to share. The first one I wrote was in Haskell. Of the four, it was definitely the most fun to write. I did, however, avoid monadic computation when it probably would have been amenable, instead I opted to use interact and a small combinator of my own design. In a “real” program in a strict language I’m sure it would have been inefficient. I felt the freedom of Haskell, letting you design the solution in the most abstract, high-level way you can imagine it, and still make it quite small.
Next up was Common Lisp. I was surprised by several things. For one, it was shorter by a handful of lines than the Haskell version. I used essentially the same design as the Haskell and that seemed to work well enough, though Lisp lacks the combinators that Haskell comes with, so I wound up using a do loop for something I was just doing with map in Haskell. And of course I was annoyed by the effort it takes to produce an executable: (sb-ext:save-lisp-and-die "a.out" :toplevel 'main :purify t :executable t).
Then I started on Prolog. Of course, the logical part of the problem was short and sweet. Then I thought about what it would take to do line input/output, got the shivers, and decided to move over to Erlang. The syntax is fairly similar, though the execution strategy is shockingly different, but this application didn’t require any backtracking anyway.
Erlang wound up being shorter than Lisp or Haskell.
This fact stunned me, though I can explain it: Lisp requires a fair amount of schmuzz to do things that are free in Haskell and Erlang (namely, defun steals a line for itself) and Haskell requires a fair amount of schmuzz for human-assisted type checking. Erlang didn’t need either of those and has some of the strongest pattern matching around (though the limited guard support is obnoxious). Erlang did need Rubyesque and despicable list_to_integer and atom_to_list type conversions, but none of those cost me a line. You could omit the type declarations in Haskell, and I did add a line to make the type signatures more readable, but that’s really bad form.
I also found myself wondering how much I was buying myself by using Haskell’s data types for part of the computation. What’s the difference between reading a character or two to create a special instance of some data type and then using that everywhere, versus just using the character? In Haskell I’ll get a read error, whereas in Lisp and Erlang an ecase or a pattern match is going to fail later in the game, but not that much later. Does the anal retentiveness pay off in the end? I’m starting to wonder if, as Jonathan Edwards is proposing, formality is a cure that’s worse than the disease.
- Erlang was the shortest (least syntactic BS as far as writing functions are concerned).
- Erlang was the hardest to debug (the error messages are more machine-readable than human-readable).
- Haskell was the most fun to write (I guess I like function combinators and higher-order programming).
- Haskell took the longest to write (it was the first one I did).
- Lisp was the easiest to write and debug.
- Lisp was the hardest to get to a binary of those that could (I don’t think Erlang can ever give you back a binary directly).
- Lisp’s schmuzz was the most obnoxious to write (especially the hapless
destructuring-bind, which is substantially underpowered compared to Erlang’s or Haskell’s pattern matching facility).
I think I will try using Common Lisp’s bind library later this week to rewrite this and see if I like that better than destructuring-bind.
Tags erlang, haskell, lisp | 2 comments
Posted by Daniel Lyons
Sat, 08 Dec 2007 23:48:00 GMT
“GWT 1.5, due in the first quarter of 2008, will produce “better” JavaScript code than manual programming by the industry’s best and brightest – in terms of speed, size and manageability of code. GWT 1.5 is also expected to improve compilation of Java code.”
—Google’s next web toolkit thinks it’s better than you
Let’s try that claim again with some different technologies. “gcc will produce ‘better’ assembly code than manual programming by the industry’s best and brightest—in terms of speed, size and manageability of code.” The claim sounds pretty unlikely, don’t you think? How are you going to do better than manual human intelligence on all three fronts that matter? But something is missing. What language are we compiling from and to?
GWT is in the somewhat ironic position of compiling Java to JavaScript. By analogy, this is like saying you can compile from C to Lisp and produce better Lisp than experts could—in terms of speed, size and manageability. Does that seem likely? Then how, pray tell, could someone compile from a language that lacks full closures and prototyping OO to one that does, improving all three of those things at the same time? For that matter, when has compiled code ever been smaller than manually written code?
I don’t know anyone using GWT, because the only people who would use it would already be using Java and I don’t know anyone doing serious web development in Java. Web development is hard in a way that precludes clunky languages (but not stupid ones like PHP).
It reminds me of the other night when my room mate David Baird and I were talking about simplicity. To some idiots, MySQL is simpler than PostgreSQL. This claim is bizarre to me, since MySQL’s source is 10 MB larger compressed, MySQL deviates intentionally and insanely from the SQL standard, and MySQL includes a variety of obnoxious features that no true database would provide. Yet it is considered simple and “industry standard.”
Half of it is from The Rise of Worse is Better, MySQL chooses to make the implementation simpler than the interface, whereas PostgreSQL prizes the interface more. Why else would MySQL’s SQL syntax change with every release, while PostgreSQL’s remains the same? But this doesn’t explain the absurd notion of table types, which only MySQL has.
There is another dichotomy here, between differing conceptions of simplicity. Which of these is simpler?
sum = foldr (+) 0
Or:
int sum(list_t list) {
sum = 0;
for (cur = list; cur != NULL; cur = cur->next)
sum += cur->value;
return sum;
}
There are at least three different ways of looking at this:
- “You’re comparing apples to oranges! Unfair!”
- “The C version is simpler because it’s closer to what’s really happening.”
- “The Haskell version is simpler because it’s closest to the concept.”
People who fall under category one are the kind of people who say things like “it doesn’t matter what language you choose to implement something in, because they’re all Turing-complete.” It only doesn’t matter if the time it takes to write, the experience of writing it, the quantity and severity of the bugs introduced while writing it and the human resources required to write it don’t matter. I think a lot of people say this because they don’t want to get into a religious war about language—it’s a cop-out.
What I’m really interested in is what happens to people to make them fall under category 2 or 3. I think this quote from Alan G. Carter’s Why No-One’s Noticed This Before may be the essence of it:
“We don’t miss what we haven’t got, and this can lead to seeing things in profoundly different ways. A person who frequently does juxtapositional thinking is aware of the importance of self-consistency in their thinking. If something doesn’t “hang together”, they know they have made an error. Often they use self-consistency as the basis of their thinking, deducing that something must be missing, and then being able to find it. A person who is rarely if ever in a position to do juxtapositional thinking, will not consider or expect self-consistency in this way. Their view of reality is therefore fragmented. If they don’t require their understanding to hang together, they develop the idea of “mere facts”. What are facts? What do they prove? Nothing! Instead they use their focussed attention to concentrate on compliance with a proceduralism, and they don’t let mere facts get in the way. They certainly don’t trust their own good senses.”
Look again at PostgreSQL. It assumes that the database is there to alleviate certain burdens. It provides you with SQL. At that point, the database’s job is complete and it is up to you to learn SQL. Learning SQL may imply learning the theory of relational databases. PostgreSQL isn’t there to hold your hand and help you do this. If it takes you 30 minutes to write an SQL statement, well, that’s how long it takes you to write it. People in category 3 don’t mind, because they’d rather have one comprehensive solution for their data situation that hangs together.
Look at MySQL again. Table types aren’t part of data management, they’re a leaky abstraction, an exposure of low-level details. MySQL’s query planner also sucks compared to PostgreSQL’s. Perhaps most damningly, MySQL doesn’t support two of the three fundamental set operations (INTERSECT and MINUS/EXCEPT). If you were modeling a relational database on set theory, you probably would have started there.
Yet MySQL is full of tiny details meant to “helpfully simplify” some aspect of databases. Such as the TIMESTAMP type. There is no other type in MySQL which is defined as equivalent to some other type plus some behavior. There is no other type in MySQL defined so, nor in all of PostgreSQL, defined in terms of behavior (when you UPDATE a row with a TIMESTAMP column, the TIMESTAMP column receives the current time even if you didn’t specify that it should be modified). However, I haven’t ever seen someone intentionally use the TIMESTAMP feature for what it’s there for, just people stumbling onto it and realizing that a whole bunch of data they thought they had has actually been obliterated. It doesn’t hang together.
David and I concluded that there is a kind of simplicity which requires learning and a kind of simplicity which attempts to avoid it. Some people find the thought of recursion and higher-order functions a lot less simple than for loops. And yet, for loops become more sophisticated in mundane languages with each successive one.
There are people who find the REPL a horribly frightening place. Look at the complete lack of “noise” in the Haskell code. It’s nothing but you, G-d and the problem. There is no public static void main. There is a desire to be typing while programming, and in plenty of languages you have to push this edifice of text around before you can begin to get anything done. There is a sensation of programming when really you’re doing nothing. You can reason operationally and have the appearance of getting things done. Somebody wrote an API for making new table types in MySQL. I have no doubt this is far simpler than improving the query planner. Someone else contributed a BerkDB table type for MySQL. I have no doubt this was fairly simple. But why would you? This is problem avoidance, but adds so many megabytes to the source code, which nobody even actually uses. There is a digital artifact to this lack of interest in actually getting anything done.
People use ActiveRecord to avoid learning SQL and relational database theory. Yet, I know plenty of people who have not studied relational database theory but who understand it anyway. A lot of people start out making tables that aren’t normalized. After a while they start to use joins. Eventually they acquire the insights, usually after not very long, say a year or two, and then they are as good as someone who has studied it. After a while they begin to be annoyed with MySQL. ActiveRecord is there to make dealing with the database more like dealing with Ruby. As long as everything is in one language, it should hang together better. But of course, ActiveRecord is built for MySQL primarily, but with an eye to portability. The advanced database users grow annoyed at it because it also represents problem avoidance.
The GWT is a lot like ActiveRecord. It wants to mitigate some problem which isn’t, in reality, a problem. It’s a nightlight. When you look at my Rails code, you see a lot of me manually executing SQL. This practice is encouraged by the books and DHH and many other Rails users do this. However, it ties you to a particular database—PostgreSQL in my case. Is your database a problem, or a solved problem? GWT is saying JavaScript is a problem, do you think JavaScript is a problem?
I can certainly look at Ruby and SQL and say, both of these things are great. I have some trouble looking at JavaScript and turning in revulsion, asking for Java to come and mitigate the pain.
Tags gwt, haskell, java, javascript, programming, rails, ruby, sql | 5 comments
Posted by Daniel Lyons
Sun, 11 Nov 2007 01:35:00 GMT
One of the great pleasures of being a Haskell user is using hylomorphisms to accomplish all your work. To wit:
factorial x = foldr (*) 1 [2..x]
fibonacci = 1 : 1 : (zipWith (+) fibonacci (tail fibonacci))
Obviously this kind of obnoxious behavior would have to be ported to Lisp at some point. And it was, via the Series macro package. It’s Appendix A in CLtL.
In Lisp you’ll have to make a few concessions. You have to construct your series from other series. There are some handy ways of getting a series from a list or vector or another series. You’re limited to lazy lists using this functionality. Still, it’s fun.
To get started, install SERIES with (asdf-install:install 'series) and then import it with (require :series) and (use-package :series).
(defun fac (n)
(collect-product (scan-range :from 2 :upto n)))
This is a pretty straight across port: [x..y] becomes (scan-range :from x :upto y). You can omit the :from and it will start with 0, omit the :upto and it will go on forever. There’s also :by which defaults to 1 for replicating the [n,m..z] syntax in Haskell. You also have :length to ensure that you only get so many (very helpful during programming because of the “P” in REPL.) And misc predicates like :above and :below are useful in certain situations. You can also use :type to change the type to ‘float if you want to produce series of floats.
collect-product does what it sounds like it would, multiplying all of the numbers together. If we didn’t have it built-in, you could replicate the functionality with (collect-fn :integer (constantly 1) #'* (scan-range ...)).
Dealing with the Fibonacci numbers is a bit more complicated:
(defvar fibs
(scan-fn '(values :integer :integer)
(lambda () (values 1 1))
(lambda (x y) (values y (+ x y)))))
This works using Lisp’s multiple return values system. Basically, we’re returning two values with each function call; one of them is being passed out to be the item, and both are being fed back through the series generator. It’s not as beautiful as the Haskell but it captures the same concept, is as general (for lists) and performs some similar optimizations.
Tags haskell, lisp | 1 comment
Posted by Daniel Lyons
Thu, 04 Oct 2007 02:27:00 GMT
I noticed something interesting the other day about the functional and object-oriented languages.
Consider Python, where you can write functions like:
def foo(first, second=0, *rest, **kwargs):
return first + second / len(rest) * kwargs['multiple']
Compare to a functional language like Haskell, where you can’t do that, but you can create types like:
data MyThing = YourThing Integer
| AnotherThing (Int, Char, Float)
| NoThing
Weird that in Haskell, a functional language, you don’t get keyword arguments or arbitrary numbers of arguments, but you do in Python, whereas in Python, you’re confined to a rather small set of built-in types or full-on objects.
Of course in Lisp, you get really ornate functions and the ability to make new types through OOP. But you don’t get strong typing. ;)
Tags haskell, languages, programming, python | 2 comments
Posted by Daniel Lyons
Fri, 28 Sep 2007 09:11:00 GMT
My faith in Haskell has wavered somewhat lately, and all because of Reddit. Essentially, three things:
- Haskell’s fixed-point combinator,
y f = f (y f).
- The ramifications of Haskell’s purity on abstraction.
- Haskell’s epidemic academia.
The first is really two problems. One is that the usual definition of the Y-combinator is not itself recursive. Obnoxious. The second problem is that, though it’s beautiful, there are a number of problems that you can’t express in Haskell using the above combinator which you could in an untyped language. This isn’t, apparently, news to anyone but me. I can’t see how to use the above Y-combinator. This is an incredibly academic problem, like most Haskell problems, but it bugs me a little.
The second was elucidated by Peter Van Roy on Lambda the Ultimate’s forum:
“True state lets information pass “underground” between two interfaces, i.e., the information passes without any apparent connection between them. This is because the connection is the shared state, which is shared by the two interfaces yet hidden from the outside. The shared state is a kind of covert information channel: it lets a module pass information to other modules (or to itself in the future) without anybody else seeing it.”
His point has to do with the fact that Haskell’s purity means that in order to get data from some point A to some point B through a number of other modules, each of the intermediate modules will have to carry the information around, even if it doesn’t do anything with it.
I would like to hate that, really, I would. But I can’t, because I programmed Voltaire in a very functional and abstract way in PHP partly because I could count on a handful of global variables passing some state around “underground” between modules that were loosely connected. In particular, Voltaire creates a region context and a template context in which each script is evaluated. The database connection is also shared clandestinely like this. If I were using Haskell, every function in the system would have to take an extra four parameters to get the current region, template, path and database connection, even if it wasn’t going to use it or pass it directly to a child.
It’s easy to denounce. At the same time I feel blameless for having done it, because while the state is “available” to anything beneath, nothing should be changing these variables outside the core. It’s available in a read-only way. Later on I wrote a plugin for rendering templates programmatically, and that involved understanding the inner state, and another plugin for producing lists which also involved understanding the inner state. But languages like Lisp provide interesting semantics for those times when you would want to change the behavior of a global variable safely.
Which brings me back around to Lisp, the language I have paid the least attention to of the four or so that I decided were “safe” so long ago when I started to force myself to use functional programming. And, truly, there are things about Lisp which are hard to love. The principle advantage of Lisp is that it permits you syntactic innovation. It’s certainly the only language that provides it meaningfully (let us not quibble about Lisp/Scheme differences or bizarre languages like Pliant). But doesn’t this seem like the fundamental abstraction of programming languages?
Aren’t we always starting with some problem and selecting a language based on its syntactic abstraction of some part of the problem domain? I mean, I pick Lisp because I want the ability to create my own structures. That comes in handy against every problem domain. But if I want to write a blog, well, Rails makes it a lot easier up front. Maybe I don’t get linguistic abstraction, but the starting abstraction is quite close. Michael chooses REALbasic for application development, I choose Cocoa. Both of us are making certain sacrifices in the name of abstraction. I lose defmacro. He loses the most recent Cocoa innovations. If I pick Lisp for my blog, then I’m sacrificing the fast start. The laziness of later syntactic abstraction had better pay off. The up-front cost is higher. For any given reasonable language, there is going to be a situation in which its abstraction is an up-front benefit that beats the up-front cost of using Lisp.
You see, these languages are compression algorithms. They compress your explanation of how to solve a problem. Like any compression algorithm, there are problems for each language that compress so badly you wind up writing a different language inside the language. This is Greenspun’s law all over again. Lisp wins frequently because it makes it easy to create a sublanguage for a subproblem that compresses it better. Ruby wins frequently because it encompasses most problem domains.
And Haskell wins frequently in academia because academia is interested in representative subproblems rather than complete problems. My experience on the ICFP this past year was that when you give Haskell a pure math problem, it will beat nearly anything else hands-down for both readability and speed. Now sprinkle some I/O on the problem. How about a non-local return? Perhaps a bit of, dare I say it, destructive state? Suddenly you find yourself looking up “monad transformer,” wondering what the hell you got yourself into.
And Justin, G-d bless him, is a Haskell wizard. I can sort of read the code he wrote. My contribution to that code was negligible. I wasn’t much help debugging it. But at the end, we had a performant Haskell version using prominent Haskell performance themes. But it was also 300 lines of code. I remain convinced against any of that pesky proof stuff that an OCaml implementation would have been half the length, more understandable, maintainable and debuggable. I believe Justin came away from the contest with the opposite conclusion: proof, solid proof, that Haskell can be made to attack the kinds of domains that other languages are generally selected for. In other words, his success with Haskell encourages him to use it more, whereas it filled me with doubt.
And today I see on Reddit a link to the paper introducing Haskell Server Pages. Not to the code itself, or the documentation talking about it, or to a page talking about it or some examples, but to an academic paper about it. I write on Reddit that “I have to admit I’m getting a bit tired of seeing things that should be cool Haskell libraries show up as academic papers. It’s as though the whole industry has turned its gaze to Haskell, exasperatedly asking to see something practical, and instead of turning out practical things, the Haskell world turns out academic papers about practical things. “Proof” that Haskell can be used practically is not the same as people using Haskell practically, nor the same as people practically deciding to use Haskell.”
Let’s face it. I really enjoy Haskell in part because of its snobbery, but that’s really a part of what it is. And the posturing about how mind-expanding it is. Haskell is addicted to academia. You’re much more likely to see a paper about some neat library than a neat library. When you go look at the code, it’s untested, only works on one platform, is broken or partially implemented. Academics are not rewarded for having good, useful code. They’re rewarded for writing papers.
Look at the Wash page and tell me who’s going to use this framework. Look at the first four links. Notice these PDFs and PS files are all LaTeX output. What kind of web people would do this? Academic web people.
So here we are. I suppose every language has its vices. I’m particularly drawn to languages that do a lot of posturing, apparently. Beyond that I’m not sure what to conclude. Every language that isn’t pure offal (Java) seems to have a place in the world. It would be better not to get too worked up about it, but it’s probably impossible.
Tags academia, haskell, languages, lisp, programming | 1 comment
Posted by Daniel Lyons
Thu, 20 Sep 2007 07:14:00 GMT
For a good time, please read a very twisted analysis of the benefits of performing poorly. (To my new anal-retentive readers: you try and figure out this guy’s name, and then I’ll cite it).
I have some remarks on Reddit which I’m proud enough of that I thought I’d share them with you sharks here. I wonder if the author has really listened to his own argument. I find it somewhat lacking in the “holding water” department:
“If you know the language to be dog slow any way, you’re much less likely to waste your time on the pointless microoptimizations that geeks so love…”
I think this one works equally well in reverse: if you know the language is already quite fast, you’re much less likely to waste time on pointless micro-optimizations that geeks so love. In fact, if your language is dog slow, there are probably more optimization opportunities than there are if it’s already quite fast, as a matter of diminishing returns.
“The fact that non-standard library code is inherently somewhat inferior adds further incentive to attempt community wide standardization…”
This fails rather spectacularly to explain why the Common Lisp standard includes such a huge standard library. Consider the inverse argument: “the fact that your library code runs as well as built-in code removes incentive to use the standard library.” In the magical imaginary world I pretend to live in, people apply appropriate abstractions without much regard for the performance—abstractions that perform radically poorly being considered inappropriate, I guess—but I would never imagine sitting on my hands, wondering whether or not I can “afford” the overhead of a function call.
“Python’s very slowness represents part of its competetive edge over languages that are in some ways better engineered and more capable…”
What is this, things that are poor in one area tend to be good in others?
I could only consider agreeing if somehow it were a zero-sum equation: all languages have equal amounts of effort applied to them, and some of it goes to performance. But it’s not a zero-sum equation, languages receive differing amounts of attention to different strengths for different reasons. Moore’s law and the rapidly increasing demand for programming alone have enabled Python to compete against a language three times older, better designed, implemented and specified.
Actually, no, that’s flat-out nonsense.
“I’d not be suprised if on the whole it greatly increases programmer productivity and results in clearer and more uniform code…”
I would tend to expect uniformity from any language which syntactically enforces it. :)
I certainly would not expect a poorly-performing program to go through as many stages of evolution as a rapid program. You have to factor in the compilation phase—but one usually doesn’t compile in-development Lisp programs while working on them. They evolve much more organically, because there’s not necessarily a separation between development and testing, whereas in Python there is to a larger extent. Supposing the compile-time differences are negligible (which, they are, if you are careful) I have a hard time believing that Python programs running more slowly permits more evolution to take place.
“Also, since only builtins have reasonable performance there’s added motiviation to become very familiar with the available builtins and far less temptation to roll one’s own version of say dict.setdefault (even if it it sucks)...”
I think the existence of sucky built-ins like setdefault contradicts the point about the quality of the standard library. From where I’m sitting, the quality of the standard library is a function of backwards-compatibility more than community involvement. Lisp has a larger, somewhat clunkier one because it is much older. Ruby’s library is much cleaner because it went through a lot of life without having to worry about backwards compatibility very much. Io is doing even better, having been designed by language aesthetes like Steve Dekorte who are familiar with a lot of good and bad APIs, and who aren’t afraid to break backward compatibility to make a global improvement in expressiveness.
This article nicely dovetails with an argument my friend Pi has been having with various cornholes on IRC about Python and Ruby. Ruby’s standard library is just plain nicer. Which do you prefer, based on your gut instinct:
foo.bar.baz.split.collect { |x| x.bazzle }.join(' ')
Or this:
' '.join([ bazzle(x) for x in string.split(foo.bar()) ])
Hell, for good measure, let’s toss in some Haskell:
unwords $ map bazzle $ words $ foo bar
I’m talking about your aesthetic reaction here. Your artistic reaction. You know which of these you prefer. You want the agglutinative glory of Ruby or the isolating awesome of Haskell. Follow your eyeballs on the above Python example. Compare to Ruby and Haskell. Your eyes hop around on the Python, trying to figure it out. Haskell and Ruby, your eyes slide across from left to right. You feel like you’re reading a language, not decoding one.
As an aside, slap the next person you meet who, ignorant of Haskell, rants about static typing. They’ve never used it, they have no idea what they’re talking about. They’re actually giddy or incensed about type annotations and other forms of busy-work. Don’t put up with it.
Tags haskell, languages, programming, python, ruby | 4 comments
Posted by Daniel Lyons
Sun, 02 Sep 2007 22:51:00 GMT
This is my response to the question as asked on programming.reddit.com.
Depends on the kind. In terms of functional programming, I understand a combinator to be just a less frightening word for higher-order function. So a combinator is a function that combines the behavior of another function with its own. A good example is filter, which just removes certain items from a list. You make a short boolean function that tells you whether or not an item is worth keeping and combine it with filter and some list, and you get the list of items you wanted.
The effect is best illustrated in Haskell where you can call a function with fewer arguments than it requires. This is usually called currying. Supposing our function for determining whether or not an item is interesting is just called interesting, you can create a new function which just gives you back the list of interesting items in a list like this:
neatItems = filter interesting
For the sake of argument, suppose you consider every number one less than a number evenly divisible by three to be “interesting.”
interesting x = x `mod` 3 == 2
Try it out:
neatItems [1..10] -- produces [2,5,8]
The fun doesn’t stop here! Functional languages provide functions with no name for those times when you need to pass something to a combinator but don’t want to bother making it a name. This is usually called an anonymous function or a lambda abstraction. This means you can make neatItems without going to the trouble of defining interesting first, if (for example) you would never use it except in this function anyway:
neatItems = filter (\x -> x `mod` 3 == 2)
Incidentally, whenever you define a function that takes one or more parameters without specifying their names by using combinators, as above, you’re using what’s called points-free style. To facilitate points-free style, you can switch between names and operators in Haskell quite easily by inserting parentheses and back-tics. Haskell lets you use any binary function in-line as an operator if you put back-tics around it, or an operator as a prefix function if you surround it with parentheses, such as (-).
If you want to “curry” an operator, such as to produce a function that multiplies by two, you just put the value inside the parentheses on the side you want. Thanks to basic arithmetic, (2*) and (*2) are the same, but the variable which is “curried” is different depending on the form (the first in the first, second in the second). A “curried” operator is called a section, and I have no idea why.
Another common combinator is (.), the dot operator. Dot lets you string together functions. Suppose you have a function which takes bread and makes toast, and another function which takes toast and butters it. You could glue these two functions together with (.) and arrive at a new function which takes bread and makes buttered toast:
butteredToast = butter . toast
We can now take the above example of filter to its logical extreme by defining our “interesting” test function with sections and the dot operator:
neatItems = filter ((==2) . (`mod`3))
Now there’s no points in that function at all. It’s not exactly a win for readability in this case, however. :) A slight improvement can be made by eliminating some of those parentheses with the ($) operator, which just takes everything on the right-hand side and slaps it into parentheses as an argument to the left-hand side:
neatItems = filter $ (==2) . (`mod`3)
Eh. Still not a lot better. I’d probably take the lambda abstraction over that unless I was feeling feisty.
Combinators come up more frequently in making libraries, much like dynamic method resolution in Ruby. A great example is Parsec, which is a parser combinator library. By introducing its own BNF-style operators, Parsec lets you define parsers in a BNF-reminiscent domain specific language. It’s also good for testing because you can separately test each constituent part’s parse directly rather than being stuck with parsing whole documents. It’s also quite fast. An example from Write Yourself a Scheme in 48 Hours:
parseNumber = liftM (Number . read) $ many1 digit
parseExpr = parseAtom <|> parseString <|> parseNumber
It looks like you’re just defining a kind of token. Actually you’re defining a function with a pretty rough specification, but that’s not your problem as the API’s user. All you have to know is how to use it to parse, which looks like this:
readExpr input = case parse parseExpr "lisp" input of
Left err -> "No match: " ++ show err
Right _ -> "Found value"
I hope this answered your question!
Tags haskell | no comments
Posted by Daniel Lyons
Tue, 07 Aug 2007 05:33:00 GMT
Earlier today I thought I’d solidify my understanding of zippers, at least with lists. I’m pretty eluded by the concept for other data structures for right now but I’m liking the idea of it for lists (though not exactly seeing the whole point of it yet).
So I wrote up a quick implementation in Haskell included here:
module Listzip where
import List
data Zipper a = Zipper [a] a [a]
deriving (Show, Eq)
at n l = Zipper prefix item postfix where
(prefix,item,postfix) = doBreak n l []
doBreak 0 (x:xs) acc = (List.reverse acc, x, xs)
doBreak n (x:xs) acc = doBreak (n-1) xs (x:acc)
next (Zipper pre i (x:xs)) = Zipper (pre ++ [i]) x xs
prev (Zipper pre i post) = Zipper (init pre) (last pre) (i:post)
I realized it might be handy to have that be a functor so I can fmap it, so I added a couple more lines:
instance Functor Zipper where
fmap f (Zipper pre i post) = Zipper (fmap f pre) (f i) (fmap f post)
toList (Zipper pre i post) = pre ++ [i] ++ post
That’s cool, because now I can do things like this:
*Listzip> fmap (**2) $ at 4 [1..10]
Zipper [1.0,4.0,9.0,16.0] 25.0 [36.0,49.0,64.0,81.0,100.0]
Baird and I got to talking about things to do with hardware. Knowing what I know about the Warren Abstract Machine, it should be not particularly hard to make Prolog run on a pretty simple piece of hardware. All you need that’s weird is some kind of searchable “database” and a couple of stacks. So then I found myself coding up my zipper again in Prolog:
%% a general list zipper for prolog
zip_at(0, [H|T], Acc, zipper(RAcc, H, T)) :- !, reverse(Acc, RAcc).
zip_at(N, [H|T], Acc, Result) :-
N0 is N - 1,
zip_at(N0, T, [H|Acc], Result).
next(zipper(Left, Item, [H|Right]), zipper(Result, H, Right)) :-
append(Left, [Item], Result).
prev(zipper(Left, Item, Right), zipper(NewLeft, NewItem, [Item|Right])) :-
append(NewLeft, [NewItem], Left).
I think that’s pretty neat. When I was testing it I noticed something else though:
?- zip_at(1, [1,2,3,4,5], [], X), next(X, Y), prev(Y, X).
X = zipper([1], 2, [3, 4, 5]),
Y = zipper([1, 2], 3, [4, 5]) ;
No
?- zip_at(1, [1,2,3,4,5], [], X), prev(Y, X).
X = zipper([1], 2, [3, 4, 5]),
Y = zipper([1, 2], 3, [4, 5]) ;
No
?- zip_at(1, [1,2,3,4,5], [], X), prev(X, Y).
X = zipper([1], 2, [3, 4, 5]),
Y = zipper([], 1, [2, 3, 4, 5]) ;
This is the first time I’ve ever managed to successfully make Prolog code that can be instantiated on either variable! As you can see, if I reverse the variable order on prev, it gives me next’s behavior. Which means prev can be shortened to:
prev(X, Y) :- next(Y, X).
I thought those predicates looked pretty similar!
When Prolog works, it’s so cool!
Tags haskell, prolog | 1 comment
Posted by Daniel Lyons
Thu, 02 Aug 2007 06:58:00 GMT
To relax after fixing the house I coded this quickie in Haskell:
atlanticCityMethod :: Float -> Float -> Float -> Float
atlanticCityMethod x m u = (u*m)/n
where
iterates = take (fromEnum m) $ iterate (\x -> (2 - x) / (3 - 4*x)) x
nearZero u x = (-u)/2 < x && x < u/2
n = fromIntegral $ length $ filter (nearZero u) iterates
I think this pretty concisely captures the specification:
Here’s the slowest, most inefficient method known for computing p: Choose an arbitrary initial value x (real) and iterate the mapping x → (2-x)/(3-4x) for a total of M times. Count the number of iterates that fall within a small interval around zero. For example, let N denote the number of iterates that fall between -u/2 and +u/2 for some small u. Then the limiting value of the ratio uM/N is p (for sufficiently large M as u goes to zero).
Observations:
- This algorithm is so shitty I can’t tell if it’s actually working with reasonable input (
atlanticCityMethod 1029 1000000 0.00005 produced 3.125 for me, but what do I know?)
- Don’t like that lambda? Do the Arrow twist:
((2-) &&& ((4*) >>> (3-))) >>> (uncurry (/))
This works just as well, but is twice as long and much harder to read. I guess points-free sometimes comes at a cost.
- The auto-derived type was much stranger than the ones I guessed it would want. Haskell inferred this type signature:
atlanticCityMethod :: (Ord b, Fractional b, Enum b) => b -> b -> b -> b
- Haskell mode’s indentation is really smart, but it still pisses me off by choosing the inner-most indentation by default. I think it would be better if it chose the previous level of indentation by default. Maybe there’s an easy way to do this, but I don’t know it.
- Want to see a screenshot of my Haskell with pretty lambdas?
- Incidentally, Justin Dressel pointed out that Haskell sometimes can work with Unicode input, at least according to the Haskell` page.
Tags emacs, haskell, pi | no comments
Posted by Daniel Lyons
Tue, 31 Jul 2007 21:41:00 GMT
Is anyone out there using Emacs these days? I want someone to be impressed by this.
I know it’s horrifyingly incorrect Haskell, but still, it shows off a neat trick you can set up with a little help from your friends. The source code is plain text, the editor is just replacing certain patterns with unicode as I type.
I’ve made a lot of progress but it’s still pissing me off a little bit. Maybe that goes away after you customize it some more.
It is pretty impressive that with abbrev-mode you can basically bind a function to typing some arbitrary characters.
Tags emacs, haskell, pretty | 1 comment
