Haskell函数式编程之四-List操作

List在函数式语言中是一个重要的抽象，很多事情离了它就很难做到。函数式语言的鼻祖Lisp名称就来自List processing。

Haskell本身也给List操作提供了一系列的操作符以及库函数。

对列表操作的运算符

:将一个元素放置到列表的前端。

1
2
3
4
5
6
7
8

Prelude> 1 : []
[1]
Prelude> 2 : [3,4,5]
[2,3,4,5]
Prelude> 'a' : ['g','h','d']
"aghd"
Prelude> 'a' : "ghd"
"aghd"

从上面例子可以看出一个字符串其实就是Char型的列表。
我们可以这样验证。

1
2

Prelude> "abc" == ['a','b','c']
True

++ 连接两个列表。

1
2
3
4

Prelude> [1,2,3] ++ [4,5,6]
[1,2,3,4,5,6]
Prelude> "abc" ++ "efg"
"abcefg"

使用Range

如果要声明一个1到20的数组，除了将这些数字一一列举出来，我们还可以使用Range来实现，操作符是..。

1
2
3
4

Prelude> [1..10]
[1,2,3,4,5,6,7,8,9,10]
Prelude> ['a'..'h']
"abcdefgh"

Range的默认步长是1，我们可以指定其步长。方法就是给出前两个元素再加上结尾元素，Haskell会根据前两个元素推断出步长，并应用。

1
2
3
4
5
6
7
8

Prelude> [1,3..21]
[1,3,5,7,9,11,13,15,17,19,21]
Prelude> [1,3..20]
[1,3,5,7,9,11,13,15,17,19]
Prelude> ['a','c'..'k']
"acegik"
Prelude> [20,18..0]
[20,18,16,14,12,10,8,6,4,2,0]

使用集合生成新的列表

Haskell对List的操作还有一种神奇的方式。下面是一个数学公式，我们在初中肯定学过。

1

S = { x | x ∈ N, x < 10}

S是一个目标集合，N是源集合，S中的元素是属于集合N,并且小于10的元素。

而在Haskell中可以直接使用这种语法。

1
2
3
4
5
6
7

Prelude> let list = [1,2,3,4,5,6]
Prelude> [x | x <- list, x < 3]
[1,2]
Prelude> [x | x <- list, x < 3, x > 1]
[2]
Prelude> [x * 2 | x <- list, x < 3]
[2,4]

常用的列表操作函数

在《Haskell函数式编程之特性篇》中我们定义了一个map函数。它就是对列表的每个元素进行一个函数元素生成另一个列表。

1
2
3
4

map' :: (a -> b) -> [a] -> [b]

map' f [] = []
map' f (x:xs) =f x : map' f xs

我们可以再定义一个filter函数，用于对列表进行过滤。

1
2
3
4
5
6

filter' :: (a -> Bool) -> [a] -> [a]

filter' f [] = []
filter' f (x:xs)
     | f x       = x : filter' f xs
     | otherwise = filter' f xs

除此之外，Haskell还有大量的库函数用于对list进行操作。我们可以自己一一实现它。

head函数用于获取列表的第一个元素。

1

head' (x:xs) = x

tail函数获取列表的除第一个元素外的所有元素。

1

tail' (x:xs) = xs

last函数是获取列表的最后一个元素。

1
2
3

last' (x:xs)
     | null xs = x
     | otherwise = last' xs

init函数返回列表中除最后一个的其他元素。

1
2
3

init' (x:xs)
     | null xs = []
     | otherwise = x : init' xs

你看使用Haskell实现这样的函数是如此的简单。注意这些函数都没有做对空列表的处理。如果给这些函数传递一个空列表会抛出异常。使用Haskll提供的库函数也一样。

1
2

Prelude> head []
*** Exception: Prelude.head: empty list

fold

对list的操作中我们经常会有这样一个情况，就是给定一个初始值，对list的每个元素进行一个操作，最后得出一个结果,这就像将列表折叠起来一样。比如求数组的最大值、最小值、求和都是这样的模式。Haskell中有相应的函数来实现这种pattern。我们可以自己实现一下。

