Learning Haskell

In most programming languages, when looking at their source code, one can usually get some idea what it does even without being familiar with the language in any way. That’s not the case with Haskell. One must understand a lot of weird symbols like ::, :, ->, <-, =>, \, $, <$>, ~., !!, ++, `op`, >>, >>=, <*> to get the basics and a lot more to really understand the code. Additionally, keywords such as class or do have very different meanings from those common in other languages.

Even now, when I have learned the basics, I often look at some Haskell source code with “what the …?!”. One must be really proficient with the language to understand it easily.

The only clear syntactic construct in Haskell is if then else. Almost everything else is either cryptic or confusing. I have met only two similar examples so far: Perl, which is fortunately legacy these days (thanks to Python, I believe), and TeX, which is limited to typesetting.

Oh, and Haskell is yet another language with the annoying camelCase (AKA ICantReadThis) naming convention.

There is a reason why it took me about ten years to learn the basics of Haskell eventually. In many programming languages, one can start programming in them after two or three afternoons and then learn additional stuff incrementally. With Haskell, it’s a journey, it’s necessary to learn a lot before being able to write something meaningful. It’s not a matter of a couple of evenings, it requires a large initial free-time block, which is hard to get for such a thing once one is no longer a university student. Honestly, I’m not willing to take a week-long vacation to spend it solely learning Haskell.

The primary barrier is probably all the fancy algebraic stuff, which is huge and not so easy to explain and to understand, at the same time being necessary to do any I/O and other things. The cryptic syntax creates an additional hurdle, making it difficult to return to the language study after a longer break.

Languages not supporting optional and keyword arguments and with insufficient polymorphism naturally tend to encode type and other information into function names, leading to explosion of the number of function or even type names. It is ugliness by itself, but additionally good luck to any beginner looking into reference documentation and trying to grasp the most useful essentials from it.

The strong typing system looks very important for safety and it actually is. But it doesn’t seem to be that great in practice. It still doesn’t prevent a lot of bugs and, at least at the beginner level, I find struggling myself with it more than it would help me in non-Haskell environments. It will probably get better once I know and practice more, but at the moment it’s another learning barrier.

In Common Lisp, it’s possible to specify types but it’s not used that often. I usually specify types only for structure/class members and when being asked by the compiler to provide hints for optimization (typically discriminating between different numeric types). The compiler identifies some basic mistakes itself and most remaining type errors are caught quickly before the program starts being used. Although type errors are experienced from time to time in production code, they are not that frequent, because the code is usually clear enough to see easily what belongs where.

That said, this may not apply to other Lisp dialects. For example, I think Emacs Lisp would benefit from better compile time checks.

In Haskell, I specify types manually everywhere except for local definitions (let & where). I wouldn’t dare to omit them because things are often entangled and not very clear in Haskell code. But sometimes I meet situations where I exactly know what I’m doing but I find it hard to specify it to Haskell.

In my first non-trivial Haskell program, I wanted to use something similar to the following:

import Data.Function
import Data.List

class SomeState state where
  nextSteps :: state -> [step]
  applyStep :: state -> step -> state

class Step step where
  value :: step -> Int

step :: SomeState state => state -> state
step state = step' (nextSteps state) state
  where
    step' [] state = state
    step' steps state = applyStep state $ maximumBy (compare `on` value) steps

Here we want to use some general type (SomeState), together with another type (Step) that guarantees some properties (applicability of value function). This would work easily in common programming languages but not in Haskell. The intention is clear, there is no real bug in the program, but the type specifications are insufficient and the program doesn’t compile. A bit of disappointment after being proud about putting together the last line of the code above. Since Haskell, unlike other popular modern languages, even strongly typed, doesn’t support dynamic type dispatch, we have to improve the type specifications.

But how? Obviously, step must be specified. A naive straightforward approach doesn’t work:

class Step step => SomeState state step where
  nextSteps :: state -> [step]
  applyStep :: state -> step -> state

The compiler objects:

Too many parameters for class ‘SomeState’
(Enable MultiParamTypeClasses to allow multi-parameter classes)

Let’s follow the advice:

