WIP: A Haskell Prelude from the Groundish Up Part One: Lists and Numbers

Started November 3, 2022
Published March 3, 2024
Last updated March 3, 2024 (commentary)

The blog post you are about to see is a product of its time#

This is old and dumb. I had fun doing it, so I don’t regret it, but it was pretty silly of me to do this when I really didn’t know much Haskell (I know less now, though :P). I will keep myself from adding commentary (other than this) because that would get old quick. Also, the original thing already has a bunch of commentary FSR.

Why#

This is a purely educational exercise, I have no real qualms with the standard Haskell prelude. And, even if I did, this is clearly not a reasonable replacement. A recursive data type for something as foundational as integers, which is exactly what we’re going to do in this article, is asinine for something that is used so often by so many programs. The optimization of the standard prelude, counterintuitively, is exactly my motivation for making this in the first place. I want a reference for a wide variety of foundational functional programming concepts; compiler-specific, somewhat messy optimizations while, again, beneficial for Haskell as a language, are simply antithetical to that purpose.

How#

I’m not going to pretend I’m a programming expert, or a functional programming expert, or a Haskell expert, or a math expert, or that I’m at least proficient at Haskell, or that

I’ve banged my head against the wall on this specific problem enough that I feel confident enough to go even further.

If you’re wondering how you can follow along, all of the code needed will be shown in each post, or you can follow [this link](INSERT LINK TO git.pyrope.net/mbk/hgpu-1 HERE) to see all the code for this chapter in one place.

Main#

Our main isn’t going to actually do anything per se, but it will serve as a useful example for how we’re doing things. I like having a single GHCi session with a file :l-oaded that I :r-eload when I make a change. By having a main file, we only need to load one file to mess with all of our stuff!

Let’s dive in headfirst:

import qualified Prelude

Now load that and try typing some numbers:[2]

ƛ 1 + 2

<interactive>:10:3: error:
    • Variable not in scope: (+) :: t0 -> t1 -> t
    • Perhaps you meant ‘Prelude.+’ (imported from Prelude)

This shows us both the depth of the prelude and how we can cheat if[3] we need to. If we really, really need to access a prelude function we can use the qualified form. We shouldn’t need to, but I may use it for demonstration purposes.

Lists#

You might think that lists would be more complicated than numbers, but the methods I’m planning to use actually make lists easier than numbers! Now technically we could just use the normal Haskell Ints, they aren’t even part of the prelude, but that’s lame and uninteresting. That really is my actual reason, but a better reason is that Ints are just too closely bound to the specifics of the compiler.[4]

Let’s create List.hs and bear witness to the awesome and mighty first fruit of this simple main method:

-- Main.hs
import List

-- List.hs
module List where

Incredible. Inimitable. Phenomenal. All jokes aside, being able to :r-eload to load the new file is convenient.

Now, we truly begin:

import qualified Prelude

data List a = Cons a (List a)
            | Nil
              deriving (Prelude.Show)

Uh oh, our first cheat came earlier than I expected. This one is just pragmatic though, telling GHCi to use some custom Show instance would be annoying if not impossible. We’ll do the same when we make a much better Show implementation in a bit.

We can Construct our first list by hand:

ƛ Cons 4 (Cons 1 (Cons 3 Nil))
Cons 4 (Cons 1 (Cons 3 Nil))

This is a pain though, so let’s make our own version of the : operator.[5]

It’s really not complicated, as it’s just a convenience:

(-:) :: a -> List a -> List a
a -: as = Cons a as

infixr 5 -:

Note the infixr 5 -:, this lets us chain it in a nice way:[6]

ƛ 1 -: 2 -: 3 -: Nil
Cons 1 (Cons 2 (Cons 3 Nil))

Much nicer, but let’s also add a method to convert to and from lists for convenience sake:[7]

fromList :: [a] -> List a
fromList []     = Nil
fromList (x:xs) = x -: fromList xs

toList :: List a -> [a]
toList Nil         = []
toList (Cons x xs) = x : toList xs

Ah, multiple equations make recursion so much more approachable. Lovely. We can check that these are the inverse of each other:

ƛ fromList [1, 2, 3]
Cons 1 (Cons 2 (Cons 3 Nil))
ƛ toList it
[1,2,3]

Perfect.

Mapping is similarly obvious:

map :: (a -> b) -> List a -> List b
map f Nil         = Nil
map f (Cons x xs) = f x -: map f xs

Once again pattern matching shows its strength with recursion, especially with such an obvious base case. We can now make some truly horrific constructions with just a little bit of code:

ƛ let eugh n = n -: n -: n -: Nil
ƛ map eugh (map eugh (map eugh (Cons Nil Nil)))
Cons (Cons (Cons (Cons Nil (Cons Nil (Cons Nil Nil))) (Cons (Cons Nil (Cons Nil (Cons Nil Nil))) (Cons (Cons Nil (Cons Nil (Cons Nil Nil))) Nil))) (Cons (Cons (Cons Nil (Cons Nil (Cons Nil Nil))) (Cons (Cons Nil (Cons Nil (Cons Nil Nil))) (Cons (Cons Nil (Cons Nil (Cons Nil Nil))) Nil))) (Cons (Cons (Cons Nil (Cons Nil (Cons Nil Nil))) (Cons (Cons Nil (Cons Nil (Cons Nil Nil))) (Cons (Cons Nil (Cons Nil (Cons Nil Nil))) Nil))) Nil))) Nil

