A simple Haskell program

Today, I'd like to share a short Haskell program which helped improve my understanding of the language, in the hopes that you all might learn a bit about it.

module Main where

data EndlessList a = Cons a (EndlessList a)

repeatForever :: a -> EndlessList a
repeatForever x = Cons x (repeatForever x)

genSequence :: a -> (a -> a) -> EndlessList a
genSequence init trans = Cons init (genSequence next trans)
    where next = trans init

naturalNumbers :: EndlessList Integer
naturalNumbers = genSequence 0 succ

printAllOf :: Show a => EndlessList a -> IO b
printAllOf (Cons a b) = putStrLn (show a) >> printAllOf b

main :: IO ()
main = printAllOf naturalNumbers

I know Haskell is pretty crazy, so I'll do my best to break this down in maximum detail. You can see how it compiles on Godbolt.

If you have ghc installed, you should be able to copy that source into a file named Main.hs, compile it with ghc Main.hs, and run it with ./Main. If you do, you'll see that it prints the natural numbers, starting from 0, and that it doesn't stop until you close the process with <ctrl>-c.

module Main where

Haskell's modules are pretty similar to Javascript's. The important thing is that any program that wants to build into an executable that we can run must define a module named Main which contains a value main :: IO (). I'll get to that down at the bottom of the source file.

data EndlessList a = Cons a (EndlessList a)

This line does several things. Reading from right to left:

• data statements define new types
• EndlessList will be the name of our new "type constructor"
• a will be an argument to EndlessList --- think of EndlessList as a function from one argument which returns a type
• = separates the type constructor (EndlessList a) from the "value constructor" Cons a (EndlessList a)
• Cons is the name of the "value constructor". It's common to give your type constructor and value constructor the same name, like data EndlessList a = EndlessList a (EndlessList a), but I felt that using different names added clarity to this example. The name "cons" comes from Lisp, and is used in functional programming to mean a pair
• a and (EndlessList a) denote two arguments to the value constructor Cons of the respective type. All in all we are left with two things: a type EndlessList a and a function named Cons of a -> EndlessList a -> EndlessList a (that's how Haskell writes function types. For example, a function that adds two numbers together might have type Int -> Int -> Int. The last type, not followed by an arrow, is the return type; all the others are arguments).

Right away you might notice something a little strange --- there's no way obvious way to construct, store, or operate on a value which must by definition be of infinite length. Despite this, ghc is able to run this code and it does immediately start printing numbers and not stop.

repeatForever :: a -> EndlessList a
repeatForever x = Cons x (repeatForever x)

This block defines a function repeatForever. The first line describes its type: for any type a, takes a value of type a and returns an EndlessList a. The second line tells how to compute it: call the constructor Cons first with x and then with the result of recursively calling repeatForever x.
This function is infinitely recursive, and if you tried to write it in Javascript/C/C++/Java, it would either crash or never terminate. In Haskell, though, where lazy evaluation is king, repeatForever x does exactly what you want it to: repeats x forever.

genSequence :: a -> (a -> a) -> EndlessList a
genSequence init trans = Cons init (genSequence next trans)
    where next = trans init

This function is like repeatForever, but way cooler. If you can read that type, good for you. init and next will each be of type a, and trans will be a function that takes an a and returns an a. This function creates a list whose first element is init and whose nth element is the result of applying trans to its (n - 1)st element.

Let's test it out with:

naturalNumbers :: EndlessList Integer
naturalNumbers = genSequence 0 succ

Here, naturalNumbers is an EndlessList of Integers. As we all know, the natural numbers start with 0, and the successor function succ will calculate the next natural number. We could replace succ with the anonymous function \n -> n + 1 for no change, but I think writing succ in my code is funny.

Haskell's hard-to-grok separation of concerns relegates input/output to a Monad called IO. Wiser people than I have tried and failed to describe what monads are and their implications, so I will not try.

Instead, I will tell you only that the type IO b means an input/output action which will result in a value of type b.

printAllOf :: Show a => EndlessList a -> IO b
printAllOf (Cons x y) = putStrLn (show x) >> printAllOf y

printAllOf will, for any type a that can be shown, take an EndlessList a and perform some IO action resulting in any arbitrary type b. Now, because our EndlessList will be infinite, this I/O action will never terminate, which is why it can claim to result in a value of any type b.

Instead of a recursive function, here we have a recursive IO action. The >> infix operator, like foo >> bar, denotes a sequence of operations. I read foo >> bar as "do foo and discard the result, then do bar". putStrLn is an IO action which prints a String to standard output, followed by a newline, similar to Javascript's console.log. show formats a value as a String, so putStrLn $ show x converts x into a String and then prints it to standard output.

main :: IO ()
main = printAllOf naturalNumbers

main, like in C/C++/Rust/Java/etc., is the "entry point" of a program. In Haskell, main is an IO action with no result, which means its type is IO (). We define ours as printing all of the natural numbers, which is what our program does.

Edit

The original code of this post used

printAllOf (Cons x y) = (putStrLn $ show x) >> printAllOf y

As per alirun's advice, I replaced that line with:

printAllOf (Cons x y) = putStrLn (show x) >> printAllOf y

Comments

[Junyoung Clare Jang]

IMO, you don't need $ for printOfAll, since

printOfAll (Cons x y) = putStrLn (show x) >> printAllOf y

is enough.

[Phoebe Goldman]

You're right; this is much cleaner. I'm going to go back and edit the post now.