Haskell学习笔记(一)——类型与类

data Tree a = Empty | Leaf a | Node (Tree a) a (Tree a)

一、什么是Haskell?

Haskell是一门纯粹函数式编程语言 (purely functional programming language)。

 

命令式编程语言(imperative programming languages) C, C++, Java, Python等,用指令控制计算机“要做什么”;而在纯粹函数式语言中,没有通常的控制流程(control flow)这种概念,而是通过用函数来描述出问题“是什么”来编程,如“阶乘是指从1到某个数的乘积”,“一个串行中数字的和”是指把第一个数字跟剩余数字的和相加。纯粹函数式语言的这个特性使得它的代码优雅且简练,适于表达各种算法。

二、基本特性

1. Haskell是惰性(lazy)的。若非特殊指明,函数在真正需要结果以前不会被求值,也就是说,惰性语言中的计算只是一组初始数据和变换公式。如此以来就有了很多有趣的特性,如无限长度的数据结构。

假设有一个函数double,它可以将一个List中的所有元素都乘以二,返回一个新的List。若是在命令式语言中,把一个List乘以8,执行 double(double(double(lst))),得遍历三遍 lst 才会得到结果。而在惰性语言中,调用 double 时并不会立即求值,它会说“嗯嗯,待会儿再做!”。不过一旦要看结果,第一个 double 就会对第二个说“给我结果,快!”第二个 double 就会把同样的话传给第三个 double,第三个 double 只能将1乘以2得2后交给第二个,第二个再乘以2得4交给第一个,最终得到第一个元素8。也就是说,这一切只需要遍历一次 lst 即可,而且仅在真正需要结果时才会执行。

2.Haskell是静态类型(statically typed)的,但我们并不需要在每段源代码上都标明它的类型。Haskell拥有一套强大的类型系统,支持自动类型推导(type inference)。类型推导可以让程序更加简练。假设有个函数是将两个数值相加,你不需要声明其类型,这个函数可以对一切可以相加的值进行计算。

3.引用透明(Referential Transparency),也即:函数的返回值只依赖于其输入值,就跟数学意义上的函数一样。另外,变量(variable)一旦被指定,就不可以更改了,你已经说了a就是5,就不能再另说a是别的什么数。(其实用variable来表达字面意义的overloading,会让人联想到imperative languages中variable是代表状态,但在functional languages中variable是相近于数学中使用的variable。x=5代表x就是5,不是说x在5这个状态)

定义和赋值的区别在于,定义不分次序,赋值有次序。比如,下列定义:

c = a + b
a = 2
b = 4

在命令式语言中会引起错误,但在Haskell中,这是完全OK的。

4.既可编译也可解释执行。GHC编译器提供了REPL,在ghci中输入:l myfunctions.hs,ghci便会加载myfunctions.hs。之后便可以调用定义的函数。:r 可以重新加载。


三、从零开始

1.定义第一个函数

doubleSmallNumber x = if x > 100 then x else  x*2
doubleSmallNumber将小于100的数都乘以2,调用doubleSmallNumber 3将返回6。

Haskell中,每个函数和表达式都要返回一个结果,包括这里的if语句

yx'nan = "It's me, yxnan!"

上面这个函数yx’nan并没有任何参数,这样的函数通常被称作“定义”或者“名字”。一旦定义,yx’nan就与字符串”It’s me, yxnan!”完全等价,且它的值不可以修改。另外,首字母大写的函数是不允许的,原因以后将会看到。

2.List

在Haskell中,List是一种单类型的数据结构,可以用来存储多个类型相同的元素。我们可以在里面装一组数字或者一组字符,但不能把字符和数字装在一起。因此可以把包含不同类型元素的List看成各自独立的数据类型

字符串实际上就是一组字符的List,“Hello”只是[‘h’,’e’,’l’,’l’,’o’]的语法糖而已。所以我们可以使用处理List的函数来对字符串进行操作。

3.Range

ghci> [1..20]
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]
ghci> ['K'..'Z']
"KLMNOPQRSTUVWXYZ"

ghci> [2,4..20]
[2,4,6,8,10,12,14,16,18,20]
ghci> [3,6..20]
[3,6,9,12,15,18]
ghci> [20,19..1]
[20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1]

可以不标明Range的上限,从而获得无限长度的List,如取前24个13的倍数:take 24 [13,26..]

4.List Comprehension

类似于数学中的set comprehension
四个例子:
ghci> [ x | x <-[50..100], x ´mod´ 7==3]  # 取50到100间所有除7的余数为3的元素
[52,59,66,73,80,87,94]