This does demonstrate the need for a nicer show instance, especially when compared to the standard list:

ƛ let meh n = n : n : n : []
ƛ Prelude.map meh (Prelude.map meh (Prelude.map meh [0]))
[[[[0,0,0],[0,0,0],[0,0,0]],[[0,0,0],[0,0,0],[0,0,0]],[[0,0,0],[0,0,0],[0,0,0]]]]

Much less intimidating.

How should we approach making a Show instance though? I hate to do this, but for the sake of brevity I’m explicitly importing show and Show:

With that out of the way, let’s start by observing that we can obviously only show a list of showable things, so that gives us the first part of our type signature:[8]

show :: Show a =>

Then this show function can take a list of Showables and, well, show them! Which leaves us with:

show :: Show a => List a -> String
show = undefined

But wait! Undefined is part of the standard prelude, and isn’t realistically definable in a nice way for us.

It is realistically, nay, trivially, definable in a very bad way for us though:

undefined = undefined

Oh. Oh no. This absolutely works. This is because of a massive, gaping hole in the Haskell type system, which, like most other gaping holes in foundational systems, doesn’t really matter at worst and is more often than not very useful.

SOMEWHAT PERTINENT DIGRESSION 1: The bottom type ⊥#

The bottom type is a type-level representation of a computation that fails or never ends.[10]

This is obviously applicable to real programs, sometimes things crash and burn, and it’s often even expected that a program won’t halt (think a server). Since it’s extremely difficult, if not impossible, to tell if something like that will happen,[11] bottom (⊥) is a member of every type.

Again, this isn’t a major problem in practice, and is often beneficial, but it does mean your precious Bools, for example, are, well.

END OF DIGRESSION#

Our undefined can never complete, as it recurses unconditionally, which means it’s ⊥ which means it’s every type, hooray!

Now we can sketch out our show implementation:[12]

showList :: Show a => List a -> String
showList xs = toList
           (concat
           (map fromList
           (intercalate ", "
           (map show xs))))

And the necessary (skeleton) definitions to make this actually compile:

intercalate :: a -> List a -> List a
intercalate = undefined

concat :: List (List a) -> List a
concat = undefined

Intercalate is a weird word obviously, but once you get used to it you realize it’s pretty much perfect. The dictionary definition tells you pretty much all you need to know, it just means putting something between other stuff. This is perfect for putting commas between everything. The most straightforward way that I’ve found to recreate intercalate[13] is to apply the classical functional programming 1337 strat of solving a simpler problem first, namely adding an element before every element of a list.

Here’s just that:[14]

appendBeforeAll :: a -> List a -> List a
appendBeforeAll a Nil         = Nil
appendBeforeAll a (Cons x xs) = a -: x -: appendBeforeAll a xs

This is definitely complex enough to warrant testing real quick:

ƛ appendBeforeAll 99 (fromList [1,2,3,4,5])
Cons 99 (Cons 1 (Cons 99 (Cons 2 (Cons 99 (Cons 3 (Cons 99 (Cons 4 (Cons 99 (Cons 5 Nil)))))))))
ƛ appendBeforeAll 99 Nil
Nil

Now that we’ve solved the easy problem, we can solve the hard problem! Isn’t functional programming great?

Evangelism aside, here’s the actual intercalate function:

intercalate a Nil         = Nil
intercalate a (Cons x xs) = x -: appendBeforeAll a xs

This is an ostensibly roundabout solution that is ultimately very intuitive (for me at least). It’s like making a sandwich from two pieces of bread that are on top of each other: You take off the top slice, put in the filling, then put the top slice back on. It would be much harder, albeit far from impossible, to do that without taking off the top slice of bread.[15]

Now, before we do concatenation of a List of Lists, we should figure out how to concatenate just two lists!

Let’s start with the easy case: Concatenating an empty list to, well, anything:[16]

(++) :: List a -> List a -> List a
Nil ++ bs = bs

What to do next is less obvious, so let’s go for another simple case even though it seems like it’s not really going anywhere:

(Cons a Nil) ++ bs = a -: bs

Adding a singleton[17] list to another list is just a roundabout cons operator! But wait, won’t our concatenation operator also eventually return Nil? That means we can reduce our definition to:[18]

(++) :: List a -> List a -> List a
Nil         ++ bs = bs
(Cons a as) ++ bs = a -: as ++ bs

infixr 5 ++

We quickly verify that it works:

ƛ (fromList [1,2,3]) ++ (fromList [4,5,6])
Cons 1 (Cons 2 (Cons 3 (Cons 4 (Cons 5 (Cons 6 Nil)))))
ƛ (fromList [1,2,3]) ++ Nil
Cons 1 (Cons 2 (Cons 3 Nil))

