haskell入门语法手册

2019-05-30 00:10:42


简介&前言

Haskell是一种函数式编程(FP)的语言,相比于命令式编程(OOP),他拥有代码简洁,强表达力,易于理解,易沉迷等优势,下面放一个用haskell写的八皇后的demo,去掉类型签名的话,核心代码只有四行

safe :: Int -> [Int] -> Int -> Bool
safe _ [] _ = True
safe x (x1:xs) n = x /= x1 && x /= x1 + n && x /= x1 - n && safe x xs (n+1)

queens :: Int -> [[Int]]
queens 0 = [[]]
queens n = [ x:y | y <- queens (n-1), x <- [1..8], safe x y 1]

下面是我给自己整理的入门笔记,听说这里可以发文章,就把自己的笔记加了个前言就投过来试试运气。

由于内容过于trivial,并且我本人水平也不高,如果有表达错误,或者概念的理解错误,再或者觉得作者是个沙雕之类的,都欢迎前来拍砖。

前置准备:

1.按照网上的教程,搭建vscode + stack-ghci的环境

2.新建一个test.hs,然后用vscode打开,并且呼出终端。

3.在终端里进入test.hs的目录,然后输入stack ghci进入haskell环境。

基本语法

函数
doubleme x = x + x

然后在终端里把函数导入

:l test

然后在终端里面运行:doubleme 3

输出6。

我们可以把doubleme x看作函数名和他需要调用的参数,然后=后面是函数的返回值。

其类似于

def doubleme(x):
    return x + x

在函数中,当然也可以调用自己写的另一个函数:

doubleus x y = doubleme(x) + doubleme(y)

导入之后,调用doubleus函数,发现他按照我们的预期运行了。

列表:

列表的定义与python差不多

numbers = [1,3,2,4]

导入之后输入lostnumbers,发现输出了这个列表的值。

列表拼接符号是++

在终端里,我们输入[1,2,4,5] ++ [4,5]

我们发现他输出了[1,2,4,5,4,5]

还有字符串。我们用"abcde"来表示一个字符串,不过值得注意的是他是['a','b','c','d','e']的语法糖。

然而列表本身,就是1:2:3:4:5:[]的语法糖,[]表示一个空列表。

特别注意的是,2:[3,4,5]是对的,但是[2,3,4]:5是错的。

因此,在列表的头部插入元素要比在尾部插入元素快得多。

[...] !! t表示从列表中取出第t个元素,注意下标从零开始。

列表之间可以用>,<,>=,<=,==来比较列表大小,标准是字典序。

其他常用函数

head用于返回列表头部,tail为尾部(去掉头之后的部分),last返回列表最后一个元素,init返回列表去掉last之后的部分。length函数返回列表长度,null检查列表是否为空,reverse反转列表。take用一个整数做参数返回一个列表的前几个元素,drop用一个整数做参数则是删除前面几个元素之后的列表。cycle以一个列表作为参数,返回一个由其无限循环组成的列表,repeat用一个整数作为参数,返回他由这个数无限循环组成的列表。

区间表示方法

[1..20]返回一个1~20的列表,[2,4..20]返回2~20中的所有偶数的列表。

[1,3..]返回大于1的所有奇数,但注意haskell是惰性的,所以他不会真把无线多个元素装进去,而是看你需要什么,比如take 10 [1,3..]返回这个无限长的列表的前十个元素。

列表推导式

列表用一个|分隔开,然后前面写参数的表达式,后面写参数的取值范围。他会自动返回取值范围内参数通过表达式运算出来的值组成的列表。

比如,[x*2 | x <- [1..10]]返回一个[2,4..20]的列表。<-可以暂时读作属于。

条件可以写多个:[x | x <- [50, 100], x `mod` 7 == 3 ]

也可以往里面写if表达式。

boombangs xs = [if x < 10 then "Boom" else "Bang" | x <- xs, odd x]

导入之后调用,注意用列表做参数。

表达式和条件也可以双变量,这样的话就有 $n*m$种结果,其中n为x的取值数,m为y的取值数

[x + y | x <- [1,2,3], y <- [10, 1000, 10000],x * y <= 50]

其中x*y <= 50谓词

其他用法:

可以在函数中,将列表作为参数传进去,然后再列表里面作为条件使用。

这样,我们可以重写一个length函数。

length' xs = sum [1 | _ <- xs]

sum是一个函数获取列表的整数和,xs作为输入的列表,然后对每一个属于xs的元素,在新的列表里放一个1,最后统计一下1的个数就是原列表的长度了。

列表也可以嵌套,嵌套的列表也可以用推导式来提取。

比如

xxs = [[1,3,4,6,7],[2,4,6,3],[9,5,3]]
even_numbers = [[x | xs,even x] | xs <- xxs]

导入之后,even_numbers就是xxs里面所有列表的奇数。

