Reasons to use Haskell as a Mathematician (2006) | Hacker News Reader

Reasons to use Haskell as a Mathematician (2006)

blog.sigfpe.com

93 pointscottonseed75 comments

I've slowly come to the opinion that laziness is not the best idea, even from a pure mathematical point of view. There are large mathematical benefits to using a strict language like SML. One important benefit to me is that strictness allows you to have an equality operation with a very strong mathematical guarantee, namely that the types for which equality can be automatically defined are precisely the types for which equality is decidable (always terminates). A lazy language throws that out the window. In a strict language you can define both a type of guaranteed-finite lists with decidable equality and a type of potentially-infinite streams, while in a lazy language you only have the latter.

I wrote about it in more detail here: http://slepnev.blogspot.ch/2014/06/is-laziness-wrong-for-equ...

But mathematics is non-strict. One can define functions that terminate when evaluated lazily but don't terminate when evaluated strictly. These kinds of functions are prevalent in mathematics.

Does your belief that "mathematics is non-strict" go as far as saying that the type of natural numbers:

    data Natural = Zero | Successor Natural

must include this member as well:

    omega :: Natural
    omega = Successor omega

    bool1 = (omega == Zero)            -- returns False
    bool2 = (omega == Successor Zero)  -- returns False
    bool3 = (omega == omega)           -- whoops, infinite loop

The moral is that some parts of mathematics may be lazy, but mathematical induction has gotta be strict. Since many functional programs rely on induction for proofs of termination, correctness and resource usage, that means they should be strict as well.

>Since many functional programs rely on induction for proofs of termination, correctness and resource usage, that means they should be strict as well.

Am I incorrect in thinking that any strict program proven to be correct and terminating is also correct as a lazy program?

Yeah, that's true for programs, i.e. things that accept no arguments. Lazy evaluation provably makes more programs terminate than any other evaluation strategy. But it's kind of misleading for functions that accept arguments, like numbers or lists. Most functions in a lazy language can fail to terminate, because the arguments could fail to terminate or could be non-standard entities like omega. So, for example, the statement "computing the length of a list always terminates" is true in a strict language but not in a lazy one.

In general, strict languages allow you to say more about termination and time/space complexity of functions than lazy languages. For example, the statement "computing the length of a list takes O(1) space" is true in a strict language, but in a lazy language it's difficult to say what the statement even means, and in most practical cases it's false. Computing length with either foldr and foldl uses at least O(n) space, and the usual advice is to use foldl', which has a strictness annotation. I think this should be alarming to anyone who recommends lazy evaluation as the right default.

In slightly more complicated cases, like sorting a list, there's no sensible way to assign a time or space complexity at all, because it depends on how the function is called and how much of the result is used by the caller. People sometimes claim that's an advantage of lazy languages, e.g. implementing quickselect in terms of quicksort and claiming that quickselect will only evaluate as much of quicksort as needed. I think that's a hack. We need to be able to reason about the time and space complexity of a program in terms of its parts, without relying on implementation details of the parts.

