MENU

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

November 29, 2018 • 瞎折腾

真是没想到，这个系列还能有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.hs。LogAnalysis.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)

简单的解读：words和lines函数分别将字符串按空格和回车符分割成字符串列表。利用模式匹配，匹配每行头一个字符即可分辨出不用的日志类型。而多行，则分割后利用递归处理（将列表交给下一层递归前先要用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并且不能打乱顺序。

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

我的解答
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

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

写一个函数：

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://skyblond.info/about.html 处获得。

Haskell二叉树二叉查找树
Last Modified: December 3, 2018
Archives QR Code
QR Code for this page
Tipping QR Code
Leave a Comment

2 Comments
  1. ic翼 ic翼
    Reply

    圈重点 宾夕法尼亚大学 (〃'▽'〃)

    1. 天空Blond 天空Blond
      Reply

      @ic翼诶嘿？那个是网上找到的资源