解释就是,对于每一个属于xxs的列表xs,用x去遍历他,将里面的奇数重新生成一个新的列表。

元组:

元组和列表不同的一点就是,其中的组成元素类型可以是不同的

(2,2.5,'haha')这样在元组里面是合法的。

但是,列表里元素的类型都是相同的,如果两个列表元素的类型相同,那么不论长度,其类型是相同的。

元组,当且仅当长度相同,并且对应的元素类型相同时,才能视为相同类型的元组。

序对

仅对二元元组生效,里面由函数fst取出第一个数,snd取出第二个数。zip可以把两个列表拼成一个由二元组组成的列表。

比如zip [1,2,4,5] [2,3,4]

其返回的结果就是[(1,2),(2,3),(4,4)]

当然,这两个类型不相同的列表也能用zip拼起来。

类型与类型类

haskell中所有函数都有其对应的类型。

拿最简单的字符来讲,’a‘的类型就是Char。

稍微复杂点的函数,比如min,其类型签名就是

Ord a => a -> a -> a

其中,Ord是类型类,a是定义的类型。类型类用来限制类型,类型用来限制函数。

比如Char是限制函数必须返回一个字符类型,Ord保证新定义的类型a是可比较的类型。Ord是类型类

=>符号放在类型类与类型之间,称之为类型约束,用于限制类型。

->我们可以暂时理解成python或者c++里面参数之间的逗号。其中最后一个参数是其返回的类型。

上面加粗的概念比较重要,下面还会用得到

定义函数类型

严格来讲,我们写一个函数之前必须定义其类型签名。

比如我们重写一个max函数

max' :: Ord a => a -> a -> a
max' x y = if x > y then x else y

函数语法以及简单的递归

模式匹配

ghci再执行函数的时候,是从上到下匹配的,如果匹配上,就执行这段函数的功能。

比如一个简单的选择分支:

laopo :: String -> String
laopo "yiliya" = "Yes"
laopo "wwww" = "No"

导入之后,你输入laopo "yiliya",他会返回一个"Yes",如果你输入"wwww",它会返回一个"No"。

原理是,他从上到下把你输入的参数和函数的参数进行比较,如果相同,那么就返回那段函数的值。

但是如果你输入其他的字符串,haskell就会报错,因为这套模式不够全面。

所以我们要留一个万能模式,就是把一个字母作为临时参数,那么他会匹配所有符合其类型的输入。

加一行

laopo x = "No"

这样,你随便输入除yiliya以外的一个人,他也不会成为我的laopo。

当然元组也可以用同样的方式匹配,你把他当整数用就行了。

列表与列表推导式的模式匹配

我们先来看一下head函数的重写。

head' :: [a] -> a
head' [] = error "Empty!"
head' (x:_) = x

[a]是列表的类型,也就是规定输入的参数必须是列表。

然后如果列表跟空列表匹配,那么就放出一个Empty的错误。

如果非空,那么就跟x:_匹配,一定要记住,列表是1:2:[]的语法糖,而且匹配是惰性的,x是首个元素,下划线是后面的元素。

哨卫

有了这个东西,可以把模式匹配写得更漂亮。

因为不用每次都另起,把函数给开出来。

拿compare函数举例子

compare' :: (Ord a) => a -> a -> Ordring
x `compare'` y 
    | x == y = EQ
    | x <= y = LT
    | otherwise = GT

|后面,=前面的东西就是哨位,如果哨位为True,那么就执行该表达式。当然表达式也是从上到下执行的。

顺便讲一下,Ordering是一个取值只有EQ,LT,GT的类型,分别表示等于,小于和大于。

where的运用

在函数里面有时候可以用一个未定义的参数,该参数可以在where里面定义。

我们定义一个计算bmi的函数

bmiTell :: Double -> Double -> String
bmiTell weight height
    | bmi <= skinny = "Underweight"
    | bmi <= normal = "Normal"
    | bmi <= fat = "Fat"
    | otherwise = "Too Fat"
  where bmi = weight / height ^ 2
        skinny = 18.5
        normal = 25.0
        fat = 30

当然where不止用于哨位,还能用于普通函数。

当然,where定义的东西也可以进行模式匹配

比如我们拿出姓名的首字母

initials :: String -> String -> String
initials firstname lastname = [f] ++ "." ++ [l] + "."
    where (f:_) = firstname
          (l:_) = lastname

从上到下匹配,拿出每个字符串的第一个字符,然后把这个字符作为单独的字符串给接起来。

当然where里面也可以定义函数

calcbmis :: [(Double, Double)] -> [Double]
calcbmis xs = [bmi w h | (w, h) <- xs]
    where bmi weight height = weight / height ^ 2
let...in的使用

let的用法相当于把where倒过来。

在let里面放入所需要算的参数,然后in里面是函数的返回值

