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 module
s 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 toEndlessList
--- think ofEndlessList
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, likedata 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 constructorCons
of the respective type. All in all we are left with two things: a typeEndlessList a
and a function namedCons
ofa -> EndlessList a -> EndlessList a
(that's how Haskell writes function types. For example, a function that adds two numbers together might have typeInt -> 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 n
th 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 Integer
s. 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 show
n, 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
Top comments (2)
IMO, you don't need $ for printOfAll, since
is enough.
You're right; this is much cleaner. I'm going to go back and edit the post now.