MENU

【代码札记】The Day I Learned Haskell 3

November 29, 2018 • Read: 51 • 瞎折腾

真是没想到,这个系列还能有3。可惜啊,这事不过三(开玩笑),这次来说说第二周的作业(Homework 2),是个二叉树。

话说我们这大学的C语言课程刚讲完结构体,今天讲的链表,二叉树似乎都不讲,结果这宾夕法尼亚大学上来第二周就来二叉树,可见真是硬核。不过在完成这周的作业的过程中,我确确实实体验到了Haskell社区的一句话:

If it compiled, it works.

另外还有Haskell的一个精髓。就是你不必像C或者Java这些指令式编程的语言,不必考虑细枝末节的数据如何变动,只需要考虑其本身的结构就可以了。且往下看。

首先你需要如下文件:Log.hs, error.log, sample.log.

提交时文件名字应该是LogAnalysis.hs

有些东西出现了一些非常糟糕的问题!

解析日志文件

我们不确定到底发生了什么,但是我们已经尽最大的可能来恢复日志文件error.log。他看起来是由包含不同日志信息的行组成。每行开头的第一个字符表明了该行包含的日志类型:

'I' 表示信息性的日志,

'W'表示警告,

'E'表示错误。

其中错误信息后面跟着一个数字表示错误的严重性。其中100表示史诗级前所未见的错误。

日志类型后面都有一个整数表示时间戳,之后直到行末都是日志本身的内容。

整个文档看起来乱糟糟的,显然我们需要一个程序来把这些东西排序。我们将定义一些捕捉这些日志格式的结构:

data MessageType = Info
                | Warning
                | Error Int
                deriving (Show, Eq)
type TimeStamp = Int
data LogMessage = LogMessage MessageType TimeStamp String
                | Unknown String
                deriving (Show, Eq)

注意LogMessage有两个构造函数:一个表示格式正确的日志,另一个表示不符合格式的日志。

我们提供了一个模组Log.hs,其中包含了这些数据类型声明,还有一些其他有用的函数。下载这个文件并放在你源文件的所在目录下,并将你的文件重命名为LogAnalysis.hsLogAnalysis.hs的头几行应该如下:

