网络书屋(Web Reading Room)

A blogging framework for hackers.

The Greatest Weapons

Everything in Haskell has a Type Here are some Type declarations.

These are your greatest weapons.

head :: [a] –> a — gets the first element of a list

tail :: [a] –> [a] — gets everything but the first element

last :: [a] –> a — gets the last element of a list

init :: [a] –> [a] — gets everything but the last element

(++) :: [a] –> [a] –> [a] — concatenates two lists together

(:) :: a –> [a] –> [a] — prepends an element to a list

fst :: (a,b) –> a — gets the first element of a tuple

snd :: (a,b) –> b — gets the second element of a tuple

(!!) :: [a]–>Int a

数学中λ-calculus的表示法为:

  1. λx.t
  2. λx[t]

“λ”不具有任何特殊意思,标识着其表达式中的可取一数值x带入。 t是表达式(例如x+3、x2+2x+1等)。

代入数值p的表示法为:

  1. (λx.t)p
  2. (λx[t])p

Lisp|scheme的λ表示法与数值代入:

1
2
(lambda (x) (+ x 1))
((lambda (x) (+ x 1) 10))

Haskell:

1
2
3
4
5
6
7
8
\x -> x+1
(\x -> x+1)10

Prelude> map (\x->x+1) [1..10]
[2,3,4,5,6,7,8,9,10,11]

\ para1 para2->(return value)
\ (para1,para2) -> (return value)

Lambda Calculus

前面提到了Haskell是基于Lambda Calculus的,所以在学习Haskell之前,我们有必要了解一下Lambda Caculus的一些基本的内容,方便我们后面正式介绍Haskell。其实,Lambda Calculus是所有函数式语言的基础,要学习FP,最好都了解一下Lambda Calculus。下面对Lambda Calculus做一个简单的介绍:

基本的语法:Lambda Calculus的核心是表达式(Expression),用FP语言写的程序执行的过程,本质上就是对表达式求值的过程

expression := variable | function | application funciton := λvariable.expression (.前面部分为定义(definition),后面部分为函数体(body)) application := expression expression

另外一种表述方法:

1
2
3
<expr> ::= <identifier>
<expr> ::= lambda <identifier-list>. <expr>
<expr> ::= (<expr> <expr>)

前两条语法用于生成lambda表达式(lambda函数),如: lambda x y. x + y haskell里面为了简洁起见用“\”来代替希腊字母lambda,它们形状比较相似。故而上面的定义也可以写成: \ x y. x + y

变量的bound与free:

λx.xy →x is bound, y is free

表达式化简(Reduction)的基本法则:

1
2
3
α−reduction: λx.E→λy.E[y/x]
β−reduction:((λx.E)z)→E[z/x]
η−reduction(if x is not free in E): λx.(Ex)→E
  • Alpha转换公理:例如,“lambda x y. x + y”转换为“lambda a b. a + b”。换句话说,函数的参数起什么名字没有关系,可以随意替换,只要函数体里面对参数的使用的地方也同时注意相应替换掉就是了。

  • Beta转换公理:例如,“(lambda x y. x + y) 2 3”转换为“2 + 3”。这个就更简单了,也就是说,当把一个lambda函数用到参数身上时,只需用实际的参数来替换掉其函数体中的相应变量即可。

软件工程里面的一条黄金定律:“任何问题都可以通过增加一个间接层来解决

变量替换

[y/x]E → substitute all occurrences of x in E to y

以上是Lambda Calculus的一些基础知识,读者朋友现在不理解没有关系,等后面讲到Haskell中相关的部分就可以理解了。对于抑制不住自已的好奇心的朋友,可以在这里:http://en.wikipedia.org/wiki/Lambda_calculus做进一步的了解。

在之前做的lambda的推导其实都只是针对单个参数,包括Haskell也是强调单参数的调用,如果多惨数那就是用curry来解决(funny多参数) 关于多参数的lambda推到比较少见,但是多参数都是可以通过curry实现。

比如Haskell的实现:

1
2
3
4
5
6
7
8
Prelude> :type take
take :: Int -> [a] -> [a]
Prelude> let takeFive = take 5
Prelude> :type takeFive
takeFive :: [a] -> [a]
Prelude> takeFive [1..]
[1,2,3,4,5]