1
2
3
4

foldl' :: (a -> b -> a) -> a -> [b] -> a

foldl' f s [] = s
foldl' f s (x:xs) = foldl' f (f s x) xs

foldl’函数接收一个函数（这个函数接收一个a类型的值，b类型的值，并返回一个a类型值），一个a类型的值，一个b类型的列表，返回值为a类型的值。 （注意其中的a，b类型并不是确定的类型，它只是代表某类型，这有点像其他编程语言中的泛型。a,b的具体类型是由调用fold’时传入的具体参数推断出来的。）

我们可以用它来计算一个数组的和。

1
2

*Main> foldl' (\ s x -> s + x)  0 [1,2,3]
6

它与我们在Haskell函数式编程之2中提到的sum’ 函数是等价的。
注意这是一个左flod。即它是对列表的每个元素按照从左到右的顺序进行函数运算。

我们也可以实现一个右fold。

1
2
3

foldr' :: (a -> b -> a) -> a -> [b] -> a
foldr' f s [] = s
foldr' f s (x:xs) = f (foldr' f s xs) x

1
2

*Main> foldr' (\ s x -> s + x)  0 [1,2,3]
6

在右fold中，对列表进行函数运算的顺序是从右到左。其实我们可以使用左fold来构造一个右fold。

1
2

