1 All You Need is Lambda

  • A calculus is a method of calculation or reasoning. The lambda calculus is one process for formalizing a method. Lambda calculus is your foundation, because Haskell is a lambda calculus.
  • The essence of Functional Programming(FP) is that programs are a combination of expressions. Expressions include concrete values, variables and functions. In FP, functions are first-class: they can be used as values or passed as arguments, or inputs, to yet more functions.
  • FP languages are all based on the lambda calculus. Haskell is a pure FP language, while some other FP languages incorporate features that aren’t translatable into lambda expressions.
  • The purity of FP languages is also called referential transparency(引用透明性). Referential transparency means that the same function, given the same values to evaluate, will always return the same result in pure FP. 和数学的函数一样，一个 x 只对应一个 y ，一个 y 可以对应多个 x .
  • Lambda calculus has three basic components: expressions, variables, and abstractions. An expression can be a variable name, an abstraction, or a combination of those things. An abstraction is a function that consist of two parts: the head and the body.The head is a $\lambda$ followed by a variable name(parameter). The body is another expression. So, a simple function might look like this: $\lambda x.x$ (the dot is just a separator)
  • Lambda abstraction has no name(like $f$ ). It is an anonymous function, so it cannot be called by name by another function. The name “abstraction” means generalization, because parameters in the head have no concrete type. Once we replace the parameters with values, we making the abstraction concrete.
  • Variable names in an abstraction’s head have no semantically meaning, so $\lambda x.x$ and $\lambda d.d$ are totally the same thing. This is called alpha equivalence ( $\alpha$-等价，又称重命名等价，是 Lambda 表达式之间的最小二元关系).
  • Beta reduction ( $\beta$-规约，是非 $\alpha$-等价的 Lambda 表达式之间的最小二元关系) is this process of applying a lambda term to an argument, replacing the bound variables with the value of the argument, and eliminating the head. The process of beta reduction stops when there are either no more heads, or lambdas, left to apply or no more arguments to apply functions to.其实就是赋值，在 body 中用取值 $Q$ 取代参数 $x$，再去掉 head。例如：
  • Sometimes the body expression has variables that are not named in the head. We call those variables free variables, like $\lambda x.xy$ . Free variables are irreducible, so:alpha equivalence does not apply to free variables, so:
  • Functions that require multiple arguments have nested heads. When you apply it once and eliminate the first (leftmost) head, the next one is applied and so on. This formulation was originally discovered by Moses Schönfinkel in the 1920s but was later rediscovered and named after Haskell Curry and is commonly called currying (柯里化，指的是把接受多个参数的函数变换成接受一个单一参数的函数，返回值是接受余下的参数的新函数). 例如：
  • $\beta$-规约的顺序不是唯一的，可以从左到右，也可以先规约括号里的。例如：
  • Beta normal form is when you cannot beta reduce the terms any further.
  • A combinator is a lambda term with no free variables. “Combinators” means only to serve to combine the arguments they are given.
  • Some reducible lambda terms cannot reduce neatly to a beta normal form because they diverge. Divergence means that the reduction process never terminates or ends. Divergence(发散) is the opposite of convergence(收敛). For example:
  • Beta reduce exercises

2 Hello, Haskell

  • A expressions is in normal form when it has reached an irreducible form. Reducible expressions are also called redexes. The process of evaluation or reduction is called “normalizing” or “executing”.
  • Functions in Haskell take one argument and return one result. If we pass multiple arguments to a function, each step of currying can be considered as calling a new function with one input and one output.
  • Function names must start with lowercase letters.
  • Haskell uses a nonstrict evaluation (also called “lazy evaluation”) strategy which defers evaluation of terms until they’re forced by other terms referring to them.
  • Calling functions in Haskell default to prefix syntax, but not all functions are prefix. Operators, such as arithmetic operators, are functions which can be used in infix style. All operators are functions, while not all functions are operators. We can use infix operators in prefix fashion by wrapping them in parentheses, so 100 + 100 is the same as (+) 100 100 .
  • The order of declarations in a source code file doesn’t matter because GHCi loads the entire file at once, so it knows all the values that have been defined. On the other hand, when you enter them one by one into the REPL, the order does matter.
  • Indentation of Haskell code is significant. Use spaces, not tabs, to indent your source code.
  • Whitespace is often the only mark of a function call, unless parentheses are necessary due to conflicting precedence. Trailing whitespace, that is, extraneous whitespace at the end of lines of code, is considered bad style.
  • some arithmetic functions：
    • / : fractional division. 3 / 2 == 1.5
    • div : integral division, round down(向下取整), div 4 3 == 1, div (-4) 3 == -2
    • quot : integral division, round towards zero(向0取整), quot 4 3 == 1, quot (-4) 3 == -1
    • mod : 整除模量, mod 5 3 == 2, mod 5 (-3) == -1, mod (-5) 3 == 1, mod (-5) (-3) == -2
    • rem : 整除余数, rem 5 3 == 2, rem 5 (-3) == 2, rem (-5) 3 == -2, rem (-5) (-3) == -2
    • (quot x y)*y + (rem x y) == x
    • (div x y)*y + (mod x y) == x
    • mod 结果的符号与第二个参数相同, rem 的结果符号与第一个参数相同。
    • 无论参数的正负，rem 结果的绝对值都与正数整除的余数相同，因此计算的时候可以先不考虑符号。而 mod 的计算过程可以想象成转时钟，第一个参数代表转的方向和刻度数，第二个参数代表表盘的排列方向和正负号，比如 15 表示正向转 15 下，-15 表示反向转 15 下，12 表示表盘顺时针排列为 0~11，-12 表示表盘逆时针排列为 0~-11，那么有 mod 15 12 == 3, mod (-15) 12 == 9, mod 15 (-12) == -9, mod (-15) (-12) == -3
  • Negation numbers in Haskell use a kind of syntactic sugar. When syntactic sugar is processed by compiler, the shorter(“sweeter”) form will be transformed to the origin representation. For example, (-1) will be transformed to (negate 1) .
  • $ is a infix operator with the lowest possible precedence. It will allow everything to the right of it to be evaluated first and can be used to delay function application(优先级最低，先算右边). For example, (2^)$(2+)$3*2==(2^)$(2+)$6==(2^)$(2+6)==(2^)$8==2^8==256 .
  • Sectioning is special syntax for partial application on infix operators.
    • (^2) is left section, the same as \x -> x ^ 2
    • (2^) is right section, the same as \x -> 2 ^ x
    • - operator cannot do a right section, because that would be interpreted as negation instead of subtraction.

3 Strings

-