ghci> let xxs = [[1,3,5,2,3,1,2,4,5],[1,2,3,4,5,6,7,8,9],[1,2,4,2,1,6,3,1,3,2,3,6]]
ghci> [ [ x | x <-xs, even x ] | xs <-xxs]     # 可以嵌套
[[2,2,4],[2,4,6,8],[2,4,2,6,2,6]]

length' xs = sum [1| _ <-xs]   # 函数length'返回xs的长度(_表示不关心变量的取值)

removeNonUppercase st = [ c | c <-st, c ´elem´ ['A'..'Z']]  # 除去字符串中所有非大写字母的函数
测试一下:
ghci> removeNonUppercase "Hahaha! Ahahaha!"
"HA"
ghci> removeNonUppercase "IdontLIKEFROGS"
"ILIKEFROGS"

5.Tuple

与List相比,Tuple:

1.可以包含不同类型的元素;

2.不同长度的Tuple都是独立的类型,故不可追加元素;

3.没有单元素的Tuple。
[(1,2),(8,11,5),(4,5)]        # 错误,长度不同
[(1,2),("one",2)]             # 错误,元素类型不同
("Alan", "MIT", 55)           # OK

两个例子:

ghci> zip [1..] ["apple","orange","cherry","mango"]
[(1,"apple"),(2,"orange"),(3,"cherry"),(4,"mango")]

let rightTriangles' = [ (a,b,c)|c<-[1..10], b<-[1..c], a<-[1..b], a^2+b^2==c^2, a+b+c==24]
ghci> rightTriangles'       # 取得所有三边长度皆为整数且小于等于10,周长为24的直角三角形
[(6,8,10)]

四、Types and Typeclasses

1.Type

在ghci中使用 :t 来检查表达式的类型:

ghci> :t 'a'
'a' :: Char
ghci> :t True
True :: Bool
ghci> :t "HELLO!"
"HELLO" :: [Char]  # [Char] 与 String 等价
ghci> :t (True, 'a')
(True, 'a') :: (Bool, Char)
ghci> :t 4 == 5
4 == 5 :: Bool

为函数加上类型声明:

addThree :: Int -> Int -> Int -> Int
addThree x y z = x + y + z

参数之间由 -> 分隔,而与返回值之间并无特殊差异。返回值是最后一项,参数就是前三项。至于为何只用 -> 而不是 Int,Int,Int->Int之类“更好看”的方式来分隔参数,这和Haskell的函数调用机制有关,在此按下不表,将在“函数”一节中具体展开。

Int 为有界整数,一般为-214748364~214748364,Integer代表无界整数。如果未声明整数的类型,Haskell会自动推导为Integer

其他例子:

factorial :: Integer -> Integer
factorial n = product [1..n]

circumference :: Float -> Float
circumference r = 2 * pi * r

circumference' :: Double -> Double
circumference r = 2 * pi * r

2.Type variables

head 函数可以取任意类型的List的首项,这是怎么做到的呢?我们看看它的类型:

ghci> :t head
head :: [a] -> a

嗯?a是啥?类型吗?不过,凡是类型其首字母必大写,所以它不会是个类型。它是个类型变量,意味着a可以是任意的类型。这一点与其他语言中的泛型(generic)很相似。使用到类型变量的函数被称作“多态函数(polymorphic function)”,head函数的类型声明里标明了它可以取任意类型的List并返回其中的第一个元素。在命名上,类型变量使用多个字符是合法的,不过约定俗成,通常都是使用单个字符,如a,b,c,d…

fst 呢?它返回一个双元素Tuple的首项

ghci> :t fst
fst :: (a, b) -> a
注意,a 和 b 是不同的类型变量,但它们不一定非得是不同的类型,它只是标明了首项的类型与返回值的类型相同。

3.Typeclasses

Typeclass很像Java中的interface,可做类比。

== 函数的类型声明是怎样的?

ghci> :t (==)
(==) :: (Eq a) => a -> a -> Bool

这里我们见到个新东西:=> 符号。它左边的部分叫做类型约束。我们可以这样阅读这段类型声明:“相等函数取两个相同类型的值作为参数并返回一个Bool值,而这两个参数的类型同在Eq类(Typeclass)之中”

elem 函数的类型为 (Eq a) => a -> [a] -> Bool。这是它在检测值是否存在于一个List时使用到了==的缘故。

几个基本的Typeclass:

Eq:包含可判断相等性的类型。除函数以外的所有类型都属于Eq,所以它们都可以判断相等性。
Ord:包含可比较大小的类型。目前所谈到的所有类型都属于Ord类。

ghci> :t (>)
(>) :: (Ord a) => a -> a -> Bool

