Haskell 笔记7

April 12, 2017

这是一些阅读Learn You a Haskell for Great Good!的时候的笔记，之前用Latex写的，放在Dropbox里面，现在想把它们整理一下，放在博客里。这是第七章 Modules的笔记。

Loading modules

之前用TeXmacs虽然挺方便，但还是感觉有点不舒服。所以还是换回来吧。

在默认的Prelude模块里面，已经默认引入了一些Data.List中的函数。另外，引入Data.List模块的时候不需要使用带限定符的方法，因为Prelude里面的函数除了默认引入的Data.List的部分函数以外，不会和Data.List里面的其它函数命名冲突。然而，如果再引用其它模块的时候就不一定了。一般情况下只需要用一般的引入模块的方法就够了：import Data.List

Data.List

group这个函数，它接收一个列表，把列表中相邻并且相等的元素合成一个子列表，对于相等但是不相邻的元素，它会分别合成独立的子列表，也就是说，它并不会排序。比如：

	λ> group [1, 2, 2, 2, 3, 4, 2, 2, 2, 5, 6]
	[[1],[2,2,2],[3],[4],[2,2,2],[5],[6]]

如果想要一个列表中的某个元素的个数，可以这样做：

	λ> map (\ xs@(x : xs') -> (x, length xs)) $ group . sort $ [1, 2, 2, 2, 3, 4, 2, 2, 2, 5, 6]
	[(1,1),(2,6),(3,1),(4,1),(5,1),(6,1)]

这里我用到了function composition(.)、function application($)、lambda表达式、lambda表达式中的模式匹配、用@符号来捕获整个模式（注意它的用法，用@符号来把整个模式和部分模式分隔开）。

init函数的意思是得到列表的前n - 1个元素，inits的意思是依次得到列表的前0, 1, 2 ... n个元素组成一个嵌套列表。

tail函数的意思是去掉列表的前1个元素，tails的意思是依次去掉列表的前0, 1, 2 ... n个元素组成的一个嵌套列表。

	λ> init [3, 4, 5, 6]
	[3,4,5]
	λ> tail [3, 4, 5, 6]
	[4,5,6]
	λ> inits [3, 4, 5, 6]
	[[],[3],[3,4],[3,4,5],[3,4,5,6]]
	λ> tails [3, 4, 5, 6]
	[[3,4,5,6],[4,5,6],[5,6],[6],[]]

好像这两个比较容易弄混。可以这样记：tails就代表一个列表的尾部，从最大的尾巴（整个列表）到最小的尾巴（空列表）组成的一个列表。 而inits就代表头部，从最小的头部（空列表）到最大的头部（整个列表）组成的一个列表。可以这样用：

search :: (Eq a) => [a] -> [a] -> Bool
search smallList bigList = foldl (\ accu xs ->
                                    if take (length smallList) xs == smallList
                                    then True
                                    else accu) False
                           $ tails bigList

这个函数用来在一个嵌套列表里面找一个子列表：

	λ> search [3..5] [1..7]
	True
	λ> search [3, 5] [1..7]
	False

最常见的应用就是在一个字符串里面找一个字符串吧，因为一个字符串也是一个列表。其实这个函数已经有库函数来实现同样的功能：isInfixOf，它接收两个列表，如果第一个列表是第二个列表的子列表那么返回真：

    λ> isInfixOf [3, 5] [1..7]
    False
    λ> isInfixOf [3..5] [1..7]
    True

类似的函数有isPrefixOf，它检查一个列表是不是另外一个列表的前缀。isSuffixOf，它检查一个列表是不是另外一个列表的后缀。

elem函数检查一个元素是不是存在于另外一个列表中。notElem相反。

partition这个函数接收一个predicate和一个列表，返回一个tuple，第一个元素是满足predicate的元素的列表，第二个元素是不满足predicate的元素的列表：

	λ> partition (> 3) [1..7]
	([4,5,6,7],[1,2,3])

这个函数和span函数是有区别的，span函数会在predicate第一次不被满足的地方把列表分割成两个列表，但是partition会遍历整个列表，把满足predicate和不满足predicate的元素分别放到一个列表里面。

find函数接收一个predicate和一个列表，如果列表中有一个元素满足predicate，那么立即返回用Maybe包裹起来的这个值。这个Maybe啊，其实相当于SML里面的option。它可以是Nothing，也可以是Just n。一个Maybe的类型由它所代表的类型决定，比如Just 6的类型就是Maybe Int。

	λ> find (> 9) [1..7]
	Nothing
	λ> find (> 5) [1..7]
	Just 6
	λ> :t (find (> 9) [1..7])
	(find (> 9) [1..7]) :: (Enum a, Num a, Ord a) => Maybe a

由于head函数对于空列表会抛出异常，所以这个时候find函数就是一个比较好的选择，如果有满足predicate的那么就返回一个Just x，如果没有那么返回一个Nothing。对于Maybe类型，后面会学到。

elemIndex函数和elem同样的功能，但是它会返回一个Maybe，如果要找的元素存在，那么返回Just i，如果不存在那么返回Nothing。

	λ> elemIndex 3 [1..7]
	Just 2
	λ> elemIndex 10 [1..7]
	Nothing

elemIndices这个函数接收一个元素和一个列表，返回一个列表，列表中的元素代表要找的元素在列表中的所有的下标。它会遍历整个列表并返回所有出现的位置。因为它返回的是一个列表，所以不需要使用Maybe，因为可以使用空列表来代表不存在，它代替了Nothing的功能。

	λ> ' ' `elemIndices` "Music Flavor by"
	[5,12]
	λ> 'K' `elemIndices` "Music Flavor by"
	[]

findIndex和elemIndex函数类似，但是它接收一个predicate和一个列表，返回第一个使得predicate为真的下标的Maybe。findIndices和elemIndices类似，但是它接收一个predicate和一个列表，返回一个使得predicate为真的下标的列表，或者空列表。

和zip、zipWith函数类似，也有zip{3..7}，zipWith{3..7}函数。比如zip4函数接收四个列表，把它们对应位置的元素打包成一个tuple。zipWith4函数接收一个函数和一个列表，把每个列表对应的元素作为函数的参数然后作为结果列表的一个元素。比如：

	λ> zip4 [1, 2, 3] [4, 5, 6, 7] [9, 10, 11] [12, 13, 14, 15]
	[(1,4,9,12),(2,5,10,13),(3,6,11,14)]
	λ> zipWith4 (\ x y z m -> x + y + z + m) [1, 2, 3] [4, 5, 6, 7] [9, 10, 11] [12, 13, 14, 15]
	[26,30,34]

注意：如果参数列表中的各个列表长度不一样的话，那么结果列表的长度和参数列表中的最短的一致。

lines函数接收一个字符串，根据字符串的换行符把字符串分割成一个一个字符串放到一个子列表里面：

	λ> lines "Hello\nTOUCH\nSummer"
	["Hello","TOUCH","Summer"]

unlines函数则相反，它接收一个字符串列表，把各个字符串用换行符连接成一个大字符串。需要注意的是，结果字符串后面会有一个换行符。不管原来列表的最后一个元素结尾是不是有换行符：

	λ> unlines ["hello", "TOUCH", "Summer"]
	"hello\nTOUCH\nSummer\n"
	λ> unlines ["hello", "TOUCH", "Summer\n"]
	"hello\nTOUCH\nSummer\n\n"

words函数把一个字符串按照空格和换行符分割成多个单词，连续的空格被当作一个空格，然后把这些单词放在结果列表里面。unwords函数接收一个单词列表，把他们用空格连接起来成为一个字符串。注意，结果字符串的结尾没有追加换行符。

nub函数接收一个列表，返回一个所有元素都唯一的一个列表。也就是它把参数中的重复元素都去掉。

delete函数接收一个元素与一个和这个元素相同类型的列表，它会删除列表中参数元素第一次出现的位置：

	λ> delete 3 [1, 2, 3, 4, 5, 3]
	[1,2,4,5,3]

\\ 函数接收两个列表，相当于集合的差，它会从第一个列表中移除所有在第二个列表中出现在元素：

	λ> [1..7] \\ [3..5]
	[1,2,6,7]

union接收两个列表，它类似于集合的并操作。遍历第二个列表，如果第二个列表中的某个元素不存在于第一个列表中，那么追加到结果列表，否则抛弃。

intersect接收两个列表，它类似于集合的交操作。

insert函数的行为类似于C++里面的lower_bound函数，它接收一个参数和一个列表，并且把参数插入到列表中。它会找到第一个不小于参数的位置插入。

	λ> insert 4 [3, 5, 1]
	[3,4,5,1]
	λ> insert 4 [3, 4, 4, 5, 1]
	[3,4,4,4,5,1]
	λ> insert 4 [3, 1]
	[3,1,4]

在第二个例子里，4插入到了原来的列表中的3和4之间。如果列表中所有元素都小于参数，那么把参数插入到列表末尾。

看下面这几个函数的类型：

	λ> :t length
	length :: Foldable t => t a -> Int
	λ> :t take
	take :: Int -> [a] -> [a]
	λ> :t drop
	drop :: Int -> [a] -> [a]
	λ> :t splitAt
	splitAt :: Int -> [a] -> ([a], [a])
	λ> :t (!!)
	(!!) :: [a] -> Int -> a
	λ> :t replicate
	replicate :: Int -> a -> [a]

我们发现这些函数里面都含有Int，其实这些函数本可以更一般，把Int替换成属于Num的成员类型变量。由于历史原因，修改这些函数可能会让现有的很多程序出问题。所以在Data.List里面实现了这些函数的替代品：genericLength，genericTake，genericDrop，genericSplitAt，genericIndex，genericReplicate。这些函数中把Int替换成了Num，所以更具一般性，也更好用。

nub， delete， union， intersect，group这些函数都有其它版本，分别是：nubBy，deleteBy，unionBy，intersectBy，groupBy，不同之处在于，原来的函数使用(==)函数来测试相等性，By版本的函数可以接收一个函数用来测试相等性。比如把一个列表中的正数和负数分别分组：

	λ> groupBy (\ x y -> (x > 0) == (y > 0))  [-1, -2, -3, 0, 3, 2, 1]
	[[-1,-2,-3,0],[3,2,1]]

也可以使用Data.Function模块中的on函数，on函数的定义类似于这样：

	on' :: (b -> b -> c) -> (a -> b) -> a -> a -> c
	on' f g = \ x y -> f (g x) (g y)

所以上面的程序也可以写成：

	λ> groupBy ((==) `on` (> 0)) [-1, -2, -3, 0, 3, 2, 1]
	[[-1,-2,-3,0],[3,2,1]]

sort，insert，maximum，minimum这几个函数也有对应的By版本：sortBy，insertBy，maximumBy，minimumBy。他们都接收一个函数和一个列表，函数参数接收两个元素作为参数，返回值是一个Ordering实例。比如：

	λ> sortBy (compare `on` length) [[3, 4, 5], [1], [2, 3]]
	[[1],[2,3],[3,4,5]]

所以有两类By系列的函数：

  1. 接收一个函数来测试相等性，一般用(==) on something
  2. 接收一个函数来测试顺序，一般用compare on something

Data.Char

这个模块里面的函数是针对字符的。

  • isControl 检查一个字符是不是控制字符。
  • isSpace 检查一个字符是不是空白符：包括空格、制表符、换行符等。
  • isLower 检查一个字符是否是小写字母。
  • isUpper 检查一个符是否是大写字母。
  • isAlpha 检查一个字符是否是字母。
  • isAlphaNum 检查一个字符是否是字母或者数字。
  • isPrint 检查一个字符是否是可打印的。比如控制符是不可打印的。
  • isDigit 检查一个字符是否是数字。
  • isOctDigit 检查一个字符是否是八进制数字。
  • isHexDigit 检查一个数字是否是十六进制数字。
  • isLetter 检查一个字符是否是字母。和isAlpha函数一样。
  • isMark 检查一个字符是否是Unicode标识字符。它们用来组成一些类似于á之类的字符吧好像。法语里面有，西语里面也有。
  • isNumber 检查一个字符是不是numeric，不知道它和isDigit有什么区别。
  • isPunctuation 检查一个字符是否是标点符号。
  • isSymbol 检查一个字符是否是数学或者货币符号。
  • isSeparator 检查一个字符是否是Unicode空格或者分隔符。
  • isAscii 检查一个字符是否是Unicode字符集的前128个字符。
  • isLatin1 检查一个字符是否是Unicode字符集的前256个字符。
  • isAsciiUpper 检查一个字符是否是ASCII并且大写。
  • isAsciiLower 检查一个字符是否是ASCII并且小写。

比如检查一个字符串是否只包含数字和字母，可以用all函数：

	λ> all isAlphaNum "abel457"
	True
	λ> all isAlphaNum "abel-457"
	False

Kewl这个单词啊，和cool的意思差不多吧。

实现words函数：

	words' :: String -> [String]
	words' xs = filter (not . any isSpace) $
	  groupBy ((==) `on` isSpace) xs
	λ> words' "Hey gus its me"
	["Hey","gus","its","me"]
	λ> words' "Hey gus its   me"
	["Hey","gus","its","me"]

这个函数在filter的predicate里面用到了复合函数，有点意思。

Ordering类型的值为LT，EQ，GT。它们是enumeration的。他们描述了两个值比较的所有的结果。同样地，GeneralCategory类型也是enumeration，它描述了任意一个字符所在的类别，一共有31种类别。比如：

	λ> generalCategory 'a'
	LowercaseLetter
	λ> generalCategory ' '
	Space
	λ> generalCategory '\n'
	Control

GeneralCategory类型是Eq的成员，所以是可以比较的：generalCategory c == Space

  • toUpper 把一个字符转化成大写。
  • toLower 把一个字符转化成小写。
  • toTitle 把一个字符转化成title-case，一般情况下就是大写。
  • digitToInt 把一个字符转化成数字，字符必须在’0’..‘9’，’a’..‘f’，’A’..‘F’的范围内。
  • intToDigit 和digitToInt相反，把一个数字转化成字符，数字范围必须在0..15的范围内，转化成的字符是小写的。
  • ord 得到一个字符的ASCII码。
  • chr 从ASCII得到对应的字符。

把一个字符串转化成另外一个字符串：

	encode :: Int -> String -> String
	encode shift xs =
	  let nums = map ord xs
	      nums_ = map (+ shift) nums
	  in
	    map chr nums_

也可以用复合函数的方法：

	encode' :: Int -> String -> String
	encode' shift = map (chr . (+ shift) . ord)

把字符串还原：

	decode :: Int -> String -> String
	decode shift = encode (negate shift)

Data.Map

一般使用一个pair列表来表示：

	phoneBook = [("abel", "123")
	            ,("shin-chan", "789")
	            ,("Zh", "456")]

在一个map里面根据key找到对应的value：

	findKey :: (Eq a) => a -> [(a, b)] -> b
	findKey x = snd . head . filter (\ (k, v) -> k == x)

这个函数当key在map里面不存在的时候会异常。因为把[]传递给了head函数。可以用Maybe来代替：

	findKey' :: (Eq a) => a -> [(a, b)] -> Maybe b
	findKey' k [] = Nothing
	findKey' k ((kk, vv) : xs) = if kk == k then Just vv
	                      else findKey' k xs

很标准的模式匹配的写法。也可以用fold来实现：

	findKey's :: (Eq a) => a -> [(a, b)] -> Maybe b
	findKey's k = foldl (\ accu (kk, vv) ->
	                        if kk == k then Just vv
	                        else accu) Nothing

这里使用的是左折叠，也可以使用右折叠。

在Data.Map里面，map使用树来表示的，而不是用列表。因此速度会快很多。Data.Map导出的函数可能会和Prelude模块里面的函数冲突，因此需要用带有限定符的方式来导入：

	import qualified Data.Map as Map
  • fromList 这个函数接收一个关联列表，返回一个map。如果关联列表中有重复的key，那么会忽略。这个函数的类型是：
	λ> :t Map.fromList
	Map.fromList :: Ord k => [(k, a)] -> Map.Map k a

要注意的是，map里面的key必须是Ord的实例，map根据Ord来决定key在树中的位置。另外这个函数的返回值是Data.Map k a，其中key和value的类型也包括在里面。

  • empty 没有参数，返回一个空的map。
  • insert 接收一个key，一个value，一个map，把key-value插入到map中并返回。可以用这个函数来实现fromList：
	fromList' :: (Ord k) => [(k, a)] -> Map.Map k a
	fromList' = foldl (\ accu (k, v) ->
	                     Map.insert k v accu) Map.empty

