WIP: A Haskell Prelude from the Groundish Up Part One: Lists and Numbers
https://cohost.org/pesterblog/post/4873144-wip-a-haskell-pre-l
an old, embarrasing permanent work in progress made with a comical lack of Haskell knowledge
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ƛ as my prompt because it’s like a derivative of Haskell’s logo1
ƛ 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 if3
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(x:xs)) being built in. ↩︎
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=> separates type constraints from the actual type of the function, so this essentially reads as “For all types a where a is Show” ↩︎
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 The endless gods, without time, without mortality are despicable in their boundless fortitude. They think themselves so far above the petty squabbles of us mortals, but it is merely the ultimate delusion. Throughout human history they have distorted us into thinking that mortality, death, finity is the ultimate depletion. But. But. They are wrong. They know they have wrong. They have always been wrong. Our reckoning with mortality may be somewhat present throughout our entire lives, but there is a single moment where we fully confront it. And then it is finished. Their reckoning with immortality, life, infinity will never, can never, end. And it grows. The endless finity of the universe, time and space, is not a game won by the last man standing.
We should be glad to die.
They envy us.
They would give anything to be us.
No matter how much they may say otherwise to us.
No matter how much they may say otherwise to themselves.
Because seeing the end of our own individual lives is so, so much better than seeing the end of All. ↩︎
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
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., we’ll get to that in the next chapter. ↩︎
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 intercalate13
Here’s just that:14(x:xs) is a very common to thing to see in Haskell, we’ve already seen it a couple times before in this post. I like to think of xs as excess :) ↩︎
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 singleton17Nil? 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 functional21
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
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.27Succs and subtract the number of Preds. ↩︎
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.