比如let a = 9 in a + 1的返回值是10.

在列表表达式中的使用

calcbmis也可以写成:

calcbmis xs = [bmi | (w, h) <- xs, let bmi = w / h ^ 2]
case的使用

语法结构:

case expression of pattern -> result
                   pattern -> result
                   pattern -> result
                   ...

举个例子,重写head

head' :: [a] -> a
head' xs = case xs of [] -> error "Empty"
                      (x:_) -> x
递归

我觉得一个会C语言的人肯定懂。这里就写一个快排把

quicksort :: (Ord a) => [a] -> [a]
quicksort [] = []
quicksort(x:xs):
    quicksort smaller ++ [x] ++ quicksort larger
    where smaller = [a | a <- xs, a <= x]
          larger = [a | a <- xs, a > x]

就是把第一个数作为标准数,然后以这个数为界把列表分成两段,然后分别解决。

关于函数式更多的思考

在之前的文章,我没有涉及一个词,就是变量。

因为haskell里面是没有全局变量的。就算是a=1,在haskell里面,也被认作是一个函数名为a,返回值为1的函数。

对于一个函数,比方说加法。正常的加法就是返回a+b,而函数式加法里面,是先造出一个加a的函数,然后拿这个函数去调用b。

haskell 代码如下:

add :: Num a => a -> a -> a
add x y = x + y

翻译成python代码,就是

def add(x):
    def ADD(y):
        return x + y;
    return ADD

# test
add_one = add(1)
print(add_one(3))

add返回一个函数,这个函数就是把输入的参数加1.

而haskell里面,每一个->都代表了一个函数,左边是参数后面是返回结果。所以haskell在执行a+b的时候,就相当于执行了上面的python代码。

具体的来说,haskell先用输入的第一个参数,假设为x,返回了一个add(x)的函数,即a->(a->a)括号里面的内容,我们把它设为f。然后括号里面又有一个参数,假设为y,那么其a->a就是f(y)。

这也称之为函数的柯里化。

另外,我们可以得出,一般类似于foo a = bar b a的函数,都可以写作foo = bar b

截断

对于一个函数,比如说类型为a->(a->a),我们可以把括号里的内容截取出来。

简单来讲,我们可以不放入参数,把他的功能表达出来。

又拿回加法做例子啦。上面我们的python代码返回了ADD函数,Haskell是可以直接把功能赋给函数的!

addone :: Int -> Int
addone = (+1)

这就是函数截断。只把其功能拿回出来。我们再终端里执行addone 2可以发现输出了3.

有了他,我们可以构造一个函数,这一函数可以对一个参数执行两遍某个函数。

比如,我们输入(+1) 10,他会返回12。

applytwice :: (a -> a) -> a -> a
applytwice f x = f (f x)

观察函数类型,如果你输入一个(-1),那么这个东西就会保存在f里面成为该函数的功能。x是输入的参数。然后返回的是执行两边f后的参数,非常巧妙。

输入的(-1)之类的截断,其所对应的类型就是(a -> a),不信可以在ghci里面试试:

t (/10)

返回值是Fractional a => a -> a

lambda和折叠

lambda可以建立一个临时的函数,比如f(x)

我们可以写成

\x -> f(x)

\为lambda的标志,后面跟上参数,再用->写出函数的表达式。当然函数的参数也是可以多个的

比如

(\x y -> max x y) 2 3
列表折叠

foldl是一个将列表向左折叠的函数,有一个初值s,然后从左往右依次拿出元素,与s执行一个二元函数,然后拿返回值跟新s,比如一个求和函数,用递归这样写

sum' :: (Num a) => [a] -> a
num' [] = 0
sum' (x:xs) = x + sum xs

用折叠就这样写

sum' :: (Num a) => [a] -> a
--sum' = foldl (+) 0 
sum' = foldl (\acc x -> acc + x) 0

其中注释掉的代码是等价的,因为+这个函数,其本质就是\acc x -> acc + x

写lambda的时候要注意参数位置,第一个是初值,第二个是列表的元素。

foldr是一个将列表向右折叠的函数,注意,其二元函数的参数位置与foldl相反。

比如一个map的实现

--向左折叠和向右折叠,两者的参数是反过来的
map'' :: (a -> b) -> [a] -> [b]
map'' f = foldr (\x acc -> f x : acc) []
--map'' f = foldl (\acc x ->  acc ++ [f x]) []
-- 不过++比:慢很多

因为在头部插入元素要远快于尾部,而foldr是从右往左,每次算出新值都是往列表头部加的,所以更优

再比如一个reverse的实现

用递归这样写

reverse' [] = []
reverse' (x : xs) = reverse xs ++ [x]

用折叠这样写

reverse' = foldl(\acc x -> x : acc) []
-- reverse' = foldl(flip (:)) []