compare函数取两个Ord类中的相同类型的值作参数,返回比较的结果。这个结果是如下三种类型之一:GT, LT, EQ。

ghci> "Abrakadabra" ´compare´ "Zebra"
LT
ghci> 5 ´compare´ 3
GT

Show:Show的成员为可用字符串表示的类,目前为止,除函数以外的所有类型都是Show的成员。

操作Show Typeclass,最常用的函数为show。它可以取任一Show的成员类型并将其转为字符串。

ghci> show 3
"3"
ghci> show 5.334
"5.334"
ghci> show True
"True"

Read:与Show相反的Typeclass。read函数可以将一个字符串转为Read的某成员类型

ghci> read "True" || False
True
ghci> read "8.2" + 3.8
12.0
ghci> read "5" - 2
3
ghci> read "[1,2,3,4]" ++ [3]
[1,2,3,4,3]

一切良好,尝试一下read “5”如何?

ghci> read "5"
< interactive >:1:0:
    Ambiguous type variable ´a´ in the constraint:
        ´Read a´ arising from a use of ´read´ at <interactive>:1:0-7
    Probable fix: add a type signature that fixes these type variable(s)

ghci说它搞不清楚我们想要的是什么样的返回值。但为啥read “5” – 2又是对的?注意调用read后跟的那部分,ghci通过它来辨认其类型。若要一个boolean值,它就知道必须得返回一个Bool类型的值。但在这里它只知道我们要的类型属于Read Typeclass,而不能明确到底是哪个。看一下read函数的类型声明吧:

ghci> :t read
read :: (Read a) => String -> a

看,它的返回值属于Read Typeclass,但我们若用不到这个值,它就永远都不会得知该表达式的类型。所以我们需要在一个表达式后跟::的类型注释,以明确函数返回值的类型。如下:

ghci> read "5" :: Int  # 注意函数调用具有最高优先级,所以这相当于(read "5") :: Int
5
ghci> read "5" :: Float
5.0
ghci> (read "5" :: Float)*4
20.0
ghci> read "[1,2,3,4]" :: [Int]
[1,2,3,4]
ghci> read "(3, 'a')" :: (Int,Char)
(3,'a')

Enum 的成员都是连续的类型–也就是可枚举。我们可以在Range中用到它的成员类型:每个值都有后继子(successer)和前置子(predecesor),分别可以通过succ函数和pred函数得到。该Typeclass包含的类型有:(),Bool,Char,Ordering,Int,Integer,Float和Double。

ghci> ['a'..'e']
"abcde"
ghci> [LT..GT]  # Ordering
[LT,EQ,GT]
ghci> [3..5]
[3,4,5]
ghci> succ 'B'  # Char
'C'

Bounded 的成员都有一个上限和下限

ghci> minBound :: Int
-2147483648
ghci> maxBound :: Char
'\1114111'
ghci> maxBound :: Bool
True
ghci> minBound :: Bool
False

minBound和maxBound函数很有趣,它们的类型都是(Bounded a) => a。可以说,它们都是多态常量

如果一个Tuple的项都属于Bounded Typeclass,那么该Tuple也属于Bounded:

ghci> maxBound :: (Bool,Int,Char)
(True,2147483647,'\1114111')

Num 是表示数字的Typeclass,它的成员类型都具有数字的特征。检查一个数字的类型:

ghci> :t 20
20 :: Num a => a

可见所有数字都是多态常量,检测*运算子的类型,可以发现它可以处理一切的数字:

ghci> :t (*)
(*) :: (Num a) => a -> a -> a

它只取两个相同类型的参数。所以(5 :: Int) * (6 :: Integer)会引发一个类型错误,而5 * (6 :: Integer)就不会有问题。

Integral 同样是表示数字的Typeclass。Num包含所有的数字:实数和整数。而Intgral仅包含整数,其中的成员类型有Int和Integer。

Floating 仅包含浮点类型:Float和Double。

fromIntegral函数在处理数字时会非常有用。其类型声明为:fromIntegral :: (Num b, Integral a) => a -> b。从中可以看出,它取一个整数做参数并返回一个更加通用的数字,这在同时处理整数和浮点时会尤为有用。举例来说,length函数的类型声明为:length :: [a] -> Int,而非更通用的形式,如(Num b) => length :: [a] -> b。这应该是历史原因吧,反正这挺蠢的。如果取了一个List长度的值再给它加3.2就会报错,因为这是将浮点数和整数相加。面对这种情况,我们就用fromIntegral (length [1,2,3,4]) + 3.2来解决。


(End.)

 

 

 

此条目发表在函数式语言分类目录。将固定链接加入收藏夹。

发表评论

电子邮件地址不会被公开。 必填项已用*标注