这里用的是左折叠，如果用右折叠也是可以的。

  • null 检查一个map是否为空。
	λ> Map.empty
	fromList []
	λ> Map.null Map.empty
	True
  • size 返回map的大小，也就是key-value对的个数
  • singleton 接收一个key和一个value，返回一个只含有这个key-value对的map：
	λ> Map.singleton "Hel" 101
	fromList [("Hel",101)]
	λ> Map.insert "Hola" 102 $ Map.singleton "Hel" 101
	fromList [("Hel",101),("Hola",102)]
  • lookup 接收一个键和一个map，返回一个Maybe。如果键存在，那么返回Just value，否则返回Nothing：
	λ> Map.lookup "Hel" $ Map.insert "Hola" 102 $ Map.singleton "Hel" 101
	Just 101
	λ> Map.lookup "Hello" $ Map.insert "Hola" 102 $ Map.singleton "Hel" 101
	Nothing

注意，$是右结合的。

  • member 和lookup类似，只不过它只返回一个Bool，表示提供的键在map中是否存在。
	λ> Map.member "Hello" $ Map.insert "Hola" 102 $ Map.singleton "Hel" 101
	False
	λ> Map.member "Hel" $ Map.insert "Hola" 102 $ Map.singleton "Hel" 101
	True
  • map 功能和Data.List.map类似，接收一个函数和一个map作为参数，把map里面的每个value传递给函数，其返回值作为新的value。
  • filter 功能和Data.List.filter类似，接收一个predicate函数和一个map作为参数，返回一个新的map。这个map里面的所有的value都使得predicate函数返回真。
  • toList 和fromList相反，接收一个map，然后返回一个list：
	λ> Map.toList . Map.filter isUpper $ Map.fromList [(1, 'A'), (3, 'b'), (5, 'C')]
	[(1,'A'),(5,'C')]

