Haskell or Standard ML for beginners?

Question

I'm going to be teaching a lower-division course in discrete structures. I have selected the text book Discrete Structures, Logic, and Computability in part because it contains examples and concepts that are conducive to implementation with a functional programming language. (I also think it's a good textbook.)

I want an easy-to-understand FP language to illustrate DS concepts and that the students can use. Most students will have had only one or two semesters of programming in Java, at best. After looking at Scheme, Erlang, Haskell, Ocaml, and SML, I've settled on either Haskell or Standard ML. I'm leaning towards Haskell for the reasons outlined below, but I'd like the opinion of those who are active programmers in one or the other.

• Both Haskell and SML have pattern matching which makes describing a recursive algorithm a cinch.
• Haskell has nice list comprehensions that match nicely with the way such lists are expressed mathematically.
• Haskell has lazy evaluation. Great for constructing infinite lists using the list comprehension technique.
• SML has a truly interactive interpreter in which functions can be both defined and used. In Haskell, functions must be defined in a separate file and compiled before being used in the interactive shell.
• SML gives explicit confirmation of the function argument and return types in a syntax that's easy to understand. For example: val foo = fn : int * int -> int. Haskell's implicit curry syntax is a bit more obtuse, but not totally alien. For example: foo :: Int -> Int -> Int.
• Haskell uses arbitrary-precision integers by default. It's an external library in SML/NJ. And SML/NJ truncates output to 70 characters by default.
• Haskell's lambda syntax is subtle -- it uses a single backslash. SML is more explicit. Not sure if we'll ever need lambda in this class, though.

Essentially, SML and Haskell are roughly equivalent. I lean toward Haskell because I'm loving the list comprehensions and infinite lists in Haskell. But I'm worried that the extensive number of symbols in Haskell's compact syntax might cause students problems. From what I've gathered reading other posts on SO, Haskell is not recommended for beginners starting out with FP. But we're not going to be building full-fledged applications, just trying out simple algorithms.

What do you think?

---

Edit: Upon reading some of your great responses, I should clarify some of my bullet points.

In SML, there's no syntactic distinction between defining a function in the interpreter and defining it in an external file. Let's say you want to write the factorial function. In Haskell you can put this definition into a file and load it into GHCi:

fac 0 = 1
fac n = n * fac (n-1)

To me, that's clear, succinct, and matches the mathematical definition in the book. But if you want to write the function in GHCi directly, you have to use a different syntax:

let fac 0 = 1; fac n = n * fac (n-1)

When working with interactive interpreters, from a teaching perspective it's very, very handy when the student can use the same code in both a file and the command line.

By "explicit confirmation of the function," I meant that upon defining the function, SML right away tells you the name of the function, the types of the arguments, and the return type. In Haskell you have to use the :type command and then you get the somewhat confusing curry notation.

One more cool thing about Haskell -- this is a valid function definition:

fac 0 = 1
fac (n+1) = (n+1) * fac n

Again, this matches a definition they might find in the textbook. Can't do that in SML!

Answer 1

Much as I love Haskell, here are the reasons I would prefer SML for a class in discrete math and data structures (and most other beginners' classes):

• Time and space costs of Haskell programs can be very hard to predict, even for experts. SML offers much more limited ways to blow the machine.

• Syntax for function defintion in an interactive interpreter is identical to syntax used in a file, so you can cut and paste.

• Although operator overloading in SML is totally bogus, it is also simple. It's going to be hard to teach a whole class in Haskell without having to get into type classes.

• Student can debug using print. (Although, as a commenter points out, it is possible to get almost the same effect in Haskell using Debug.Trace.trace.)

• Infinite data structures blow people's minds. For beginners, you're better off having them define a stream type complete with ref cells and thunks, so they know how it works:

  datatype 'a thunk_contents = UNEVALUATED of unit -> 'a
                             | VALUE of 'a
  type 'a thunk = 'a thunk_contents ref
  val delay : (unit -> 'a) -> 'a thunk
  val force : 'a thunk -> 'a
  

  Now it's not magic any more, and you can go from here to streams (infinite lists).

• Layout is not as simple as in Python and can be confusing.

There are two places Haskell has an edge:

• In core Haskell you can write a function's type signature just before its definition. This is hugely helpful for students and other beginners. There just isn't a nice way to deal with type signatures in SML.

• Haskell has better concrete syntax. The Haskell syntax is a major improvement over ML syntax. I have written a short note about when to use parentheses in an ML program; this helps a little.

Finally, there is a sword that cuts both ways:

• Haskell code is pure by default, so your students are unlikely to stumble over impure constructs (IO monad, state monad) by accident. But by the same token, they can't print, and if you want to do I/O then at minumum you have to explain do notation, and return is confusing.

---

On a related topic, here is some advice for your course preparation: don't overlook Purely Functional Data Structures by Chris Okasaki. Even if you don't have your students use it, you will definitely want to have a copy.