上下等价。

scanl和scanr和fold差不多,但会把每一步的结果存进列表。

比如scanl (+) 0 [3,5,2,1],其结果是[0,3,8,10,11]

foldl1,foldr1,scanl1,scanr1无需定义初始值,他们自动把列表的左端/右端定义为初始值

复合函数

lambda可适用于函数表达式较短的函数。表达式过长就不太方便了。

.是haskell进行组合的函数

类似于f(g(x))的复合函数,在Haskell中是这么定义的:(f.g) (x) = f(g(x))

其中.的类型为(.) :: (b -> c) -> (a -> b) -> a -> c

意思是以两个函数作为参数复合成一个新函数,然后应用在a上输出c。

$`是一个用来改变函数优先级的运算符,也就是说,`$后面的函数先算,然后将他的值代回前面的函数

其类型为( $) :: (a -> b) -> a -> b` 意思是用他后面算出来的`a`作为参数应用到`a -> b`的函数中,然后输出。 有人可能会觉得,这俩玩意不是一样的么,都是把函数右结合的符号。 其实不然,看下面这个实例。 `(*) 3 $ (+1) 2,输入haskell不会报错,然而(*) 3 . (+1) 2就会了。

为什么?因为不管是$`还是`.`,他们的特性都是算出符号之后的函数。 对照其签名,发现`.`是把`(a -> b)`的函数作为参数传给`b -> c`的,而实例中,由于他自动把`.`后面的函数算了出来,变成了把`b`作为参数传给了`(a -> b)`,这明显与签名不符。 所以改成`((*) 3 . (+1)) 2` 就可以了。 ##### point-free与复合函数消括号 在之前的柯里化,我们提到大部分类似于`foo a = bar b a`的函数,都可以写作`foo = bar b` 这就是point-free,无参数。 看一个实例,将自然数的平方根相加,到底几个数时和会超过1000? 我们可以很快写出下面代码 ```haskell sqrtSums :: Int sqrtSums = length ( takeWhile(< 1000) (scanl1 (+) (map sqrt [1..]))) + 1 ``` 先记下`map sqrt [1..]`,然后与`scanl1 (+)` 由于要保证先把map求出来之后再与scanl结合,所以有`scanl1 (+) $ map sqrt [1..200]

然后与takewhile和length复合

`length . takeWhile(< 1000) . scanl1 (+) $ map sqrt [1..200]` 最后把他作为一个整体之后加一,与succ复合 ```haskell sqrtSums = succ . length . takeWhile(< 1000) . scanl1 (+) $ map sqrt [1..200]


### 模块

先看一个最简单的实例

```haskell
import Data.List

numUnique :: (Eq a) => [a] -> Int
numUnique = length . nub

其中,nub函数位于Data.List中,用import导入,功能是对一个列表去重,然后再把它和length复合。

我们再来写一个统计单词数的函数。

首先,我们先写出这个函数的类型签名。

numWords :: String -> [(String, Int)]

我们有以下几个函数,words,用来把一个字符串按空格分成一个由字符串组成的列表,group,我们可以把一个列表内相同的元组挤在一个列表内,返回一个由列表组成的列表。

然后我们就可以想到,先用words把句子中的单词分出来,排序后用group把相同单词挤成列表,再对大列表里的每一个小列表统计length。

最后一步用lambda: map (\ws -> (head ws, length ws))

整个复合出来就是

numWords = map (\ws -> (head ws, length ws)) . group . sort . words

以下是常用模块的函数

函数名 隶属模块 功能
words Data.List 将一串字符串分成一个由单词组成的列表
group Data.List 将一个列表相邻且相同的元素并在一起
sort Data.List 对一个列表进行排序
tails Data.List 返回列表里,所有右端点是最右边的[]的区间
isPrefixOf Data.List 判断第二个列表是否以第一个列表开头
isInfixOf Data.List 判断第一个列表是否是第二个列表的子串
ord Data.Char 将字符转成数字(ASCII)
chr Data.Char 将数字转成字符(ASCII)
foldl' Data.List foldl的优化,严格向左折叠,内存消耗少
digitToInt Data.Char 将字符转化为数字(16进制)
find Data.List 取一个谓词和列表做参数,返回列表中第一个满足条件的元素
fromList Data.Map 把一个由二元组拼成的列表转化为“Map”
lookup Data.Map 在“Map”中查找特定元素
size Data.Map 返回一个Map的大小
fromListWith Data.Map 定义了相同键的处理办法

备注

  1. 其中lookup返回的类型是Maybe,也就是如果存在元素,返回just xxx,否则返回Nothing
  2. Map跟C++的map差不多,内部应该用了某种高效的平衡树实现。
  3. 在引用Map的时候不能简单的import Data.Map,会引起冲突。使用import qualified Data.Map as Map,然后调用时用Map.xxx