foldr2 f s [] = s
foldr2 f s (x:xs) = f s (foldl' f x xs)

1
2

*Main> foldr2 (\ s x -> s + x)  0 [1,2,3]
6

只不过这个右fold有个局限性，那就是a，b两个必须是同一个类型。

我们甚至可以用fold来实现map及filter等函数。

使用左fold实现map和filter。

1
2
3
4
5
6

map2 :: (a -> b) -> [a] -> [b]
map2 f xs =foldl' (\s x -> s ++ [f x]) [] xs

filter2 :: (a -> Bool) -> [a] -> [a]
filter2 f [] = []
filter2 f (x:xs) = foldl' (\s x -> if f x then s ++ [x] else s ) [] xs

使用右fold来实现map和filter。

1
2
3
4
5
6

map3 :: (a -> b) -> [a] -> [b
map3 f xs =foldr' (\s x -> f x : s) [] xs

filter3 :: (a -> Bool) -> [a] -> [a]
filter3 f [] = []
filter3 f (x:xs) = foldr' (\s x -> if f x then x : s else s) [] xs

由于++效率没有:高，所以生成结果为list的时候最好使用右fold。

以上就是关于List操作的各种知识了。其实Haskell中的列表就是一个函数，一个包装了一系列元素的函数。我们甚至可以自己实现自己的List函数。等有空的时候一起实现下。

另外，本篇文章所有源码被我放置在github中，地址是https://github.com/huangbowen521/HaskellLearning,想要源码的可以自行下载。

时间： 2024-10-29 06:39:04

Haskell函数式编程之四-List操作的相关文章

Haskell函数式编程之三-纯函数式编程特点

函数式编程的定义是: In computer science, functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids stateand mutable data. 即:函数式编程是一种编程模型,他将计算机运算看做是数学中函数的计算,并且避免了引入状态及可变数据. 它更强调函数的应用,而不像命令式编

Haskell函数式编程之一-语言初体验

如果你是使用面向对像语言进行编程的程序员,那么你应该去了解掌握一门动态语言.而动态语言的魔力之一就是函数式编程.而要学习了解函数式编程,那么haskell是一个不错的选择. Haskell是是一门纯函数式编程语言(purely functional programming language).在其世界中函数是第一等对象.并且在haskell中没有赋值,例如你指派a的值为5,然后你无法再给a分配其它的值.所以你不能像命令式语言那样命令电脑"要做什么",而是通过函数来描述出问题"

《Haskell函数式编程入门》—— 第1章，第1.6节本章小结

本章小结 学习本章后,相信读者对Haskell应该有了大致的了解.GHCi是一个常用的测试代码的工具,希望读者可以花更多的时间来熟悉.细心的读者可能会发现Haskell与C语言编译后可执行文件的大小有很大差异.其实,Haskell使用内存空间和硬盘空间的效率是有些低的,这也是早期函数式编程没有比C一类的语言更流行的原因之一.但是,如今计算机硬件已经发展到内存和硬盘不会像以前那样限制函数式编程语言能力了,在时间和空间的效率上也可以手动或自动调试优化.因此,相信在不久的未来,函数式编程会以它精炼.缜

《Haskell函数式编程入门》—— 第1章，第1.4节.hs和.lhs文件、注释与库函数

1.4 .hs和.lhs文件.注释与库函数GHCi和Hugs可以解析扩展名为.hs和.lhs的文件.两者所写程序在语法上完全相同,它们的差别是.lhs(literate Haskell script)文件是为了能让Haskell的代码生成文档.有效程序代码可以用"大于号(>)"和空格开头.比如: add :: Int -> Int -> Intadd x y = x + y不以大于号和空格开头的内容将被视作注释处理,且注释与代码间必须有一行以上的间隔.还有一些.lhs

《Haskell函数式编程入门》—— 第1章，第1.5节第一个Haskell程序HelloWorld!

1.5 第一个Haskell程序HelloWorld! HelloWorld程序虽然不能完全展示Haskell编程的风格与优势,但学习计算机编程都是从这里开始的.现在写一个HelloWorld程序,当作开始学习Haskell的第一步吧! 文本编辑器中输入: main = putStrLn "Hello,World!" 保存并命名为Helloworld.hs. 这里可以看到,Haskell和C.Java一样,都以一个名叫main的函数作为程序的开始运行的入口.保存代码文件,打开命令行窗口

《Haskell函数式编程入门》—— 第1章，第1.3节GHCi的使用

1.3 GHCi的使用 GHCi是一个对函数进行测试与调式的工具,可以导入Haskell源代码文件,然后调用其中的函数.查看函数的信息等.本节先学习如何使用GHCi中的命令来对文件和库进行导入等,再来了解如何在GHCi中调用函数. 启动GHCi后可以看到GHCi的版本,还有导入的库等,可以不用管它们,最后一行会有一个Prelude>提示符,其中Prelude指的是GHCi在运行时一个默认的初始环境.它是一个定义了很多类型与函数的库.启动GHCi后,用户可以不做任何设置而直接使用其中定义的内容.下

《Haskell函数式编程入门》——导读

第1章Haskell简介 第1章第1节Haskell的由来第1章第2节Haskell编译器的安装以及编写环境第1章第3节GHCi的使用第1章第4节.hs和.lhs文件.注释与库函数第1章第5节第一个Haskell程序HelloWorld!第1章第6节小结第2章类型系统和函数第3章基于布尔值的函数第4章库函数及其应用第5章递归函数第6章列表内包第7章高阶函数与复合函数第8章定义数据类型第9章定义类型类第10章Monad初步第11章系统编程及输入/输出第12章记录器Monad.读取器Monad.状态

Haskell函数式编程之二-递归

在Haskell的世界中,没有变量赋值,流程跳转,如果要实现一些简单的功能,比如求一个数组中的最大值,都需要借助递归实现. 递归函数的定义: A function may be partly defined in terms of itself. 即如果一个函数的定义中使用了其自身,这个函数就叫做递归函数. 普通递归(traditional recursion) 我们就写一个简单的对数组求和的函数. 1 2 3 sum' :: (Num a) => [a] -> a sum' (x:xs) =

每个人都应该懂点函数式编程

一个问题 假设现在我们需要开发一个绘制数学函数平面图像(一元)的工具库,可以提供绘制各种函数图形的功能,比如直线f(x)=ax+b.抛物线 f(x)=ax²+bx+c或者三角函数f(x)=asinx+b等等.那么怎么设计公开接口呢?由于每种行数的系数(a.b.c等)不同,并且函数构造 也不同.正常情况下我们很难提供一个统一的接口.所以会出现类似下面这样的公开方法: //绘制直线函数图像  public void DrawLine(double a, double b)  {      List<