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
module Main where
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:
datastatements define new types
EndlessListwill be the name of our new "type constructor"
awill be an argument to
EndlessList--- think of
EndlessListas a function from one argument which returns a type
=separates the type constructor (
EndlessList a) from the "value constructor"
Cons a (EndlessList a)
Consis 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
(EndlessList a)denote two arguments to the value constructor
Consof the respective type. All in all we are left with two things: a type
EndlessList aand a function named
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 does exactly what you want it to: repeats
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.
next will each be of type
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
naturalNumbers is an
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
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
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
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
putStrLn is an
IO action which prints a
show formats a value as a
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.
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