As someone who has used Haskell for math, I would comment that the standard prelude (Haskell's standard library) can be quite obnoxious to work with depending on what you are doing. When I use Haskell for math, I normally switch to the numeric-prelude [0].

[0] https://hackage.haskell.org/package/numeric-prelude

At least #2 on their list of issues is currently fixed in GHC 7.8

I'm currently porting a Numpy project into haskell as a self-improvement project, and it's been 69% great. But then I find some library that I have to implement from scratch when I just had it in python. That's a pretty big problem, and I'm willing to put up with it, but most people aren't.

A nice way to look at it: if you share what code you have had to reimplement, you're making it more than 69% great for the potential Haskellers that follow!

Would love to! But my employer probably wouldn't be so thrilled about it.

Just out of curiosity, what libraries were these?

Scipy optimization libraries primarily.

I've always wondered why computational mathematicians/physicists end up using MATLAB/FORTRAN instead of haskell or similar.

The author of the article gives a hint: "Haskell isn't very good at dealing with arrays." High performance numerical code typically involves mutating large arrays distributed over a grid of machines or processors. I talk about the question you ask a little more here:

http://arstechnica.com/science/2014/05/scientific-computings...

That just isn't true though. It might be true for the standard prelude, but there are very high performance options available. Not only that, there are great wrappers to the standard C/Fortran scientific libraries used by everyone.

I have written real time 3D reconstruction and SLAM algorithms in Haskell, so I have had to face this head on.

Because they're trying to do work with computers, rather than do research about computing. If the interestingness of the implementation doesn't matter and you just want results, go with MATLAB/FORTRAN/Numpy or whatever and a fast BLAS implementation. Mutable state everywhere, side effects everywhere, you got your results fast and can go finish your paper or your project or whatever.

Once you've learned Haskell, actually, you can be far more productive in it than most other languages. The only piece of your statement that I'll agree with is that Haskell doesn't really have any great numerical or scientific tooling (like Python).

As languages go, Haskell out paces (not just in elegance but pragmatism too) most of the mainstream imperative languages.

The tooling for scientific computing does need to catch up though.

Can the typechecker ensure that your matrices (constructed from files) have compatible dimensions to be multiplied together? No? None of the compilers I've tried are much good for numeric computing. Since the error-prone parts of writing your code are not made easier by the typechecker, a dynamic language works just as well and has much lower cognitive overhead.

Remember that scientists don't care about the quality of their code. In many cases, once the code is complete, it will only run once and then be thrown away. There is no maintenance. Things like technical debt don't exist.

And pragmatism? Haskell doesn't even have loops. Loops with mutable variables inside are a very intuitive way of thinking about things and often a better fit to a problem than recursion. Sure, you can use tail recursion (which is just ugly looping) instead, but you're adding unwanted cognitive overhead.

What I would like is a functional language with enclosed, sealed off loops. Syntactic sugar for tail recursion, basically, but Haskell isn't built with programmers in mind; it's built for CS researchers. Computer language researchers, more specifically.

> Can the typechecker ensure that your matrices have compatible dimensions to be multiplied together? No?

Yes. In fact this is one of the earliest examples [0] of what you can do with the ever more numerous extensions to Haskell's type system.

There are BLAS bindings [1] and several native linear-algebra libraries in Hackage [2] that enlist the type-checker to enforce shape constraints at compile time.

0. See McBride (2001), "Faking It": http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.22.2...

1. http://hackage.haskell.org/package/blas

2. Repa, for instance: http://hackage.haskell.org/package/repa, http://hackage.haskell.org/package/repa-algorithms

> Remember that scientists don't care about the quality of their code. In many cases, once the code is complete, it will only run once and then be thrown away. There is no maintenance. Things like technical debt don't exist.

The code is usually used once, but it’s modified and “improved” for the next paper. So you add a few new routines here and a few files to read or write there, ... And one day you have a 95 pages fortran 77 program (it’s does’t even follow the fortran 90 standard).

> Can the typechecker ensure that your matrices have compatible dimensions to be multiplied together?

In any dependently typed language, absolutely yes.

Except Haskell isn't dependently typed, right?

I can do it in C# for small matrices, by including the dimensions as type bindings (http://bling.codeplex.com), but that is not practical for larger matrices, nor would it work for matrices loaded from IO.

To the downvoters: are you claiming Haskell is dependently typed? If so, why isn't it used in http://hackage.haskell.org/package/matrix-0.2.1/docs/Data-Ma...? Or just one matrix data type that checks dimension lengths via the type system?

Actually Haskell does have some dependently typed features (and is being extended constantly). The reason it isn't used in that particular package is a mystery, except that a lot of these things are very new and Haskell is an evoloving ecosystem. That particular package simply may not have a release that uses all the latest GHC features.

Repa for instance does provide type errors based on dimensionality of matrices. This is a package on Hackage.

See http://www.haskell.org/haskellwiki/Numeric_Haskell:_A_Repa_T...

Dimensionality is easy, its the lengths of these dimensions that are hard. E.g. you can multiply n by k, k by m matrices to get an n by m matrix, but anything else is a type error. In Bling, I had Matrix<LN,LK> * Matrix<LK,LM> => Matrix<LN,LM>, where LN,LK,LM are type parameters up to around 10 (L0, L1, ..., L10, enough to do 3D graphics, mostly, but wouldn't work for HPC where lengths are much longer and diverse).

Looking at the linked page, extent isn't a part of a matrix's type signature, so it would be checked dynamically, correct?

> you can multiply n by k, k by m matrices to get an n by m matrix, but anything else is a type error.

This is exactly how Repa works, it uses a Peano encoding of the extent of dimensions to make invalid array operations inexpressible.

Ok. This isn't obvious at all by looking at the documentation, also since extent doesn't seem to appear in the type signature of a matrix instance.

Deleted comment

Ah, this is exactly the approach I took in C# (though with a small range of branded types to stand in for numbers). Thanks for clearing this up!

Sorry, I forgot to specify that I meant matrices you read at runtime, for example from a csv.

Haskell has a very neat interface for this, in that you build a special type which remembers the dimensions of a matrix as you build them, and then return either the result or a failure.

It's very simple to build a function which doesn't have to understand the possible dimension conflicts and lift it to work on this new type, returning an either (or a maybe, if there's only one failure mode) in place of a definite value.

It's also very simple to propagate such errors forward, so they'll short circuit a computation when you have non-matching matrices used in a calculation that's multiple steps.

In Haskell, I don't have to remember to write special functions which guard against this: I write functions that operate on the matrices and add the guarding at the very end. I can ensure that all my calls use the guarding functions, because they have a different type signature.

Trying to do this same thing in Python require that I remember to always use the guarded calls, and doesn't have as clean of an interface to create the guarded functions from standard functions.

What does it matter? No type-system will magically know ahead of time what the contents of the file will be before you run the program, but it can force you to do the appropriate checks when you do read it from the file.

> No type-system will magically know ahead of time what the contents of the file will be before you run the program.

Yes they can, it's known as 'type providers'. http://blogs.msdn.com/b/dsyme/archive/2013/01/30/twelve-type...

I believe you could enforce something like compatible dimensions in Haskell in a library, but I could be wrong. If not, I wonder if you could do it in idris.

Idris is a wonderful language but the tooling there is even more immature for numerical computing than Haskell.

> Can the typechecker ensure that your matrices (constructed from files) have compatible dimensions to be multiplied together?

It seems so

http://stackoverflow.com/questions/8332392/type-safe-matrix-...

> Once you've learned Haskell, actually, you can be far more productive in it than most other languages.

Not when you're doing mathematical research. You can write x86 machine code and the time spent programming is still completely dwarfed by the time spent doing math. Mathematics is full of renowned professors who write F77 by hunting and pecking with one finger. There's no reason for them to use anything "more productive" because they can already code far, far faster than they can think of what to code.

There are extreme outliers for whom this doesn't hold, but they are few and far between.

Once you've learned Haskell, actually, you can be far more productive in it than most other languages.

Productive in what sense and at what cost (in time, especially, but generally)? What benefit is there to learning Haskell when the existing "tooling" in FORTRAN77, C, or C++ is quite adequate for the purpose of research? I mean for the specific purpose of applying it in a research context; not the general sense (i.e. this isn't meant to question the worth learning something new in general).

> FORTRAN77, C, or C++

Some people also use Fortran 95/2003/2008.

I've been a mathematician programming in a variety of languages over the last 20 years, and I can say that if it "doesn't really have any great numerical or scientific tooling" then I won't even give it thought number one for doing computations.

And you know, that's totally fair. I'm not a mathematician so my perspective is limited only to producing production software. I'm simply relating my own experience in the hope that people will stop judging Haskell as a "research language" with little to no industrial value.

That's the funny thing about researchers, some seem extremely obstinate (I suppose in many ways that's a required attribute otherwise they might give up). I wonder if this is why we still have Fortran code around...

Once you learn how to play the piano, you can play wonderful pieces. But that takes years. It's not cost-effective if humming is just good enough.

Can you cite that ? Have you tried doing Numerical (or Symbolic) computation in Haskell ?

Look, asking people to cite opinions is a dumb way of having casual discussion.

If you need any more input from me to convince you to learn something new, then it's not worth my time or yours.

Like I said the tooling isn't as mature but the language enables me to produce results faster with fewer bugs that is much easier to maintain down the road.

The only numerical computing I've ever really programmed for was manipulation of time series data and some standard statistical methods.

I did it at first in Python with Pandas and numpy. Then moved to Haskell. The language was better but the tooling I had to shore up in places.

Take that if it's useful to you :)

Yeah, but with Haskell the code would look more like the actual equations you're working from and not an implementation of the equations (thinking like differential manifolds etc).

What does this mean? I've seen this before and I don't get what it means.

Look more like the actual equations? Can you give me a concrete example of Haskell code that solves a simple PDE?

How does matrix indexing look like in Haskell?

I found this by looking at the repa docs:

    mmMult  :: Monad m
         => Array U DIM2 Double
         -> Array U DIM2 Double
         -> m (Array U DIM2 Double)
    mmMult a b = sumP (Repa.zipWith (*) aRepl bRepl)
        where
          t     = transpose2D b
          aRepl = extend (Z :.All :.colsB :.All) a
          bRepl = extend (Z :.rowsA :.All :.All) t
          (Z :.colsA :.rowsA) = extent a
          (Z :.colsB :.rowsB) = extent b

http://www.haskell.org/haskellwiki/Numeric_Haskell:_A_Repa_T...

I meant, just accessing a matrix element i,j which in many languages happens by m(i,j) or m[i,j].

The literal answer to your question is

   readIOArray m (i,j)

But that is misleading because there are two kinds of arrays in Haskell, and the kind (namely, mutable) I used in my literal answer is the less common kind. In fact, it is so uncommon and so contrary to the spirit of Haskell that the language implementations do not take the trouble to make it fast. Last time I played with the Glasgow Haskell Compiler, for example, a related operation (readIORef) was over 100 times slower than its counterpart in C.

Parenthetically, because you need to use "a monad" to perform any sort of mutable operation in Haskell, the translation of

   m[i,j] := m[j,i]

into Haskell is not

   writeIOArray m (i,j) (readIOArray m (j,i))

like someone unfamiliar with monadic style might think, but rather

   readIOArray m (j,i) >>= writeIOArray m (i,j)

or equivalently

   do
      element <- readIOArray m (j,i)
      writeIOArray m (i,j) element

But that is a side issue. The central fact is that even though it is technically possible, it is considered bad style in Haskell to access or update individual array elements.

> The central fact is that even though it is technically possible, it is considered bad style in Haskell to access or update individual array elements.

And another reason why Haskell will not fair well. A lot of numerical mathematics is linear algebra which involves, almost exclusively, updating array elements.

I'm sure Haskell is good at some things but for many of the types of problems that numerical analysts face Haskell's paradigm just doesn't make sense. Especially when we have languages like Fortran/Matlab which were explicitly designed for computational mathematics.

Yeah, I was just thinking that as /u/warfangle/ said that

> with Haskell the code would look more like the actual equations you're working from

so at least in matrix algorithms, and finite difference methods for partial differential equations, the textbooks usually explain the algorithms using a notation that refers to matrix elements. So in these cases, an imperative implementation would be close to the math textbook representation, and the Haskell code would not.

I believe the Haskell way of doing numerical things would be thinking in terms of what you're trying to do rather than "Step x is get the value from [i,j] of the matrice". I could be very wrong, but for general programming I had to stop thinking in terms of accessing specific elements of an array to write idiomatic Haskell.

I one who tried it but ended up having to port to python to use a sparse linear system solver.

The state of the art in numerical computing really isn't to the point we can work from equations because things like sparsity and which solver you use (Algebraic Multi Grid? Conjugate Gradient Descent? ...) matter a lot and the established algorithms and implementations are really fast and well tested.

FORTRAN = decades of battle tested (also not-understood-so-much-anymore), performant code.

Matlab toolboxes and Fortran libraries.

Well... modern Fortran has pure procedures, at the least.

there are a bunch of languages mathematicians should know, haskell is one of them, so is prolog, lisp, APL, FORTRAN, and C. They all have their advantages, and you just have to know which one will give you an edge in your problem domain.

I want to hear from people who do math all day every day, and not just programming language theory. I want to hear about algebraic geometers, topolgists, ring theorists using Haskell and saying "Yeah this is really helping me in my work."

As a mathematician I'll certainly endorse a number of the points in the linked post. Because what they mean is that it can be very quick to translate mathematics into code. Maybe it won't run fast or be understandable by anyone else, but I can express complicated ideas (relatively) compactly and quickly and get something working without huge amounts of tedium.

Can you give me some examples? What do you use Haskell to do? I am also a mathematician so I can handle the jargon.

Mostly not large things. (Or at least, mostly not things that are large in Haskell.) An example recently -- I wanted to consider, let's say you have two finite rooted trees, S and T, with T having more vertices; and you you have a bijection f from the set of subtrees of S (subtrees have to have the same root as the original) to the set of subtrees of T, with certain restrictions on it; and then to f you associate a system of linear equations; and if the solution set to this system isn't contained a hyperplane aligned with the axes, then (if there exists an f for which this is true) I'll say "S interferes with T". And then I want to check for various T whether there is any smaller S that interferes with them.

Basically without something like Haskell, or at least something like Haskell-or-ML (I didn't need typeclasses and I don't know how much I needed laziness), it seems like that would have been a complete mess.

Of course, the above example is perhaps not the best as it meant I had to [either look up a library, or, what I actually did] implement row-reduction in Haskell, obviously not a great language for it! But ultimately it wasn't too terrible. And the rest as I've said would have been terrible in another language.

Shamelessly off-topic, but I can tell the author is a legit pure mathematician:

(1) Haskell is Functional

(2) Haskell Insulates You

(3) Haskell Performs Well

[...]

(3) Haskell is Declarative

Not being ironic, by the way. From experience, often I can tell pure vs applied mathematicians by how hilariously bad/absent-minded they can be at basic arithmetic/algebraic manipulations.

Same for theoretical- vs systems-oriented CS people, I've found --almost as if being a horrible programmer somehow gives you academic hipster cred.

(EDIT - To clarify: I mean CS academics in grad school, not CS professionals in industry. Also it's just a silly anecdote only marginally correlated with reality: no offense intended to anyone.)

He was a pure mathematician at the time this was written. Now he works for Google, IIRC on self-driving cars:

http://www.knowthecosmos.com/destember/destember-experiment-...

He also won an Oscar this year, his second total:

http://www.imdb.com/name/nm0685004/awards

Nice to know, if an oscar-winning pure mathematician working on science-fiction projects found difficult to learn Haskell, I can save myself the trouble.

If that's your goal. There are some people who do things because they are difficult, because whatever activity is most difficult is probably the most mind-expanding.

Inheriting off-topicness, while that stereotype does apply to most mathematicians, a large number of the CS theory people I've worked/TA'd with were actually pretty good programmers, and a few had even taught multiple years of our intro systems course. Of course this is just one school, but I think computer science as a field is still young enough that someone can be an expert in one area and still be reasonably fluent in other areas.

Don't think the last point is particularly true either: being a good programmer is valuable even for theoretical CS. Point in case, recently saw the work leading to a paper on SDD solvers: there was a ton of programming and exploration (albeit in Mathematica/Matlab) that led to the final paper. Also, people working on parallel stuff these days (even the theory guys) usually publish CILK/MPI along with the paper. It's great when you can do both :)

Yes: That's definitely the way it should be! I agree 100% that CS is still young and cohesive enough for dedicated people to achieve both breadth and depth, which perhaps means "grand" single-person revolutionary breakthroughs can still be achieved: Karp made a similar point during one of the Turing centenary talks (*An Algorithmic View of the Universe [1,2]), positing that the field is not yet specialized enough to prevent an Alan Turing-like figure today to have a comprehensive view of the state-of-art of the discipline (!).

[1] http://dl.acm.org/citation.cfm?id=2322176.2322189

[2] http://www.youtube.com/watch?v=f6df3s3x3zo#t=56m25s

It is technically impossible to be a good 'CS People' and simultaneously be a 'horrible programmer'. It seems that what you are referring to are people who know basic CS concepts and even know the basic features of a language or two but do not have a 'Hacker' mindset. This does not make them a 'horrible programmer' -- just as a hacker who comes up with 'tricks', without actually understanding that the things he 'created' were already discovered in some 70s CS paper, is not a 'horrible Computer Scientist'. It's not a sufficient method to describe a person's strengths and weaknesses.

Sorry I wasn't clear: by 'CS people' I meant to refer to CS academics in graduate school (professors, post-docs, grad students), not CS professionals in industry --admittedly a sign of insularity, I recognize.

And what I meant is that, anecdotally, academics working on CS theory (eg theory of computation, computational learning theory) are more likely than not to unmistakeably be what I think everyone on HN would agree to call point-blank "horrible programmers": no use of version control, no tests, little concern for organization/modularity/maintainability, etc. And in part it makes sense since they don't have to hack nearly as much as systems-type CS academics --in many ways their work is closer to pure mathematics than engineering/applied math. That's all.

In all just a silly anecdote, although with a kernel of truth. See for instance Scott Aaronson's joke comments about his programming abilities [1]:

On the spectrum of computer science, I'm about as theoretical as you can get. One way to put it is that I got through CS grad school at Berkeley without really learning any programming language other than QBASIC (!).

[1] http://www.scottaaronson.com/blog/?p=266

This wouldn't be at all surprising if people realized that the job of academic computer scientists is not to program (just like the job of an academic mathematician is not to perform basic arithmetic.)

First -- I don't think it's wise or useful to judge Ph.D.'s by the same standards as industrial developers. Or vice versa. Consider the corresponding criticism of industry: "have you meet some of these jokers in industry? Most of them couldn't pass the qualifiers even after like 5 years doing CS full time. WTH?! It's almost like like haven't learned much new theory or math since graduating from undergrad or something...")

Second -- and this is purely based upon my personal experience (perhaps we have worked with people in radically different departments or research areas) -- what you say is simply not true in most cases.

I've worked with a lot of theory people, and did not encounter any really bad programmers.

Your specific criticisms:

1. version control. Everyone uses it for everything. Even and especially paper writing. If your experience is that theory phds don't use version control, then I would say your department is/was abnormal (or else we've observed people in very different parts of theory, I suppose).

But also, in many cases, using VCS is more religious than practical. Academic projects are often <10kloc single dev projects. It's more of a useful additional backup mechanism than actually necessary.

2. Testing. If the paper contains a full spec and correctness proof for the implementation (e.g. inference rules, automata, algorithm in terms of some mathematical object) then the point of the implementation is really just transliteration. The space for potential bugs is still there, but the bugs are very different from typical bugs (which, imho, are most often due to poor/vague or even completely absent specification). You simply need fewer unit tests when you know that precisely the thing you are implementing is correct, and just want to make sure you copied things down correctly.

3. The code is often well-written. When it is not, two problems are most common:

a. no comments! Okay, but of course there is a 20 page paper explaining the core idea. And also it's a protoype.

b. Bad structure/poor abstractions. Again, most prototypes don't need to be maintainable. If the core idea gets big and important, it probably makes sense to reimplement as part of a new research agenda anyways (e.g. for performance reasons, or because of unforeseen extensions due to scientific advances, etc). Also, in some cases, the correct way to organize a piece of academic software is highly non-obvious. Organizing your code is much easier when it's a completely solved technical problem in search for new social applications (yet another web app) than when it's a completely new technical idea.

So, basically, you think that there are exactly 0 CS professors who are horrible programmers?

How can your comment completely disregard the entirety of my actual conclusion?

>It's not a sufficient method to describe a person's strengths and weaknesses.

So, there should be if your classifications are correct. You are assuming that 'CS Professor' is equatable to 'good CS People'. But, my classification may not be so rigid.

EDIT: You also still have not defined what it means to be a 'Good Programmer' vs. a 'Horrible' one.

I don't think you know enough pure mathematicians.

You are probably right --I haven't been spending much time of late with people from my own department. :)

Reply on news.ycombinator.com