Category Archives: Programming

Lazy big-O and Haskell Answers

Programming

First, Evan has a host of interesting articles about Haskell, and I found his lazy big-O article particulary interesting.

Next, Eric Warmenhoven has recently taken up Haskell and posted some Haskell questions on his blog. Eric, here are some answers for you.

First, regarding shared libraries. While Haskell can be compiled to machine code, and GHC is a popular way to do that, a standard C way of representing information about a library (.h and .so files) is not really rich enough for Haskell. Consider, for instance, that functions may accept arguments of a wide range of types (or even things such as lists of any type). Haskell also performs type checking, and thus must know the type of arguments a function expects, as well as its return type, at compile time. So you do not generally compile Haskell code directly to .so files, but rather use the compiler’s module or package support to do that. See Cabal for more information on packages. Through the FFI (Foreign Function Interface), it is possible to both call into C and be called from C with Haskell code, if that’s where you want to go. It is actually easier in Haskell than in any other high-level language I’ve dealt with before.

Regarding circular module deps — I’ve never used them and can’t really comment. I can say, though, that the .boot files are internal files created by GHC.

Regarding practical stuff in tutorials — I share your complaint there. I have found a few that are better than the others: Yet Another Haskell Tutorial, and Haskell: The Craft of Functional Programming, 2nd ed., by Simon Thompson. Several of us are working intermittently on a project called Haskell V8 — take a look and darcs send me patches! I would say that Haskell’s I/O system is the most powerful I’ve seen in many ways — especially with regard to laziness — and in the upcoming GHC 6.6 release, it will be both lazy *and* blazingly fast. Very nice.

There isn’t much Debian-specific documentation, but there is a draft policy and a mailing list (link to it is in the policy doc).

Hope this helps!

Announcing HSH, the Haskell Shell

Programming

Following the “release early, release often” motto, I am happy to announce version 0.1.0 of HSH, the Haskell shell.

You may obtain it with:

darcs get --tag 0.1.0 http://darcs.complete.org/hsh

Things are still very rough in many ways, but this version already lets you:

  • Run commands
  • Pipe things between commands
  • Pipe command input/output into and out of pure Haskell functions
  • Pure Haskell functions are as much a first-class citizen as is grep or cat

Here is an example session: (some lines wrapped for readability)

$ ghci -fglasgow-exts HSH

*HSH> run $ ("ls", ["."])
COPYING    HSH        HSH.hs    TODO    announcements  testsrc
COPYRIGHT  HSH.cabal  Makefile  _darcs  test.hs

*HSH> run $ ("ls", ["-l"]) -|- ("wc", ["-l"])
12

*HSH> :m +Text.Printf
*HSH Text.Printf> let countLines = (zipWith (\i line -> printf "%-5d %s" i line) 
       [(1::Int)..])::([String] -> [String])

*HSH Text.Printf> run $ ("ls", ["-l"]) -|- countLines -|- ("grep", ["hs$"])
6     -rw-r--r-- 1 jgoerzen jgoerzen  1285 Jun  6 09:43 HSH.hs
11    -rw-r--r-- 1 jgoerzen jgoerzen   565 Jun  6 09:43 test.hs

*HSH Text.Printf> :m +Data.List
*HSH Text.Printf Data.List> run $ ("ls", ["-l"]) -|- countLines -|- 
         filter (isSuffixOf "hs")
6     -rw-r--r-- 1 jgoerzen jgoerzen  1285 Jun  6 09:43 HSH.hs
11    -rw-r--r-- 1 jgoerzen jgoerzen   565 Jun  6 09:43 test.hs

*HSH Text.Printf Data.List> run $ ("ls", ["-l"]) -|- countLines -|- filter (isSuffixOf "hs") 
       -|- ("tr", ["a-z", "A-Z"])
6     -RW-R--R-- 1 JGOERZEN JGOERZEN  1285 JUN  6 09:43 HSH.HS
11    -RW-R--R-- 1 JGOERZEN JGOERZEN   565 JUN  6 09:43 TEST.HS

*HSH Text.Printf Data.List> let generator = \(_::String) -> unlines . map show $ [1..20]
*HSH Text.Printf Data.List> generator ""
"1\n2\n3\n4\n5\n6\n7\n8\n9\n10\n11\n12\n13\n14\n15\n16\n17\n18\n19\n20\n"
*HSH Text.Printf Data.List> run $ generator -|- ("grep", ["1"])
1
10
11
12
13
14
15
16
17
18
19