We could define concat now relatively easily, but, for an elegant definition, we need one last thing: foldr.

foldr turns a list of values into a single value by repeatedly applying a function to the head of the list and an accumulator. The type signature is a bit scary, but it’s not that bad:

foldr :: (a -> b -> b) -> b -> List a -> b

If there are no elements we apply f to the accumulator zero times, which just means returning the accumulator unchanged:

foldr f acc Nil = acc

Otherwise we apply foldr to the head of the list and the result of foldring the rest of the list:

foldr f acc (Cons x xs) = f x (foldr f acc xs)

And now for that sweet, sweet payoff:

concat :: List (List a) -> List a
concat = foldr (++) Nil

Ah, pointfree, how I’ve missed you.[19]

And with that the showList function actually works!

ƛ showList (fromList [1,2,3])
"1, 2, 3"
ƛ showList Nil
""

And, if we remove the deriving (Prelude.Show) line, we can make that how GHCi will print our lists from now on:

instance Show a => Show (List a) where
    show = showList

Although there’s a tiny problem:

ƛ fromList [1,2,3]
1, 2, 3
ƛ Nil

Showing nothing for Nil kind of makes sense, but is bound to cause problems. Let’s fix that by surrounding the list with some cool brackets: ⟦⟧

We’d might as well make a generic function just in case we want to use something like this later:

singleton :: a -> List a
singleton x = Cons x Nil

surround :: a -> a -> List a -> List a
surround l r xs = l -: xs ++ singleton r

We can add yet more nested parentheses:[20]

showList :: Show a => List a -> String
showList xs = toList
             (concat
             (map fromList
             (surround "⟦" "⟧"
             (intercalate ", "
             (map show xs)))))

With that, we’re done with our list for now. We’ll definitely add more, such as a length operator when we have our own integers, but this is pretty great.

ƛ fromList [1,2,3]
⟦1, 2, 3⟧
ƛ map (Prelude.+ 1) it
⟦2, 3, 4⟧
ƛ foldr (Prelude.+) 0 it
9
ƛ "remember this?"
"remember this?"
ƛ let eugh n = n -: n -: n -: Nil
ƛ map eugh (map eugh (map eugh (singleton 0)))
⟦⟦⟦⟦0, 0, 0⟧, ⟦0, 0, 0⟧, ⟦0, 0, 0⟧⟧, ⟦⟦0, 0, 0⟧, ⟦0, 0, 0⟧, ⟦0, 0, 0⟧⟧, ⟦⟦0, 0, 0⟧, ⟦0, 0, 0⟧, ⟦0, 0, 0⟧⟧⟧⟧

Wonderful.

Numbers#

Numbers are really hard.

More precisely, the way I’m going to be doing numbers is really hard. Numbers and math in programming languages normally have a very intimate relationship with the CPU because they are used so drastically often.

However, I’m not trying to make a functional[21] prelude, I’m trying to make a functional[22] one.

A Recursive Datatype for Numbers#

-- Main.hs
import Num

-- Num.hs
module Num where

import           Prelude (Show, String)
import qualified Prelude

data Int = Succ Int | Pred Int | Zero
    deriving (Show)

Now that I’ve ripped off the generic self-adhesive mini-bandage, let’s talk about the logic behind this… thing. Is using a recursi—No, of course not, this is of solely educational value.[24]

This datatype is a variation of Peano numbers that allow for signedness, which I feel has some nice benefits to both usability and ease of implementation.[25] Take the successor and predecessor functions:[26]

That’s right, Haskell datatypes make sneaky functions, so our successor and predecessor functions (henceforth shortened as succ and pred) are already defined!

ƛ Succ Zero
Succ Zero
ƛ Pred it
Pred (Succ Zero)

This nicely demonstrates a problem that we can nicely solve: redundancy. Negative one and positive one cancel out, leaving nothing behind:

reduce :: Int -> Int
reduce (Succ (Pred n)) = reduce n
reduce (Pred (Succ n)) = reduce n

And zero remains zero:

reduce n = n

This function as it is now will reduce our numbers, but not as much as they can be reduced. Take the following scenario:

Succ (Succ (Pred Zero))

There’s clearly some cancelling that can happen.[27] Unfortunately, because the beginning cannot be reduced, the function stops too early, missing out on some juicy (potentially infinite) reduction. This problem, like many other problems in life, can be solved with more recursion.[28]

We replace the reduce n = n with:

reduce (Pred n)        = Pred (reduce n)
reduce (Succ n)        = Succ (reduce n)
reduce Zero            = Zero

Which will eagerly chomp through the number, deftly handling the previous example, and even a slightly more pathological case:

ƛ Succ (Succ (Pred Zero))
Succ (Succ (Pred Zero))
ƛ reduce it
Succ Zero
ƛ Pred (Pred (Succ (Pred (Succ Zero))))
Pred (Pred (Succ (Pred (Succ Zero))))
ƛ reduce it
Pred Zero

These parentheses are getting annoying. Let’s make a fromInt method to reduce the hassle.