复合函数和function application($)真是好用。

  • keys 和Perl一样，返回一个map的键的列表。
  • elems 它竟然不叫做values。。elems是什么鬼。。它返回map的值的列表：
	λ> Map.keys . Map.filter isUpper $ Map.fromList [(1, 'A'), (3, 'b'), (5, 'C')]
	[1,5]
	λ> Map.elems . Map.filter isUpper $ Map.fromList [(1, 'A'), (3, 'b'), (5, 'C')]
	"AC"
  • fromListWith 它和fromList的不同点是：对于list中的相同的key，它会用一个函数来处理对应的value，而不是忽略。注意，它的第一个参数是一个函数，它只处理value的值，所以这个函数的参数是两个value：
	λ> Map.fromListWith (\ x y -> x ++ ", " ++ y) [("abel-abel", "123"), ("bern", "456"), ("abel-abel", "789"), ("repl", "101")]
	fromList [("abel-abel","789, 123"),("bern","456"),("repl","101")]

我们也可以先把关链表里面的value全部变成list，然后把(++)传递给fromListWith函数：

	λ> Map.fromListWith (++) $ map (\ (x, y) -> (x, [y])) [("abel-abel", "123"), ("bern", "456"), ("abel-abel", "789"), ("repl", "101")]
	fromList [("abel-abel",["789","123"]),("bern",["456"]),("repl",["101"])]