Future versions will likely simplify syntax to make it easier to write scripts and introduce a sh to hsh converter. I also plan to add pure Haskell tools for some common shell-ish things that one could do in Haskell.

Haskell #1 in the Shootout

Programming

Wow. Some Haskell hackers have started paying a small bit of attention to the Great Computer Language Shootout site, and the results are impressive.

Haskell now takes first place in the lines of code competition. In the CPU time competition, Haskell is also doing quite respectably: it beats out OCaml by a small margin, and defeats Java, C++, Python, Perl, Erlang, Ruby, Mono, Tcl, etc. by significant margins.

These links are all using the Shootout default weightings for individual tests.

The only downside to the Shootout is that the programs — for all languages — are not really idomatic and don’t show off a language’s natural beauty. Sounds like it’s time to gather up some Haskell hackers to rally around the PLEAC effort as well.

Some nice code: libarchive

Programming

Yesterday, while looking for information on the format of tar files, I discovered libarchive, which is part of FreeBSD. libarchive and read about 5 different tar formats, 4 different cpio formats, zip, and ISO images, and supports gzip and bzip2. It can also write 2 different tar formats plus cpio and shar. Very nice.

Oh, and its tar.5 is the best reference on the tar format I’ve seen.

I’ve packaged up libarchive and bsdtar (the default tar on FreeBSD, which is built using libarchive) for Debian.

Perl, Powered By Haskell

Programming

Autrijus Tang is well-known for developing the first working Perl 6 interpreter, Pugs. Pugs is written in Haskell, my new favorite language. Perl.com has an interview with Autrijus, and page 2 of that interview gets particularly interesting. Here are some quotes from Autrijus:

Haskell . . . is faster than C++, more concise than Perl, more regular than Python, more flexible than Ruby, more typeful than C#, more robust than Java, and has absolutely nothing in common with PHP.

(If it has nothing in common with PHP, it must be great, right?)

Haskell is a pure functional language optimised for conciseness and clarity. It handles infinite data structures natively, and offers rich types and function abstractions that give Haskell programs a strong declarative flavor–the entire Pugs compiler and runtime is under 3000 lines of code.

Most languages require you to pay a “language tax”: code that does nothing with the main algorithm, placed there only to make the computer happy. [Java, anyone? — jgoerzen]

On the other end of spectrum, we often shy away from abstracting huge legacy code because we are afraid of breaking the complex interplay of flow control and global and mutable variables. Besides, the paths leading to common targets of refactoring–those Design Patterns–are often non-obvious.

Because Haskell makes all side effects explicit, code can be refactored in a safe and automatic way. Indeed, you can ask a bot on to turn programs to its most abstracted form for you.

Go check out the interview (page 2) for more, including a demo program that Autrijus wrote to show off Haskell.

Thanks to metaperl for the link.

Recent Coding

Programming

I’ve been busy coding lately. Here’s what I’m up to:

  • A Haskell binding to OpenLDAP. I’ve got the groundwork laid (I can connect and bind to a LDAP server by now). Next up: searching. After that, the rest should be fairly easy. ETA about 1 week. Development sources: fetch with darcs get http://darcs.complete.org/ldap-haskell. See also the related haskell-cafe thread.
  • Packaged up and uploaded hsffig to Debian. hsffig will parse C .h files and automatically generate Haskell bindings and prototypes for them. It requires zero human assistance. Very, very, very cool. A little rough yet, but this is exciting stuff. Check out the source package with darcs get http://darcs.complete.org/debian/hsffig.
  • Packaged up and uploaded libcdk5, the latest version of the Curses Development Kit (CDK). CDK is a much more high-level tool than ncurses, and lets you say things like “show a dialog box” instead of “draw a border from 3,20 to 3,70 and make it gray”. Check out Debian source package with darcs get http://darcs.complete.org/debian/libcdk5.
  • Updated my MissingH Haskell library so it now builds and runs properly on Windows platforms. I now remember how much I detest them. (Urgh, drive letters complicate path manipulation in millions of annoying ways.)

Looking For Text-Mode Widget Library

Programming

I’m looking for a text-mode widget library. Something that has dialog-boxes, etc. for text-mode (curses/console/xterm) programs.

I’ve looked at these so far:

  • tvision/tv/turbovision: Questionable license situation, unsuitable for Debian
  • CDK: Fine on *nix, but unusable on Windows
  • CTK: Not maintained for several years, looks dead, not as good as CDK anyway

I want something with a C library, that supports *nix and Windows, and has support for things like menus, dialog boxes, etc. Any suggestions?