by Eiko, 2024 eikochanowo@outlook.com
Welcome, wizards from different countries and regions! You will come to a magical realm guarded by the mysterious and ancient magic type mechanism, where the code is elegant, concise, and beautiful, and the kingdom is free of bugs. Here, wizards cast abstract and mysterious spells, and the magic type mechanism of the wand is checked first to reduce the risk of incorrect spells being cast.
We will explore the ancient and modern magical power of Haskell magic, learn the concept of pure functional programming and why it is important, and how to use the type system to ensure robust and reliable magic design. By learning Haskell magic, anyone’s magical power can be enhanced! In this magical realm, we will explore many unseen landscapes, such as curry, functor, monad, type variables, classes, type families, and many other magical skills and concepts.
Learning Haskell magic and type magic can help you:
Write more robust, bug-free programs and greatly reduce debugging time (I would say 50%~80% reduction in debug time)
Build complex programs from simple objects like playing with building blocks, making coding even more fun (Real fun and intellectually amusing)
Experience a different magical world, learn new knowledge, and enhance your mathematical and abstract thinking. These skills may have a profound and beneficial impact on you (even if you don’t use it).
Prerequisites?
Theoretically, there are no prerequisites. Familiarity with concepts such as programming, ~~mathematics, type theory, category theory~~ can be helpful, but not necessary. You can use this journey to enhance these skills! owo
Just need a curious and enthusiastic you!
Who is it suitable for?
Curious, exploratory, and thoughtful individuals
Those who enjoy mathematics and abstract concepts
Fans of building, constructing, and creating games or activities
~~Functional programming enthusiasts~~
~~PhD in Math or Computer Science~~
If you are interested, please give me some feedback!
Haskell is a functional programming language with a long history (at least 30 years) and is constantly evolving. It is closely related to the developments and research in computer science and mathematics in recent decades, such as type theory, category theory, and lambda calculus.
Functional programming means that functions are first-class citizens here, everything is a function, and you can pass complex functions as parameters to other functions.
The biggest difference is that in functional programming, most functions are pure, meaning they have no “side effects” (also known as denotational semantics). This means that a function, given the same input, will always produce the same output.
By default, all values are immutable and there are no “variables”. Computation is not achieved by modifying the value of a state, but rather by using a series of ~~spells~~ functions to transform input values into processed values, which are then combined using ~~spells~~ functions to produce the output.
Of course, this does not mean that Haskell cannot read external state or create mutable variables. In Haskell, you can manage sequential computation and side effects using Monads such as IO and ST, which allows you to separate the pure parts of your program from the parts that contain side effects. If you try to use IO in a pure function, it will not compile and the type system will reject your program. This allows you to know the behavior of a function just by looking at its type signature, without having to check the code itself.
getBirthday :: IO String -- the 'IO' in the type signature tells you this function is not pure
getBirthday = readFile "myBirthday.txt"
myBirthday :: String -- trying to deceive the type system by pretending a String with side effects is just a String
myBirthday = getBirthday -- will not compile, type error: 'IO String' is not 'String'Haskell has the following main advantages:
Type safety: Its powerful type system supports complex type-level programming. Types can help you with compile-time calculations, logical reasoning, and verifying that your program is correct in the aspects you specify, thus eliminating a large class of bugs. The power of type theory comes from mathematical logic, which guarantees that many errors will be caught at compile time. Therefore, as long as your program can compile, it is probably correct.
function :: Type Signature Appears Here
function = (... definition ...)For example:
f :: Int -> Int
f x = x + 1 -- f 5 will output 6
getBirthday :: IO String -- the 'IO' in the type signature tells you this function is not pure
getBirthday = readFile "myBirthday.txt"
myBirthday :: String -- trying to pass off a String with side effects as a pure String
myBirthday = getBirthday -- will not compile, type error: 'IO String' is not 'String'By defining newtypes for similar types to prevent type confusion, and using type parameters to further refine types, you can also use type signatures to specify the behavior of functions and ensure type safety.
{-# LANGUAGE DataKinds #-}
data Users = Alice | Bob | Eve
newtype UserId a = UserId String -- this is just a String, but with a tag parameter
newtype Address a = Address String -- this is just a String, but with a tag parameter
sendMessage :: (a :: Users) => UserId a -> Address a -> String -> IO ()
-- this signature enforce the user id and address have the same tag type
sendMessageBad :: String -> String -> String -> IO ()
-- compare it to this design, which is error-prone, what are these strings?
-- mixing the order of them still get you compiled, making bugs more likely.
aliceId :: UserId 'Alice
aliceId = UserId "775533"
aliceAddress :: Address 'Alice
aliceAddress = Address "1.1.1.1"
bobId :: UserId 'Bob
bobId = UserId "443399"
bobAddress :: Address 'Bob
bobAddress = Address "2.2.2.2"
sendMessage aliceId aliceAddress "hi!" -- fine
sendMessage aliceId bobAddress "hi!" -- type error: Alice is not Bob
sendMessage aliceAddress aliceId "hi!" -- type error: UserId is not AddressType Inference: Haskell’s Hindley-Milner Type System supports type inference, type variables, and other simple and useful features.
Type variables allow the same function to be used with multiple types.
Type inference allows you to often not need to annotate the types of functions, as the compiler can infer them from the context.
-- The last example can be rewritten as
f = (+1)
-- compiler will infer f :: (Num a) => a -> a
-- this function is usable for any number type a (implemented Num class) that supports (+)
-- Int, Integer, Double, these are all instances of Num classCategories and Abstraction: Haskell supports powerful abstract concepts from category theory, such as functors and monads. There are also abstract means such as classes and instances. These abstract concepts allow us to better perform abstract reasoning, increase code clarity, code reuse, and reduce code volume.
fmap :: (Functor f) => (a -> b) -> (f a -> f b) -- functor map of functor f, works for all functors
join :: (Monad m) => m (m a) -> m a -- the multiplication of monad
return :: (Monad m) => a -> m a -- the unitthere are plenty of examples of monads, like [ ], Maybe, Either s, IO, Parser, etc. example of using a functor:
fmap @[] @Int @Int :: (Int -> Int) -> ([Int] -> [Int]) (f = [], a = Int, b = Int)
fmap (+1) [1,2,3] = [2,3,4]
-- in fact, the specialization of fmap on lists is called map :: (a -> b) -> [a] -> [b]Highly Modular: One of the great advantages of functional programming’s Pure attribute is that the code is highly modular. It is easy to build complex programs by using existing modules like building blocks. This is because pureness ensures that the output of a function is solely determined by its input. In contrast, in general imperative programming, knowing the input of a function is not enough to fully determine its output. These functions may read the value of external states or modify global variables, causing changes in the behavior of other functions, making it less easy to combine them.
f :: Int -> String
g :: String -> Bool
h = g . f :: Int -> Bool
-- (.) is the function composition in mathematics, h is the function obtained by first applying f then apply g.Advanced type system support: type family, associated types, GADTs, data kind systems, these very powerful and flexible systems are hard to find elsewhere. These features make Haskell’s type system highly expressive and able to organize very complex concepts and behaviors. And it is constantly evolving: the latest research achievement, Linear Type extension, implemented in the past two years, is expected to achieve similar or even better resource safety control in Haskell as in Rust (of course, Linear Type has many other uses, and this area is still being explored).
type family AllEq (ts :: [Type]) :: Constraint where
AllEq '[] = ()
AllEq (t ': ts) = (Eq t, AllEq ts)Concise syntax: Haskell’s syntax is very concise, supporting very concise Pattern match, guards, do notation, etc. Writing functions usually takes only one or two lines. There are no curly braces { } or semicolons. This reduces the amount of code and allows you to see many functions on one page in your code editor.
quickSort [] = []
quickSort (x : xs) = quickSort [y | y <- xs, y <= x] ++ [x] ++ quickSort [y | y <- xs, y > x]
-- compiler will infer type quickSort :: (Ord a) => [a] -> [a]Lazy evaluation: Haskell defaults to a lazy evaluation model, which means that all values are only calculated when needed, which can avoid unnecessary calculations and reduce the amount of computation. Lazy evaluation also allows us to write infinite data structures such as infinite lists. With proper use, it can also implement mysterious computing models such as on-demand reading of files, streaming modification and writing, etc.
The list [a] is a lazy data structure, which allows us to define infinite lists ```Haskell infList = [1,2..]
take 5 infList = [1,2,3,4,5] – the evaluation stops here, will not loop forever Example: Define an infinite list composed of prime numbersHaskell allPrimes = filterPrimes [2..] :: [Integer] – an example of an infinite list of all primes where filterPrimes (p:ps) = p : filterPrimes [n | n <- ps, n mod p /= 0]
take 5 allPrimes = [2,3,5,7,11] – will not loop forever, it will only evalute the first 5 elements ```
For example, in Haskell, the operators || and && are lazy for the second variable. This means that if the value of the first variable is True (False for &&), the second variable will not be evaluated.
True || (whatever this is, it will not be evaluated) = True
False && (whatever this is, it will not be evaluated) = FalseConcurrency and parallelism support: Haskell’s purity makes it relatively easy to implement concurrency and parallelism. Haskell also provides lightweight models for concurrency (MVar, STM, Chan, etc.) and parallelism (Eval, rpar, etc.), which can be used to build complex programs.
parallelAdd x y = runEval $ do
x' <- rpar x -- x and y will be computed in parallel
y' <- rpar y
return (x + y)Enhanced abstract and mathematical thinking abilities: Haskell’s various concepts are closely related to those in mathematics. By thinking about them, you can enhance your abstract and mathematical thinking abilities. If you enjoy mathematics, writing Haskell code feels like solving mathematical problems and can be very enjoyable!
curry :: ((a, b) -> c) -> a -> b -> c
curry fpair x y = fpair (x, y)
uncurry :: (a -> b -> c) -> (a, b) -> c
uncurry f2 (x, y) = f2 x y
--- These functions give you an isomorphism between the two types (a, b) -> c and a -> b -> c.‘Interactive Type Programming’: Thanks to the efforts of industry and academia experts, Haskell’s tool HLS (Haskell Language Server) is very useful. By using type level programming correctly, you can let types and the compiler assist you in thinking and reasoning while writing code. The following information is an example of adding a hole _ in the code to generate a prompt in real time:
• Found hole: _ :: GPoly [x, z] [Power x, Power z] k -> Poly2 z x k
Where: ‘z’, ‘x’, ‘k’ are rigid type variables bound by
the type signature for:
rePX :: forall k x z.
(Num k, Eq k, Fractional k, Show k, AbstractSymbol x,
AbstractSymbol z) =>
Reduction2 x z kBy seeing this prompt, we can know that the hole should be filled with a function of type
GPoly [x, z] [Power x, Power z] k -> Poly2 z x kThus, by constructing powerful type representations, we can let the compiler help us compute types together, which will help us through the thinking process. (Similar to Interactive Theorem Proving, if you know what it is)
Although Haskell has many advantages, it also has some disadvantages, the main ones being the following three:
Haskell has a reputation for being “esoteric” and difficult to learn. On one hand, this is because it is closely related to concepts in mathematics and computer science, which can make many of its concepts abstract. On the other hand, its way of thinking is completely different from the commonly used imperative programming. (But this also means that if you enjoy mathematics, especially the abstract kind, you will definitely enjoy Haskell and may find it more natural to learn! So this may not necessarily be a disadvantage?)
The behavior of lazy evaluation can sometimes be “surprising”: Although lazy evaluation is magical, if not understood or used properly, it can lead to excessive memory usage or unpredictable behavior. Understanding the computational principles of Haskell and using lazy evaluation wisely is an important topic.
Relatively small library: Although Haskell’s official library is already quite large, it is still smaller compared to mainstream programming languages like Python. This means that you may not be able to find the library you need in certain areas, and you may need to implement it yourself or call an external library. However, the Haskell community is very supportive and the documentation for existing libraries is very comprehensive!
Unfortunately, there are a lot of points and knowledge requirements for Haskell, and it is impossible for us to cover everything mentioned in the introduction. Let’s see if we can cover the following core concepts, and the rest can be explored by everyone on their owon!
Introducing Haskell (already done!)
Installing Haskell, ghc, cabal, and other tools through ghcup
Playing with ghci
Using cabal to manage projects (similar to cargo)
Running your first Haskell program
Int, Integer, Double, Float, String, Char, [a], Bool,
Simplest data
Type classes like Num, Ord, Eq, Enum, Bounded, Show, Read
Polymorphic numbers, functions
data, newtype, Type Safety RulesMore Basic Functions
Define complex data structures and new types using data.
Create copies and refinements of existing types using newtype.
What are the rules for type safety?
In this section, we will talk a little bit about category theory!
Category, Functor
[] is a functor, Hom functor
Monad is a monoidal object in the category of endofunctors
Understanding and using Monads such as IO, Maybe, []
Understanding >>=, >=>, >>, do notation
(Tentative) In this session, we will demonstrate how to handcraft your own Parser Library using Monad as a powerful example!
Lectures 1~4 cover the most important core content, Lecture 5 plans to include a complete example owo! However, there is still a vast amount of content that has not been covered, such as monad transform, GADTs, data kind, type family, associated type, generic programming, concurrency, parallel, etc. If time allows, we may select more interesting content. Everyone is also encouraged to explore on their own!
https://www.haskell.org/ghcup/
It is recommended to use ghcup to install and manage versions of the compiler (GHC) and cabal (package manager).
It is also recommended to install HLS (although I am not sure if your editor/IDE supports/uses the Language Server).
Here is an official tutorial for configuring your editor (I personally use neovim).
https://haskell-language-server.readthedocs.io/en/latest/configuration.html#configuring-your-editor
Create a new directory called MyFirstProject using the command “mkdir MyFirstProject”.
Navigate to the newly created directory using the command “cd MyFirstProject”.
Initialize a new project using the command “cabal init”. If you do not want to be prompted with questions, you can use the non-interactive mode by adding the “-n” flag i.e. using the command “cabal init -n” instead.
Congratulations, your Hello World project has been successfully created! You can now try running it using the command “cabal run”. If you want to compile without running, you can use the command “cabal build”.
Introduction to .cabal file: The .cabal file is an essential component of Haskell projects, as it serves as a package description and build system for the project. It contains information such as the project name, version, dependencies, and build instructions. The .cabal file allows for easy management and distribution of Haskell packages, making it a crucial tool for developers.
How to use ghcup to manage compiler versions: Ghcup is a command-line tool that allows for the installation and management of different versions of the Glasgow Haskell Compiler (GHC). This is particularly useful for projects that require specific versions of GHC to run correctly. Ghcup also allows for easy switching between different compiler versions, making it a convenient tool for developers working on multiple projects.
Alternatively, you can use ghc directly for compilation: While ghcup is a useful tool for managing compiler versions, it is not necessary for compiling Haskell projects. The GHC compiler can be used directly from the command line, without the need for additional tools. This can be useful for developers who prefer a more hands-on approach to managing their compiler versions or for projects that do not require specific versions of GHC. However, for more complex projects, using ghcup may be a more efficient and convenient option.