by Eiko, 2024 eikochanowo@outlook.com
欢迎各位来自不同国家和地区的魔法师！你将来到一个代码优雅简洁而又美丽，由神秘深奥的上古魔法类型机制守护着无BUG王国的魔法领域。在这里，法师们施展着以抽象而神秘著称的法术，并且施法时会首先由法杖的魔法类型机制进行检查，从而减少不正确的危险法术被施放。
我们将探索Haskell魔法这一门古老神秘而又现代的魔法力量，学习纯函数式编程的理念以及它们为什么重要，以及如何使用类型系统来保证稳健可信赖的魔法设计。通过学习Haskell魔法，任何人的法力都可以得到增强！在这片神奇的领域，我们将探索许多不曾见过的风景，诸如curry, functor, monad, type variables, classes, type families等多个魔法技能和概念。
学习Haskell魔法和类型魔法，可以让你
写出更稳健，bug-free的程序，大幅减少debug时间(I would say 50%~80% reduction in debug time)
像搭积木一样从简单的物件构造出复杂的程序，让写代码比游戏还好玩(Real fun and intellectually amusing)
见识不一样的魔法世界，学到很多新的知识，增强你的数学思维，抽象思维。这些思维可能会对你产生深远而有益的影响。(even if you don’t use it)
基础知识需求？
理论上，没有基础知识需求。对编程，~~数学，类型论，范畴论~~等概念的熟悉是有益，但非必须的。你可以通过这次旅程来增强这方面的技能！owo
只需要一个充满好奇心和热情的你！
适合什么样的人？
充满好奇心，喜欢探索，思考
喜欢数学，抽象的概念
喜欢建造，构造，创造类的游戏或者活动
~~函数式编程狂热人士~~
~~PhD in Math or Computer Science~~
If you are interested, write some feedback to me!
Haskell是一门有着悠久历史(不少于30年)并在不断发展的的函数式编程语言，和近几十年来计算机科学和数学领域的发展和研究(Type theory, Category theory, lambda calculus)密不可分。
函数式编程意味着在这里，函数是一等公民，所有东西都是函数，并且你可以将复杂的函数作为参数传入其它函数。
最大的区别是，函数式编程中，大部分函数是Pure的，它们没有“副作用” (这也称为denotational semantics)。 这意味着一个函数，只要其输入是确定的，它的输出就一定是确定的。
默认状态下，所有量都是immutable的，没有’变量’。计算不是通过修改状态的值来完成，而是通过一系列~~法术~~函数将输入的值变成一个个加工后的值，最终通过一个个~~法术~~函数合成为输出。
当然这并不代表Haskell不能阅读外部状态或者创建可变的变量，这当然是可以做到的，Haskell里，你可以通过IO和ST等Monad管理顺序计算和副作用，从而将程序Pure的部分和包含Side effect的部分分离开来。如果你试图在Pure函数里使用IO，这是做不到的，类型系统会拒绝编译你的程序。这使得你只要看到类型签名，不用检查代码本身就可以知道函数的行为。
getBirthday :: IO String -- the 'IO' in the type signature tells you this function is not pure
getBirthday = readFile "myBirthday.txt"
myBirthday :: String -- 试图蒙混过关，将带有side effect的String伪装成String
myBirthday = getBirthday -- will not compile, type error: 'IO String' is not 'String'Haskell有如下主要优点：
类型安全：强大的类型系统支持相当复杂的类型级别编程。类型可以帮你做compile time计算，逻辑推理，在编译时就验证你的程序在你规定的方面是正确的，从而排除一大类BUG。类型论的力量来自于数理逻辑，它保证许多错误在编译时就会被抓住。从而通常，只要你的程序能编译，它大概就是对的。
function :: Type Signature Appears Here
function = (... definition ...)举例子：
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 -- 试图蒙混过关，将带有side effect的String伪装成String
myBirthday = getBirthday -- will not compile, type error: 'IO String' is not 'String'通过给相似的type定义newtype防止类型混淆，还可以使用type parameter来给type进一步细化:
{-# 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 Address类型推断：Haskell的Hindley-Milner Type System支持类型推断，类型变量等非常简单好用的特性。
类型变量可以使得同一个函数可以同时被多种类型使用。
类型推断可以让你在很多时候你不需要为函数注释类型，编译器会自己通过上下文去推断它的类型。
-- 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 class范畴和抽象：Haskell支持一些来自数学范畴论中强大的抽象概念，诸如函子和Monad。还有诸如class和instance等抽象手段。这些抽象概念使得我们能够更好的进行抽象推理，增加代码清晰度，代码重用和减少代码量。
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]高度模块化：函数式编程的Pure属性带来的一个巨大优点是，代码的模块化程度很高，可以像搭积木一样利用现有的积木轻松组建出非常复杂的程序。这是因为pureness 保证了函数的输出只由输入决定，而在一般的imperative programming中，只知道函数的输入是不能完全确定函数的输出的，这些函数可能会阅读外部状态的值，或者修改全局变量，导致其它函数的行为发生改变，从而没有那么容易将它们组合起来。
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.高级类型系统支持：type family, associated types, GADTs, data kind systems, 这些非常强大而灵活的系统在其它地方很难找到。这些特性使得Haskell的类型系统拥有极高的表达力，能组织非常复杂的概念和行为。并且还在不断进化：近两年实现的最新的研究成果Linear Type扩展有望在Haskell中实现类似于乃至超过Rust对资源安全的控制(当然Linear Type还有很多别的用途，这方面的东西都很新，大家还在探索中)。
type family AllEq (ts :: [Type]) :: Constraint where
AllEq '[] = ()
AllEq (t ': ts) = (Eq t, AllEq ts)简洁的语法：Haskell的语法非常简洁，支持非常简洁的Pattern match，guards，do notation等。编写函数通常可以在一行或者两行之内完成。没有大括号{ }也没有分号。这使得代码量降低了，并且能让你在代码编辑器上的一页可以看到很多函数。
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]惰性计算：Haskell默认采用惰性计算模型，惰性计算的意思是，所有值只有在需要的时候才被计算，它能避免不必要的计算从而降低计算量。惰性计算还可以允许我们编写类似于无穷列表这样的无穷数据结构。利用得当还能实现神秘的计算模型比如文件按需阅读，流式修改并写入等。
列表[a]是lazy的数据结构，这使得我们可以定义无穷列表
infList = [1,2..]
take 5 infList = [1,2,3,4,5] -- the evaluation stops here, will not loop forever例子：定义一个素数组成的无穷列表
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再比如，在Haskell中，运算符||和&&是对第二个变量lazy的。意思是说，如果第一个变量的值是True (对&&是False)，第二个变量不会被求值。
True || (whatever this is, it will not be evaluated) = True
False && (whatever this is, it will not be evaluated) = False并发和并行化支持：Haskell的Pureness使得并发和并行化的实现相对简单。Haskell还提供了轻量级的并发(MVar, STM, Chan等)和并行化(Eval, rpar等)模型，使用它们可以构建复杂的程序。
parallelAdd x y = runEval $ do
x' <- rpar x -- x and y will be computed in parallel
y' <- rpar y
return (x + y)增强抽象思维和数学思维能力：Haskell的各种概念和数学中的相关概念关系密切，通过思考他们，你可以增强抽象思维能力和数学思维能力。如果你喜欢数学，写Haskell代码的体验就像在解决数学问题，会让你非常享受！
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 gives you an isomorphism between the two types (a, b) -> c and a -> b -> c.~~‘Interactive Theorem Proving’ (划掉)~~ ‘Interactive Type Programming’: 多亏了业界和学界大佬们的努力，Haskell的工具 HLS (Haskell Language Server) 非常好用，如果正确的使用Type level programming，你可以让type和编译器在写代码的过程中辅助你思考和推理。下面的信息是在写代码过程中在代码中加入一个hole _ 让编译器实时为你生成的一个提示：
• 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 k通过看到这个提示，我们可以知道这个hole应该填入一个具有类型
GPoly [x, z] [Power x, Power z] k -> Poly2 z x k的函数。从而通过构建强大的类型表示，我们可以让编译器帮助我们一起计算类型。(类似于Interactive Theorem Proving)
虽然Haskell优点很多，但它也有一些缺点，最主要的有如下三个：
Haskell有“深奥难懂(esoteric)”的reputation，比较难学。一方面是因为它和数学和计算机科学中的一些概念关系密切，这导致其许多概念比较抽象。另一方面是和大家常用的imperative programming的思维方式完全不同。 (但这也表明如果你喜欢数学，尤其是抽象的那种，你肯定会喜欢Haskell，并且上手起来可能会更自然！所以这不一定算一个缺点?)
惰性计算的行为有时“令人惊讶”: 惰性计算虽然很神奇，但是不了解或者不当使用的话，可能导致过多的内存占用或者难以预料的计算行为。深入了解Haskell的计算机理，善用惰性计算，在正确的地方使用惰性计算和强制求值是一个重要的课题。
相对较小的library: 虽然Haskell的官方library已经很大了，但是和python之类的主流编程语言相比还是较小的。这使得你可能在某些领域找不到需要的库，这时你可能需要自己去实现它或者调用外部库。不过Haskell的社区支持，和已经有的library的文档都非常丰富！
很遗憾，Haskell的知识点和知识需求非常的多，我们不可能把以上介绍中出现的东西都讲了。看看我们能否涵盖以下核心概念，剩下的大家可以自己探索哦！
介绍Haskell (already done!)
通过ghcup安装haskell, ghc, cabal等工具
和ghci玩一玩
使用cabal来管理project (类似于cargo)
运行你的第一个Haskell程序
Int, Integer, Double, Float, String, Char, [a], Bool,
最简单的data
type classes like Num, Ord, Eq, Enum, Bounded, Show, Read
polymorphic number, functions
更多基本函数
通过data定义复杂的数据结构和新的类型。
通过newtype创建现有类型的copy和refinement.
什么是类型安全的法则？
这一节我们会讲一点范畴论！
范畴，函子
[]是函子, Hom函子
Monad是自函子范畴里面的一个monoidal object
认识和使用IO, Maybe, [] 等Monad
认识>>=, >=>, >>, do notation
(暂定)这一节我们演示如何使用Monad手搓一个你自己的Parser Library 作为一个强大的example!
Lecture 1~4涵盖了最重要的核心内容，Lecture 5打算放一个完整的例子owo！但是还有海量内容如monad transform, GADTs, data kind, type family, associated type, generic programming, Concurrency, Parallel, 等并没有涉及到。时间允许的话我们也许可以挑选更多有趣的内容。大家也可以（也鼓励）自行探索！
建议通过ghcup安装和管理编译器(GHC)版本，和cabal(包管理器)版本。
推荐安装HLS (当然，不知道你的编辑器/IDE是否支持/用的上Language Server)
以下是一个配置编辑器的官方教程(I personally use neovim.)
https://haskell-language-server.readthedocs.io/en/latest/configuration.html#configuring-your-editor
mkdir MyFirstProject
cd MyFirstProject
cabal init 或者 cabal init -n (non-interactive mode, 如果你不想被问问题)
你的Hello world project已经创建好了！你可以运行cabal run试一试！
介绍.cabal file
如何使用ghcup来管理编译器版本
也可以直接使用ghc来编译