{-# OPTIONS_GHC -Wall #-}
module LogAnalysis where

import Log

这几行能够让你引用Log.hs以便使用其中的数据类型和函数。

练习1

首先第一步要搞清楚如何解析一条独立的日志。定义如下函数:

parseMessage :: String -> LogMessage

这个函数将解析日志文件的单行。例如:

parseMessage "E 2 562 help help" == LogMessage (Error 2) 562 "help help"
parseMessage "I 29 la la la" == LogMessage Info 29 "la la la"
parseMessage "This is not in the right format" == Unknown "This is not in the right format"

一旦我们能够处理一行日志,那么处理整个日志就不在话下了。定义如下函数:

parse :: String -> [LogMessage]

这个函数解析整个日志文件并返回一个LogMessage列表。

为了测试你的函数,可以使用Log模块中提供的testParse函数,提供你的parse函数,测试的行数以及日志文件。例如在GHCi中加载了你的LogAnalysis.hs之后执行如下命令:

testParse parse 10 "error.log"

留神别像上周一样重复造轮子!用Prelude库中自带的函数来让你的解答尽量的简洁、高水平、可用。例如将字符串"562"转换成整数,你可以使用read函数。其他你可能用到的函数包括:lines, words, unwords, take, drop 和 (.)

我的解答
parseMessage :: String -> LogMessage
parseMessage str = case words str of 
                    ("E":(x:(y:xs))) -> LogMessage (Error $ read x) (read y) (unwords xs)
                    ("I":(x:xs))     -> LogMessage Info (read x) (unwords xs)
                    ("W":(x:xs))     -> LogMessage Warning (read x) (unwords xs)
                    _                -> Unknown str

parse :: String -> [LogMessage]
parse str = case lines str of
                []     -> []
                (x:xs) -> parseMessage x : (parse $ unlines xs) 

简单的解读:wordslines函数分别将字符串按空格和回车符分割成字符串列表。利用模式匹配,匹配每行头一个字符即可分辨出不用的日志类型。而多行,则分割后利用递归处理(将列表交给下一层递归前先要用unlines还原成字符串。该函数在列表的每个字符串之间插入换行符并合成一个大字符串)。

排序日志信息

很抱歉,因为错误信息是由世界范围内多个地点的多个服务器由于多种原因(可能是风暴、闪电、磁盘故障、未完成的程序等)产生的,因此错误信息十分的无序。除非我们将他们排好,否则我们不可能弄清楚到底发生了什么。我们需要定义一个LogMessage的二叉查找树来帮我们排序:

data MessageTree = Leaf
                | Node MessageTree LogMessage MessageTree

注意MessageTree是递归的数据类型:Node构造函数使用两个自己类型的子树,分别表示左子树和右子树,中间是LogMessage。在这里,Leaf类型表示空的树。

一个MessageTree应该按照时间戳排序:即每个Node的时间戳应该都大于它所有左子树的时间戳,并且小于它所有右子树的时间戳。

另外Unknow类型的消息不应当被排进MessageTree因为他们没有时间戳。

练习2

定义函数:

insert :: LogMessage -> MessageTree -> MessageTree

该函数将一个LogMessage插入到一个已有的树,并产生一个新树。insert函数假定给定的MessageTree是已经排序的,并且产生的新树要包含原有树的内容和要插入的LogMessage并且不能打乱顺序。

需要注意的是,如果给定的LogMessageUnknow类型的,函数应该返回未改变的原树。

我的解答
insert :: LogMessage -> MessageTree -> MessageTree
insert (Unknown _) tree = tree
insert message Leaf = Node Leaf message Leaf
insert message@(LogMessage _ time _ ) tree@(Node left content@(LogMessage _ nodeTime _ ) right)
    | time == nodeTime = Node left message right 
    | time <  nodeTime = Node (insert message left) content right
    | time >  nodeTime = Node left content (insert message right)
    | otherwise        = tree
insert _ tree = tree

一点解读:第一个模式匹配处理Unknow类型的消息。由于是递归处理,因此考虑遇到末端空节点的情况,即遇到Leaf时就返回一个包含当前消息的Node。之后便是普遍的情况,给定一个有效的LogMessage和一个MessageTree,按照规则比较时间戳。如果相等,那么保持左右子树不变,更新其中保存的消息。如果时间戳小,就像左子树中插入。反之则向右。这里递归可能不大好理解,请诸位找张纸画一画推敲推敲即可。简单的说就是利用递归找到二叉查找树找到合适的树底部,随后替换其中的Leaf为一个Node。而与此同时在层层递归中还保留住了原有的数据结构与信息。

练习3

一旦我们能往一个已有的树中插入一个数据,那么我们就能够通过LogMessage列表构建出一个MessageTree。特别地,我们定义一个函数:

build :: [LogMessage] -> MessageTree

这个函数从Left开始连续的插入数据项,最终构建一个包含LogMessage内数据项的树。

我的解答
build :: [LogMessage] -> MessageTree
build []     = Leaf
build (x:xs) = buildHelper xs (insert x Leaf)

buildHelper :: [LogMessage] -> MessageTree -> MessageTree
buildHelper [] tree = tree
buildHelper (x:xs) tree = buildHelper xs (insert x tree)

一点解读:这里我不得已使用了一个Helper,原本Haskell的函数应当简洁,但是我实在没有想到如何把这两个函数合成一个,因此如果有想法,请在评论区留下您的高论,我愿闻其详。

buildHelper函数接受一个列表和已有的树做为参数,利用递归遍历列表并加入已有的树,并把新的树传给下一层递归。最终得到了包含列表中全部数据项的数。而build函数则用列表中的第一项构建一个树,随后调用递归处理余下的项。

练习4

最终,我们定义一个函数:

inOrder :: MessageTree -> [LogMessage]

这个函数利用已有的MessageTree产生一个排好序的LogMessage列表。顺序是时间戳从小到大(即所谓的顺序遍历二叉树)。利用这些函数,现在我们能够移除Unknow类型的日志并整理好日志的排序,一下命令是一个例子:

inOrder (build tree)

需要注意的是还有更好的方法排序一个列表,此处只是想让你练习处理一个递归的数据类型。

我的解答
inOrder :: MessageTree -> [LogMessage]
inOrder Leaf = []
inOrder (Node Leaf message Leaf) = [message]
inOrder (Node left content right) =  inOrder left ++ [content] ++ inOrder right

一点解读:显而易见,要求从小到大排列列表,对应二叉树的左小右大,那么自然而然地,利用递归展开左树(小的),然后加上当前的,最后在利用递归展开右树(大的)。

处理加工日志文件

练习5

现在我们能够排序这些日志了,就剩下一个事情:提取有关的信息。此处我们认为“有关”就是“严重性大于等于50Error”。

写一个函数:

whatWentWrong :: [LogMessage] -> [String]

这个函数接受一个未排序的列表,并返回一个字符串列表,其中包括了严重性大于等于50的错误日志的内容,且已经按照时间戳顺序排序了。

例如有如下的日志文件:

I 6 Completed armadillo processing
I 1 Nothing to report
E 99 10 Flange failed!
I 4 Everything normal
I 11 Initiating self-destruct sequence
E 70 3 Way too many pickles
E 65 8 Bad pickle-flange interaction detected
W 5 Flange is due for a check-up
I 7 Out for lunch, back in two time steps
E 20 2 Too many pickles
I 9 Back from lunch

这个对应的是文件sample.log。这里面由四个错误,三个是严重性大于等于50的。所以这个函数的输出应该是:

[ "Way too many pickles"
, "Bad pickle-flange interaction detected"
, "Flange failed!"
]

你可以利用函数testWhatWentWrong测试你的函数。你应当提供你的parse函数、你的whatWentWrong和日志文件的名字。

杂项

  • 我们会用除上面给你的日志文件以外的文件测试你的程序,所以不要使用硬编码(hardcoding)。
  • 你可以随意(实际上我们鼓励)和你的同学讨论你的作业,只要你不照抄别人的答案。

结语

练习6(选做)

由于各种原因,我们开始怀疑最近的混乱是一个自负的黑客造成的。你能弄明白是谁做的吗?

我的解答

讲道理这个我真没发现。但是题中说是一个自负的黑客,那么在提供的五千多行日志中应该会留下蛛丝马迹,因此可以利用上面的函数做些修改,可能会存在某些规律吧,但是我一时间没找到。这个我也不大想找了,如果谁找到了,我愿闻其详。请在评论区留个话,先谢谢您了。

我的结语

这次作业是真的非同寻常。一开始我还吐槽,这二叉树是真的硬核。但是不用于C或Java,指令式编程的二叉树,以插入为例,需要考虑几种不同的情况,其中一大类是一个子树为Null,另一大类则是在非空节点中插入,要考虑插入后左树右树怎么放,总之需要考虑的事情非常多,也非常繁琐,想必编写时再怎么严谨,也逃不掉那恼人的调试和修改。而Haskell则非常不同,一旦你理清楚思路,利用递归配合数据结构本身,就能够很容易的定义出插入的函数,可以参见insert函数:

insert :: LogMessage -> MessageTree -> MessageTree
insert (Unknown _) tree = tree
insert message Leaf = Node Leaf message Leaf
insert message@(LogMessage _ time _ ) tree@(Node left content@(LogMessage _ nodeTime _ ) right)
    | time == nodeTime = Node left message right 
    | time <  nodeTime = Node (insert message left) content right
    | time >  nodeTime = Node left content (insert message right)
    | otherwise        = tree
insert _ tree = tree

只需要考虑数据项的大小关系就行了,额外的定义只有落到树底部将Leaf换成一个Node就行了。而最后一行,则是为了满足编译器的模式匹配完备性检查。你看,一个简单的插入只用了9行代码。而C呢,以我看的教程(C Primer Plus),代码足足印刷了三页纸。这就看出Haskell的好了。

总之Haskell确实是给我提供了一个新的看问题的角度,拿C或Java写程序的时候一上来就一头扎进细节里,然后搞得自己脑壳痛。运气好程序能用,运气不好越写越乱。当然了,有充足的时间还是能够将程序整理好的,但是这样看来,远不如Haskell来的快,这些程序我一共用了不到一个半小时。

最后放出来我的完整版的LogAnalysis.hs

{-# OPTIONS_GHC -Wall #-}
module LogAnalysis where
import Log

parseMessage :: String -> LogMessage
parseMessage str = case words str of 
                    ("E":(x:(y:xs))) -> LogMessage (Error $ read x) (read y) (unwords xs)
                    ("I":(x:xs))     -> LogMessage Info (read x) (unwords xs)
                    ("W":(x:xs))     -> LogMessage Warning (read x) (unwords xs)
                    _                -> Unknown str

parse :: String -> [LogMessage]
parse str = case lines str of
                []     -> []
                (x:xs) -> parseMessage x : (parse $ unlines xs) 

insert :: LogMessage -> MessageTree -> MessageTree
insert (Unknown _) tree = tree
insert message Leaf = Node Leaf message Leaf
insert message@(LogMessage _ time _ ) tree@(Node left content@(LogMessage _ nodeTime _ ) right)
    | time == nodeTime = Node left message right 
    | time <  nodeTime = Node (insert message left) content right
    | time >  nodeTime = Node left content (insert message right)
    | otherwise        = tree
insert _ tree = tree

build :: [LogMessage] -> MessageTree
build []     = Leaf
build (x:xs) = buildHelper xs (insert x Leaf)

buildHelper :: [LogMessage] -> MessageTree -> MessageTree
buildHelper [] tree = tree
buildHelper (x:xs) tree = buildHelper xs (insert x tree)

inOrder :: MessageTree -> [LogMessage]
inOrder Leaf = []
inOrder (Node Leaf message Leaf) = [message]
inOrder (Node left content right) =  inOrder left ++ [content] ++ inOrder right

whatWentWrong :: [LogMessage] -> [String]
whatWentWrong [] = []
whatWentWrong xs = whatWentWrongHelper $ inOrder $ build xs

whatWentWrongHelper :: [LogMessage] -> [String]
whatWentWrongHelper [] = []
whatWentWrongHelper ((LogMessage (Error y) _ str):xs)
    | y >= 50   = [str] ++ whatWentWrongHelper xs
    | otherwise = whatWentWrongHelper xs
whatWentWrongHelper ((LogMessage _ _ _):xs) = whatWentWrongHelper xs 
whatWentWrongHelper ((Unknown _):xs) = whatWentWrongHelper xs

那么这次就是这些了,我们下次见。


知识共享许可协议
【代码札记】The Day I Learned Haskell 3天空 Blond 采用 知识共享 署名 - 非商业性使用 - 相同方式共享 4.0 国际 许可协议进行许可。
本许可协议授权之外的使用权限可以从 https://www.skyblond.info/about.html 处获得。

Archives QR Code Tip
QR Code for this page
Tipping QR Code
Leave a Comment

已有 2 条评论
  1. 圈重点 宾夕法尼亚大学 (〃'▽'〃)

    1. @ic翼诶嘿?那个是网上找到的资源

0:00