另外一种使用场景是：比如在列表里面一个key有多个value，我们想选择其中最大的value作为map中的value，所以：

	λ> Map.fromListWith max [("1", 2), ("1", 3), ("2", 10)]
	fromList [("1",3),("2",10)]

或者把所有相同key对应的value加起来：

	λ> Map.fromListWith (+) [("1", 2), ("1", 3), ("2", 10)]
	fromList [("1",5),("2",10)]
  • insertWith 和insert类似，它接收一个额外的函数，当要插入的key在map中已经存在的时候，用这个函数来更新map中对应的value的值：
	λ> Map.insertWith (+) 3 10 $ Map.fromList [(1, 2), (2, 3), (3, 4)]
	fromList [(1,2),(2,3),(3,14)]

Data.Set

  • fromList 接收一个列表，返回一个set：
	λ> let s1 = Set.fromList "Hello, I am abel. Buenas nochas!"
	λ> let s2 = Set.fromList "Mucho gusto! Soy Slackware!"
	λ> s1
	fromList " !,.BHIabcehlmnosu"
  • intersection 返回两个set的交集：
	λ> Set.intersection s1 s2
	fromList " !acehlosu"
  • difference 返回第一个set和第二个set的差集：
	λ> Set.difference s1 s2
	fromList ",.BHIbmn"
  • union 返回两个set的并集：
	λ> Set.union s1 s2
	fromList " !,.BHIMSabceghklmnorstuwy"

null, size, member, empty, singleton, insert, delete 这些函数和Map里面的类似。

Making our own modules

comments powered by Disqus