{-# LANGUAGE MultiParamTypeClasses #-}
…
class Step step => SomeState state step where
  nextSteps :: state -> [step]
  applyStep :: state -> step -> state
…
step :: SomeState state step => state -> state
…

Still not good:

Could not deduce (SomeState state step0)

The compiler knows that step satisfies Step. But searching the web discovers that

nextSteps :: state -> [step]

is meaningless, because it specifies that nextSteps should return all the possible types of step, which is of course not possible. Quite surprising to what we are used to in other programming languages. Desperation increases — as before, the intention is clear, the program is correct, but the type checker is still not happy. Further search discovers there is a thing called functional dependencies:

{-# LANGUAGE FunctionalDependencies #-}
{-# LANGUAGE MultiParamTypeClasses #-}
…
class Step step => SomeState state step | state -> step where

This works! Following the final suggestion of a linter to use ConstrainedClassMethods rather than MultiParamTypeClasses, we get the final, type correct, version:

{-# LANGUAGE ConstrainedClassMethods #-}
{-# LANGUAGE FunctionalDependencies #-}

import Data.Function
import Data.List

class Step step => SomeState state step | state -> step where
  nextSteps :: state -> [step]
  applyStep :: state -> step -> state

class Step step where
  value :: step -> Int

step :: (SomeState state step) => state -> state
step state = step' (nextSteps state) state
  where
    step' [] state = state
    step' steps state = applyStep state $ maximumBy (compare `on` value) steps

Most likely obvious for an experienced Haskell programmer, but hard to achieve for a beginner trying to write his first simple program. After hours of searching, reading, trying to understand and using three language extensions, the goal of specifying the obvious has been achieved.

Trying to use random numbers in Haskell illustrates some of the learning struggles mentioned above.

Let’s start with random numbers in Common Lisp. A search term such as „common lisp random“ leads to the corresponding documentation page, which explains that generating random numbers is as easy as expected. For instance

(random 10)

returns a random integer in the range from 0 to 9 or

(random 10.0)

returns a non-negative floating number less than 10.

Anytime, anywhere.

There is a little culprit in that some stuff around the random state is implementation dependent. This is because Common Lisp has an official ANSI standard and having an overspecified standard could cause trouble. The implementation specific things are clarified in the SBCL manual (SBCL is to Common Lisp what GHC is to Haskell). An important information there is that the initial random state is the same each time SBCL is started. This is good for testing and debugging but to have truly random numbers, one can make the random state random:

(setf *random-state* (make-random-state t))

And this is all one needs to know for 90% of non-cryptographic random number uses.

How about random numbers Haskell? Well, there is in principle no such thing as a mutable state, even less a global mutable state, in Haskell. Moreover, to obtain true random numbers, we need to access a system source of random information. That means we will have to use the Haskell state tracking machinery, including IO.

No surprise that it’s not a part of Prelude and is implemented as a special library. Uh, OK. Let’s look at its documentation. It starts with some examples using random number generators initialized with particular seeds. They are followed by many, many variations of functions and instances. Let’s try to dig out something from them.

First, we need a random number generator initialized from random data. A good candidate seems to be the global generator but according to the documentation, its use is discouraged in libraries. What to use instead? initStdGen looks like the function that we need.

Now, what to do with the generator? It’s necessary to track its changes when generating random numbers. This has some implications. There is a trouble to use an infinite list, one of the Haskell idioms, of random numbers because then we don’t have access to the generator anymore. Either the list is the only random source we need (not applicable if we need random values of different types) or we should use a separately initialized random number generator to create it. Neither of the options is attractive in my case, so let’s give up on infinite lists. Another implication is that the need of tracking together with the typical type pattern there, g -> (a, g), strongly suggests using monads, which is also addressed by the documentation.

initStdGen already wraps the generator in MonadIO but it’s beyond my current knowledge how to utilize it and the documentation is not helpful in this respect. It looks like the generator should be extracted and wrapped in another monad. The documentation mentions StateGenM, which should be good enough, but it seems it can be used basically only as:

main = do
  g <- initStdGen
  let (r, g) = runStateGen g randomM :: (Int, StdGen)
  …
  let (r, g) = runStateGen g randomM :: (Int, StdGen)
  …

Which brings no progress over using and tracking the generator directly, without monads. So let’s use another wrapper. newIOGenM is used most often in the documentation and it seems to be the least overkill from the available options although I don’t need to perform any IO when generating random numbers. But it apparently serves for tracking the generator state some way.

main = do
  g <- initStdGen >>= newIOGenM
  r <- randomM g :: IO Int
  …
  r <- randomM g :: IO Int
  …

This looks better. But I don’t want to generate random numbers in main, I want to pass the generator to another function. The case above looks interesting, it seems we have a truly mutable object g — could we pass it to a function simply as a mutable argument?!

randomList :: IOGenM StdGen -> Int -> [Int]

Apparently not, the functions applied on the generator return their values in monadic contexts. And since IOGenM should be bound to IO some way (possibly explaining the apparent mutability), let’s try to use IO as the context:

randomList :: IOGenM StdGen -> Int -> IO [Int]
randomList g n = do
  replicateM n $ randomM g

It works! We could also take the advantage of the “free slot” in IO to return a value from the function. Otherwise we had to use monad transformers, I’m afraid. So having IO there is not that useless in the end result.

It’s still needed to pass the generator as an extra argument, but in order to not complicate the things already complicated enough, let’s live with it.

The last remaining bit is that using Int may perhaps cause some expensive conversions and one of the Word types should be used instead, together with the corresponding functions.

This example illustrates how knowledgeable one must be before starting with basic programming in Haskell. And it’s only a summary, omitting all the blind alleys I met before reaching the given point.