CIS194 Spring13的Homework 5，有关类型类（typeclass）的作业。你应当提交一个Calc.hs的文件，同时文件中应当包含一个同名的模块（module）。如我们在课上所见，Haskell的类型类提供了特殊的多态性（ad-hoc polymorphism），即能够根据输入的类型决定做什么。 这次作业探讨了在构建特定领域语言（domain-specific languages）时类型类的一个有趣用法。表达式假设有一天你的新工作是一个软件工程师，你被要求为公司的新重磅产品编程：一个计算器。但这不只是一个普通的计算器！广泛的焦点小组（Extensive focus group）分析表明，人们真正想让他们的计算器拥有的功能无非是能够做整数加法和乘法。额外的功能只会让界面变得更杂乱。你的老板已经开始对域（domain）建模了，算术表达式的数据类型如下：data ExprT = Lit Integer | Add ExprT ExprT | Mul ExprT ExprT deriving (Show, Eq)这个类型能够兼容涉及到整数常量、加法、乘法的算术表达式。例如表达式 $(2+3)\times4$ 应该能够表示成：Mul (Add (Lit 2) (Lit 3)) (Lit 4)。你的老板已经在ExprT.hs中定义了ExprT类型，所以和平时一样你只需要在你的文件顶部引用ExprT就可以了。然而，这里就是你的老板卡住的地方。练习 1编写第一个版本的计算器：为ExprT编写一个求值器：eval :: ExprT -> Integer例如：eval (Mul (Add (Lit 2) (Lit 3)) (Lit 4)) == 20我的解答eval :: ExprT -> Integer eval (ExprT.Lit x) = x eval (ExprT.Add a b) = eval a + eval b eval (ExprT.Mul a b) = eval a * eval b解读：简单的模式匹配，这里使用了ExprT.Lit，表明Lit函数是在ExprT模块中定义的，是为了和后面的练习题做出区别，下面还会有定义重名的情况。这个求值器本身就是简单的递归调用和模式匹配。ExprT最基本的结构就是Lit，他的值就是其中包含的整数。而其他的Add和Mul就是对Lit和前述二者的组合，因此对于任意两个ExprT的运算，分别求明白参与运算的两个ExprT的值，再进行运算就是了。练习 2UI部门已经实现了焦点小组的研究，并且已经准备好和你协同了。他们已经开发了前端用户接口：一个用于解析所选语言的文本解析器。他们发给你了一个模组Parser.hs，其中的parseExp函数用于解析。如果你将ExprT的构造函数作为参数传给它，它则将一个字符串以ExprT类型的算术表达式重新表示。例如1：*Calc> parseExp Lit Add Mul "(2+3)*4" Just (Mul (Add (Lit 2) (Lit 3)) (Lit 4)) *Calc> parseExp Lit Add Mul "2+3*4" Just (Add (Lit 2) (Mul (Lit 3) (Lit 4))) *Calc> parseExp Lit Add Mul "2+3*" Nothing利用UI团队的资源实现额外的函数：evalStr :: String -> Maybe Integer该函数对一个字符串类型的算术表达式求值，如果输入的字符串是无效的，那么输出Nothing，如果输入有效，就输出Just n，n是输入所对应的值。我的解答evalStr :: String -> Maybe Integer evalStr str = case parseExp ExprT.Lit ExprT.Add ExprT.Mul str of Nothing -> Nothing Just x -> Just (eval x)这里使用了一个模式匹配来判断由parseExp函数解析的结果是Nothing还是Just x，我知道对于Maybe的判断有更好的函数，例如isNothing和fromMaybe，但是我总觉得对于本题模式匹配更简单吧。如果是Nothing就返回Nothing，否则对其求值并包装一个Just作为返回值。练习 3由于不可抗力—— Win10蓝屏 :( ——后面本来写好的翻译和解答没能保存，因此之后不再进行题目的翻译了。此处推荐使用谷歌翻译，现在谷歌对于长文章已经能翻译的很好了。Good news! Early customer feedback indicates that people really do love the interface! Unfortunately, there seems to be some disagreement over exactly how the calculator should go about its calculating business. The problem the software department (i.e. you) has is that while ExprT is nice, it is also rather inflexible, which makes cateringto diverse demographics a bit clumsy. You decide to abstract away the properties of ExprT with a type class.Create a type class called Expr with three methods called lit, add, and mul which parallel the constructors of ExprT. Make an instance of Expr for the ExprT type, in such a way thatmul (add (lit 2) (lit 3)) (lit 4) :: ExprT == Mul (Add (Lit 2) (Lit 3)) (Lit 4)Think carefully about what types lit, add, and mul should have. It may be helpful to consider the types of the ExprT constructors, which you can find out by typing (for example)*Calc> :t Litat the ghci prompt.Remark. Take a look at the type of the foregoing example expression:*Calc> :t mul (add (lit 2) (lit 3)) (lit 4) Expr a => aWhat does this mean? The expression mul (add (lit 2) (lit 3)) (lit 4) has any type which is an instance of the Expr type class. So writing it by itself is ambiguous: GHC doesn't know what concrete type you want to use, so it doesn't know which implementations of mul, add, and lit to pick.One way to resolve the ambiguity is by giving an explicit type signature, as in the above example. Another way is by using such an expression as part of some larger expression so that the context in which it is used determines the type. For example, we may write a function reify as follows:reify :: ExprT -> ExprT reify = idTo the untrained eye it may look like reify does no actual work! But its real purpose is to constrain the type of its argument to ExprT. Now we can write things likereify $ mul (add (lit 2) (lit 3)) (lit 4)at the ghci prompt.我的解答class Expr a where lit :: Integer -> a add :: a -> a -> a mul :: a -> a -> a instance Expr ExprT where lit x = ExprT.Lit x add a b = ExprT.Lit (eval a + eval b) mul a b = ExprT.Lit (eval a * eval b)首先是对ExprT的抽象，可以见得：lit函数和Lit构造函数一样，将一个整数转换成对应的数据类型a，故类型是Integer -> a。而add和mul则接受两个类型相同的表达式，做出计算并封装回原来的类型，因此上述两个函数应当是a -> a -> a。至于Expr对ExprT的实例，则调用ExprT的函数即可。唯一需要注意的是eval计算出来的是整数，还需要调用lit才能够将其封装回ExprT类型。练习 4The marketing department has gotten wind of just how flexible the calculator project is and has promised custom calculators to some big clients. As you noticed after the initial roll-out, everyone loves the interface, but everyone seems to have their own opinion on what the semantics should be. Remember when we wrote ExprT and thought that addition and multiplication of integers was pretty cut and dried? Well, it turns out that some big clients want customized calculators with behaviors that they have decided are right for them.The point of our Expr type class is that we can now write down arithmetic expressions once and have them interpreted in various ways just by using them at various types.Make instances of Expr for each of the following types:Integerworks like the original calculatorBoolevery literal value less than or equal to 0 is interpreted as False, and all positive Integers are interpreted as True; "addition" is logical or, "multiplication" is logical andMinMax"addition" is taken to be the max function, while "multiplication" is the min functionMod7all values should be in the ranage 0...6, and all arithmetic is done modulo 7; for example, $ 5 + 3 = 1 $ .The last two variants work with Integers internally, but in order to provide different instances, we wrap those Integers in newtype wrappers. These are used just like the data constructors we've seen before.newtype MinMax = MinMax Integer deriving (Eq, Show) newtype Mod7 = Mod7 Integer deriving (Eq, Show)Once done, the following code should demonstrate our family of calculators:testExp :: Expr a => Maybe a testExp = parseExp lit add mul "(3 * -4) + 5" testInteger = testExp :: Maybe Integer testBool = testExp :: Maybe Bool testMM = testExp :: Maybe MinMax testSat = testExp :: Maybe Mod7Try printing out each of those tests in ghci to see if things are working. It’s great how easy it is for us to swap in new semantics for the same syntactic expression!我的解答newtype MinMax = MinMax Integer deriving (Eq, Show) newtype Mod7 = Mod7 Integer deriving (Eq, Show) instance Expr Integer where lit = id add a b = a + b mul a b = a * b instance Expr Bool where lit x | x <= 0 = False | otherwise = True add a b = a || b mul a b = a && b instance Expr MinMax where lit = MinMax add (MinMax a) (MinMax b) = lit $ max a b mul (MinMax a) (MinMax b) = lit $ min a b instance Expr Mod7 where lit x = Mod7 (x `mod` 7) add (Mod7 a) (Mod7 b) = lit (a + b) mul (Mod7 a) (Mod7 b) = lit (a * b) 解读：对于整数类，lit其实什么都没干，就相当于lit x = x，因此使用id。add和mul就是整数的运算。对于布尔类型，lit函数需要对给定的整数做个判断。因此这里使用了guards写法，当然也可以用if...else...then语法糖。而加法和乘法按照对应的要求实现即可。关于MinMax类型，lit函数就相当于MinMax的构造函数，因为其本质还是整数，所以不需要额外的转换。加法和乘法都使用了模式匹配，将MinMax里面包含的整数直接取出来，进行相应运算之后再调用lit包装回MinMax类型。此处利用了Haskell的类型推断：对于该add实现，应该是MinMax -> MinMax -> MinMax，因而Haskell会自动找到返回值是MinMax的lit实现，而不会导致错误。下面的Mod7是类似的原理，不再赘述。GHCi检查*Calc> testExp Just (-7) *Calc> testInteger Just (-7) *Calc> testBool Just True *Calc> testMM Just (MinMax 5) *Calc> testSat Just (Mod7 0)练习 5（或者做下面的练习6）The folks down in hardware have finished our new custom CPU, so we'd like to target that from now on. The catch is that a stackbased architecture was chosen to save money. You need to write a version of your calculator that will emit assembly language for the new processor.The hardware group has provided you with StackVM.hs, which is a software simulation of the custom CPU. The CPU supports six operations, as embodied in the StackExp data type:data StackExp = PushI Integer | PushB Bool | Add | Mul | And | Or deriving Show type Program = [StackExp]PushI and PushB push values onto the top of the stack, which can store both Integer and Bool values. Add, Mul, And, and Or each pop the top two items off the top of the stack, perform the appropriate operation, and push the result back onto the top of the stack. For example, executing the program[PushB True, PushI 3, PushI 6, Mul]will result in a stack holding True on the bottom, and 18 on top of that.If there are not enough operands on top of the stack, or if an operation is performed on operands of the wrong type, the processor will melt into a puddle of silicon goo. For a more precise specification of the capabilities and behavior of the custom CPU, consult the reference implementation provided in StackVM.hs.Your task is to implement a compiler for arithmetic expressions. Simply create an instance of the Expr type class for Program, so that arithmetic expressions can be interpreted as compiled programs. For any arithmetic expression exp :: Expr a => a it should be the case thatstackVM exp == Right [IVal exp]Note that in order to make an instance for Program (which is a type synonym) you will need to enable the TypeSynonymInstancesand FlexibleInstances language extension, which you can do by adding{-# LANGUAGE TypeSynonymInstances,FlexibleInstances #-}as the first line in your file.Finally, put together the pieces you have to create a functioncompile :: String -> Maybe Programwhich takes Strings representing arithmetic expressions and compiles them into programs that can be run on the custom CPU.我的解答instance Expr Program where lit x = [PushI x] add a b = a ++ b ++ [StackVM.Add] mul a b = a ++ b ++ [StackVM.Mul] compile :: String -> Maybe Program compile = parseExp lit add mul解读：这里他要求将数学表达式转换成一个由操作组成的列表。显然易见，lit就是要把给定的数字放在栈顶，所以对应他给的函数就是PushI。而加法和乘法则是默认对栈顶的两个数字操作，因此实现就是先把要操作的两个数字放在栈顶，而对于两个列表，每个列表如果正确的话执行完后将会把结果放在栈顶，后续操作的结果会摞在原先的栈顶上。因此a和b分别代表两个程序列表，执行后就相当于[PushI x, PushI y]，其中x和y分别就是a和b执行后的结果。最后连接上对应的操作即可。而compile就是parseExp lit add mul。由于compile输出是Maybe Program，因此类型推断表明parseExp lit add mul使用的实现一定是产生Program的实现，因为parseExp的类型是(Integer -> a) -> (a -> a -> a) -> (a -> a -> a) -> String -> Maybe a，其中a在这里就是Program。练习 6（或做上面的练习5）Some users of your calculator have requested the ability to give names to intermediate values and then reuse these stored values later.To enable this, you first need to give arithmetic expressions the ability to contain variables. Create a new type class HasVars a which contains a single method var :: String -> a. Thus, types which are instances of HasVars have some notion of named variables.Start out by creating a new data type VarExprT which is the same as ExprT but with an extra constructor for variables. Make VarExprT an instance of both Expr and HasVars. You should now be able to write things like*Calc> add (lit 3) (var "x") :: VarExprTBut we can't stop there: we want to be able to interpret expressions containing variables, given a suitable mapping from variables to values. For storing mappings from variables to values, you should use the Data.Map module. Addimport qualified Data.Map as Mat the top of your file. The qualified import means that you must prefix M. whenever you refer to things from Data.Map. This is standard practice, since Data.Map exports quite a few functions with names that overlap with names from the Prelude. Consult the Data.Map documentation to read about the operations that are supported on Maps.Implement the following instances:instance HasVars (M.Map String Integer -> Maybe Integer) instance Expr (M.Map String Integer -> Maybe Integer)The first instance says that variables can be interpreted as functions from a mapping of variables to Integer values to (possibly) Integer values. It should work by looking up the variable in the mapping.The second instance says that these same functions can be interpreted as expressions (by passing along the mapping to subexpressions and combining results appropriately).Note: to write these instances you will need to enable the FlexibleInstances language extension by putting{-# LANGUAGE FlexibleInstances #-}as the first line in your file.Once you have created these instances, you should be able to test them as follows:withVars :: [(String, Integer)] -> (M.Map String Integer -> Maybe Integer) -> Maybe Integer withVars vs exp = exp $ M.fromList vs *Calc> :t add (lit 3) (var "x") add (lit 3) (var "x") :: (Expr a, HasVars a) => a *Calc> withVars [("x", 6)] $ add (lit 3) (var "x") Just 9 *Expr> withVars [("x", 6)] $ add (lit 3) (var "y") Nothing *Calc> withVars [("x", 6), ("y", 3)] $ mul (var "x") (add (var "y") (var "x")) Just 54我的解答class HasVars a where var :: String -> a data VarExprT = Lit Integer | Add VarExprT VarExprT | Mul VarExprT VarExprT | Var String deriving (Show, Eq) evalVar :: VarExprT -> Integer evalVar (Calc.Lit x) = x evalVar (Calc.Add a b) = evalVar a + evalVar b evalVar (Calc.Mul a b) = evalVar a * evalVar b instance HasVars VarExprT where var str = Calc.Lit 0 instance Expr VarExprT where lit x = Calc.Lit x add a b = lit $ (evalVar a + evalVar b) mul a b = lit $ (evalVar a * evalVar b) instance HasVars (M.Map String Integer -> Maybe Integer) where var = M.lookup instance Expr (M.Map String Integer -> Maybe Integer) where lit x = (\_ -> Just x) add f g = (\x -> case f x of Nothing -> Nothing Just f' -> case g x of Nothing -> Nothing Just g' -> Just (f' + g')) mul f g = (\x -> case f x of Nothing -> Nothing Just f' -> case g x of Nothing -> Nothing Just g' -> Just (f' * g')) withVars :: [(String, Integer)] -> (M.Map String Integer -> Maybe Integer) -> Maybe Integer withVars vs exp = exp $ M.fromList vs解读：首先是HasVars类型类，按照题目要求书写即可。然后具体的VarExprT类型，除了包含ExprT的三个构造函数之外，还应该有一个额外的处理变量的构造函数，即Var String。随后是一个辅助函数evalVar，它的作用类似eval，是给VarExprT求值的。这个函数在下面创建Expr实例时将会用到。下面的两个实例，HasVars的实例是令默认的VarExprT的变量默认求值是0，实际上在后面的实现我也没发现有啥用到的地方，因此就给了个0，理论上可以随便给的。Expr实例就是VarExprT的计算，同上面的实例实现，不再赘述。后面关于两个函数类型的实例，其中HasVars就是一个查询。(M.Map String Integer -> Maybe Integer)是给定一个映射表要返回一个可能的整数，而要M.lookup加上一个字符串，剩下的刚好就是这个，即给定一个要查询的变量名，返回一个接收映射表（即从哪查询）并返回查到的数值（有就是Just，没有就是Nothing）。下面的Expr同理。lit函数接收一个整数，返回一个函数，该函数不管接受什么参数都返回该整数，因为这是确定的数，不需要查询。加法则是利用模式匹配，其中x就是要查询的映射表，如果第一个表达式中查询结果是Nothing那么直接就返回Nothing，如果有值，那么就取出来看第二个表达式。第二个表达式同理，只有两个都有值时才做运算，并在运算后包装回原来的数据类型。-全文完- 这里的显示的代码是在GHCi中执行的。进入GHCi后使用:l [filename]加载对应的文件，此处应该是:l Calc.hs或者直接省略.hs直接使用模组名。加载成功后当前光标所在行应当以*Calc>开头，随后可以复制粘贴对应代码框中*Calc>后面的代码，在GHCi中运行即可。其中偶数行代表执行上一行代码后的输出。 ↩
如期而至的周更，这次是Homework 4. 感觉这作业是越来越费脑子了，不过逐渐适应一种新思维模式的感觉很好，而且解出来的一瞬间也十分的有意思。要求：你最终要提交一个单个的.hs（或.lhs）文件，并且文件必须经过类型检查。1练习 1 全麦编程2用一种在Haskell中更加完美的方式重新实现下面两个函数。实践全麦编程的思想，将每个程序分解为对整个数据结构的增量转换管道3。将你的函数分别命名为fun1'和fun2'。fun1 :: [Integer] -> Integer fun1 [] = 1 fun1 (x:xs) | even x = (x - 2) * fun1 xs | otherwise = fun1 xs fun2 :: Integer -> Integer fun2 1 = 0 fun2 n | even n = n + fun2 (n `div` 2) | otherwise = fun2 (3 * n + 1)提示：对于第二个函数你可能希望使用iterate和takeWhile函数。请查阅Prelude的文档来查看他们是干什么的。（此处就当各位查阅过文档，我就不做额外解释了。）我的解答import Data.List fun1' :: [Integer] -> Integer fun1' = foldl' (*) 1 . map (\x -> x - 2) . filter even fun2' :: Integer -> Integer fun2' = sum . filter even . takeWhile (>0) . iterate helper where helper 1 = 0 helper x = if even x then div x 2 else 3 * x + 1一点解说：关于第一个函数，他做的事情是将给定列表中的所有偶数减去2再相乘。因此按照这个思路，先利用filter函数筛选出所有偶数，再使用map函数对列表中的所有偶数减去2，最后用foldl'（或者foldr也行）将所有的数乘起来。这里需要特别说明map函数用的匿名函数。诸位可能和我一样一开始认为，例如map (+2) xs和map (*2) xs这样的语句中，括号里的的函数应该是Integer -> Integer类型的，而天真的我以为这里的减去2，也应当是类似(-2)这种表达，但是实际上这种表达意味着负2，而非减2，因此编译器会报出类型不匹配的错误。我的解决方案是使用匿名函数，而Haskell中也自带了一个函数来专门应对这种情况，即(subtract 2)，或者为了求省事，直接写成(-2+)也是可以的。关于第二个函数，需要诸位动手写一写画一画了。通过一些简单的代入，我们能够发现一些规律。例如代入一个奇数，那么下一次递归调用的参数一定是偶数（3乘以奇数还是奇数，再加1就是偶数了），因此如果偶数再调用过程中除成了奇数，那么最终还是会变成偶数，直到除成1为止。其中还应该注意到一点，只有偶数被加上去了。因此我这里利用iterate函数生成了符合上述规则的数列。第一个数就是传入的数字n，随后根据其奇偶性做出不同的操作，之后再对上一步的结果同样按照其奇偶性做出不同操作，如此反复，直到除成1。由于iterate函数生成一个无限长度的列表，因此需要使用takeWhile (>0)取出有用的部分。在这里数列最终收敛到0，因此我们遇到0就停止，毕竟后面的求和过程中有没有0都不影响结果的。刚刚我们说了，只有偶数才被求和，因此对取出来的数列过遍筛子，留下偶数，随后一个sum求和，万事大吉。练习 2 折叠树回忆一下二叉树的定义。一个二叉树的高度是从根节点到最深的节点的路径的长度（换句话说就是从根节点到最底下，最多经过了多少层）。例如，一个单独的节点（左右都是叶子）高度是0；一个有两个子树的根节点的高度是1.我们说如果一个二叉树的左右子树的高度相差不超过1，则称这个二叉树平衡，由此他的左子树和右子树也平衡。你应该使用下面的定义来表示二叉树。注意每个节点有一个额外的Integer来表示当前节点的高度。data Tree a = Leaf | Node Integer (Tree a) a (Tree a) deriving (Show, Eq)对于这个练习，写一个函数foldTree :: [a] -> Tree a foldTree = ...它将使用foldr从一个列表产生一个平衡的二叉树。举个例子：foldTree "ABCDEFGHIJ" == Node 3 (Node 2 (Node 0 Leaf 'F' Leaf) 'I' (Node 1 (Node 0 Leaf 'B' Leaf) 'C' Leaf)) 'J' (Node 2 (Node 1 (Node 0 Leaf 'A' Leaf) 'G' Leaf) 'H' (Node 1 (Node 0 Leaf 'D' Leaf) 'E' Leaf))结构图如下：【图片】你的答案不一定要将数据摆成一模一样的顺序，只要是个平衡的二叉树，且每个节点都正确的计算了高度就行。我的解答height :: Tree a -> Integer height Leaf = 0 height (Node _ Leaf y Leaf) = 0 height (Node _ subL y subR) = 1 + max (height subL) (height subR) insertTree :: a -> Tree a -> Tree a insertTree x Leaf = Node 0 Leaf x Leaf insertTree x (Node _ Leaf y subR) = Node (height (Node 0 (insertTree x Leaf) y subR)) (insertTree x Leaf) y subR insertTree x (Node _ subL y Leaf) = Node (height (Node 0 subL y (insertTree x Leaf))) subL y (insertTree x Leaf) insertTree x (Node _ subL y subR) | height subL <= height subR = Node (height (Node 0 (insertTree x subL) y subR)) (insertTree x subL) y subR | otherwise = Node (height (Node 0 subL y (insertTree x subR))) subL y (insertTree x subR) foldTree :: [a] -> Tree a foldTree = foldr insertTree Leaf我的这个做法可能有点长，也不算最简洁，但是这确实是我能想到的最好的办法了。如果诸位有更好的主意，请务必在评论区中回复我，洗耳恭听。首先height函数将按照题目中说的规则计算给定节点的高度。insertTree这个函数一会再说，先说foldTree，他说一定要使用foldr，一开始我没看到，后来才看到。使用这个函数就是相当于将列表中的每一项折叠出来，即foldr f z [x1, x2, ..., xn] == f x1 (f x2 ... (f xn z)...)，换作树的话，相当于每次折叠，函数f将列表中的一个元素插入到已有的树中，而一开始的z，就是一个Leaf。而上面的insertTree，就是f。这个函数我写的有些复杂，但是我想不到化简的方法。首先考虑的情况就是把元素插入到一个空的树里面，这也是递归调用的终止条件，即直接返回一个包含当前元素、高度为0的单个节点。随后在考虑左子树或右子树为Leaf的情况，这里不用额外说明两个都是Leaf的情况，此时优先匹配到左子树是Leaf的情况，按那种情况处理。因为不知道处理好的树有多高，因此将要生成的树丢进height函数计算一下高度，这个值作为返回的节点的高度，其中不一定是Node 0，这个的高度随便写，反正height函数不匹配这个参数。之后就是两边都有树的情况了。如果左边的树比较矮，或者和右边的树一样高，那么默认是插到左边的树，否则查到右边的树里，这样不断递归，总会遇到有子节点是Leaf的树，再按照上面的情况处理就行了。我觉得这个函数应该能够用fold来实现，本质上这是一种递归，而fold这一系列的函数就是为了处理递归而设计的，所以应该是可以用fold这些个函数实现的。不过我大概是没想到，同样还是想听听评论区是怎么说的，愿闻其详。另解因为一开始我没看到他说要用foldr那个要求，所以一开始我没用这个，写出的来倒是运行的挺好，后来用这个作为基准与fold版本的答案对比进行调试。代码如下：foldTree :: [a] -> Tree a foldTree [] = Leaf foldTree [m] = Node 0 Leaf m Leaf foldTree (x:xs) = Node deepth (sub1) x (sub2) where deepth = fromIntegral . length . takeWhile ( < 1 + length xs) . map helper $ [0..] helper 0 = 1 helper n = 2^n + helper (n-1) sub1 = foldTree . map fst . filter (odd.snd) $ zip xs [1..] sub2 = foldTree . map fst . filter (even.snd) $ zip xs [1..]从上往下看，首先如果是空列表，那么生成的自然就是Leaf节点，如果只有一个元素，那么就是个高度为0的单节点。遇到长度大于1的链表，那么就利用递归处理。首先解释如何产生当前节点的高度：helper函数接收一个非负整数（负整数的情况没有处理，因为后面保证调用的参数是非负的），对应树的高度，返回值是该高度下最多能够有多少节点。例如高度为0的话就是单独的1个子节点；高度为2则是$ 2^2 $个高度为0的子节点，$ 2^1 $个高度为1的子节点和$2^0$个（1个）高度为2的根节点。利用map将[0..]（从0开始的无限长度的递增数列）的每一个参数传递进去，产生一个第$i$个元素是对应高度为$i$的树能够存储的节点数量。这时候再用takeWhile取所有小于当前传入函数的列表长度的项，例如当前传入的列表长度为5，那么提取到的就是[1,3]；若传入的长度是8，则提取到的是[1,3,7]。对提取的列表求长度，就是对应这一个节点的高度。fromIntegral是将length函数返回的Int转换为Integer类型。余下的操作就是将剩下的列表对半分开，分别调用两个递归产生左子树和右子树。这里我将余下的列表和[1..]（从1开始的无限长度的递增数列）打包成了双元组列表。即假设余下的列表是[a,b,c,d]，那么产生的就是[(a,1),(b,2),(c,3),(d,4)]，随后用filter判断双元组的第二个元素的奇偶性，分别留下序号是奇数的和偶数的，这样就形成了两个平均的列表，交给递归就可以了。练习 3 更多的折叠1. 折叠实现xor实现函数xor :: [Bool] -> Bool它只在输入的列表中有奇数个True时才返回True，与False的个数无关。例如：xor [False, True, False] == True xor [False, True, False, False, True] == False你的答案应该使用fold。我的解答xor :: [Bool] -> Bool xor = foldr (\x y -> if x then not y else y) False对于给定列表，初始值是False，对应匿名函数里面的y，如果列表里的元素（对应匿名函数中的x）是True，那么就将y取反，即奇数个True折叠后的效果相当于一次取反，即返回True，偶数个True折叠后相当于什么也没做，还是False。折叠过程中上一次的结果作为y传入匿名函数，这就算是实现了累加True。2. 用fold实现map如题，完成如下定义：map' :: (a -> b) -> [a] -> [b] map' f = foldr ...使得map'函数和标准的map函数功能相同。我的解答map' :: (a -> b) -> [a] -> [b] map' f = foldr (\x xs -> [f x] ++ xs) [] foldr将初始的空列表或上一次折叠的结果绑定到匿名函数中的xs中，同时将列表中的元素绑定到x，将f应用到x上，将结果构成一个列表在和xs连接到一起，最终还是列表。由于foldr从右边开始求值，因此xs中是从后到前的结果，放在后面。这里其实可以用(f x) : xs代替，因为可以保证xs一定是列表。如果使用foldl，那么应该是xs ++ [f x]，因为它是从左边求值，xs中保存的是从前往后的结果，应该放在前面。3. （选做）用foldr实现foldl如题，完成如下定义myFoldl :: (a -> b -> a) -> a -> [b] -> a myFoldl f base xs = foldr ...myFoldl函数应该和标准的foldl函数功能一致。提示：如下foldr和foldl的工作机制应当有所帮助：foldr f z [x1, x2, ..., xn] == x1 'f' (x2 'f' ... (xn 'f' z)...) foldl f z [x1, x2, ..., xn] == (...((z 'f' x1) 'f' x2) 'f'...) 'f' xn我的解答myFoldl :: (a -> b -> a) -> a -> [b] -> a myFoldl f base xs = foldr (\x y -> f y x) base $ reverse xs由于foldr是从后往前求值，即先折叠最后的元素，再折叠前面的，而foldl则正好相反，因此先对列表逆序，然后再使用foldr操作。需要注意的是foldr将f应用的第一个参数是列表中的元素，第二个是上一次折叠的结果或初始值，而foldl正相反，第一个参数是初始值或折叠结果，第二个才是列表中的元素。因此使用了一个匿名函数调换了参数列表的顺序以适应f函数。练习 4 寻找素数阅读有关Sundaram筛的内容。使用函数组合的方法完成算法。给定整数$n$，你的函数返回值应该包含所有的小于等于$2n+2$的奇素数（不包括2的素数）。sieveSundaram :: Integer -> [Integer] sieveSundaram = ...为了帮助你解题，下面的函数能够生成两个列表的笛卡儿积。这与zip类似，但是结果是两个列表中元素所有可能的组合。例如：cartProd [1,2] ['a','b'] == [(1,'a'),(1,'b'),(2,'a'),(2,'b')]这个函数使用了列表推导4，我们还没在课上讲过，但你不妨搜索一下他们。cartProd :: [a] -> [b] -> [(a, b)] cartProd xs ys = [(x,y) | x <- xs, y <- ys]我的解答sieveSundaram :: Integer -> [Integer] sieveSundaram n = filter (\x -> x /= 0) $ map (\x -> if x `elem` rm then 0 else 2 * x + 1) [1..n] where rm = map (\(x,y) -> x + y + 2 * x * y) $ cartProd [1..n] [1..n]我这里没有按照题目给的形式实现，想了半天，不明确绑定参数n着实是想不出来怎么做。按照链接中的算法，应该有给定i和j，对应所有的i + j + 2*i*j <= n, 1 <= i <= j都应该从[1..n]中剔除出去。而题目中提供的函数可以计算笛卡儿积，刚好就是我们要的所有的(i,j)组合。其中虽然不严格满足i <= j，但不满足的结果也就是导致计算i + j + 2*i*j会有重复项，并不影响最终结果。因此将得到的要剔除的数的列表记成rm。对[1..n]的每一个元素作如下操作 ：判断该元素是不是需要剔除的（elem x rm），如果是就把这一项写成0，不是就将这个元素乘2加1得到对应的素数。最后将所有为0的项过滤掉，得到的就是所有的小于等于$ 2n+2 $的奇素数。小结上一次作业体验到了Haskell的简洁，这次则是感受到了Haskell的递归。之前也写过递归的作业，例如上一次作业Homework3，我也用上过递归，但是并没有使用fold封装，基本上都是一些简单的递归。这次作业尝试了使用fold，应该算是Haskell中对应递归的通用封装。感觉与方便的递归又是一个不一样的思考方式，要考虑如何将递归封装成一个函数交给fold处理，这又是一种挑战，也是一种乐趣。我觉得OK。 这句话的原文是：What to turn in: you should turn a single .hs (or .lhs) file, which must type check. 此处我没有搞懂后半句的意思。 ↩ 原文： Wholemeal programming. ↩ 原文：... breaking each function into a pipeline of incremental transformations to an entire data structure. ↩ 原文：list comprehension. ↩
这次发的是Homework 3的练习。代码高尔夫！1这次的任务很简单：下面有三个任务。对于每个任务，你都应该按照给定名称和类型标识符提交一个对应的尽可能简短的函数。规则除了代码，你的解答必须包含一些解释性的注释。没有注释将会取得0分。博主注：我将在下面利用说明性的文本代替注释。你的注释应当完全展示出你对你的答案的理解。换句话说，一切都很公平，但是你必须证明你理解你写的代码。如果有疑问，那么就在注释中包含更多细节。注释将不会计入你解答的总长度类型标识不计入解答的总长度import声明不计入解答的总长度。因此你可以随意引用Haskell平台的包。空白不会计入解答的总长度。所以你没必要将你的代码全部挤在一行里。适时地使用空格，但同时保持你的代码尽可能简短。我们鼓励你包含上述要求以外的函数。即：我们鼓励你将你的解答分成若干函数，如果你想这样做的话（确实，有时这样做能够达成更短的解答）。当然，额外的函数同样计入你解答的总长度（他们的类型标识除外）。你最终应当提交一个名为Golf.hs的文件，其中定义的模块是Golf。所以文件首行应该是：module Golf where前三个最短的答案将赋予额外的2分，因此你最多可以获得4分。其他情况下长度不是那么重要，长但是正确的答案将获得对应的解答正确的分数。额外的分数取决于他们代码的风格。提示尽可能多地使用标准库函数。这是这次作业的目的所在。例如使用map要比你自己造轮子方便得多。特别地，尝试使用标准库函数封装递归模式，而非你自己实现递归函数。或许你一开始不需要考虑长度问题，先让代码能够工作。之后再慢慢缩减长度。如果有其他不明白的事情，欢迎到Piazza上弄明白。任务练习 1 跳房子你的第一个任务是写这样一个函数：skips :: [a] -> a这个函数输出一个列表的列表。第一个列表是和输入相同的。第二个列表包含输入的第2、4、6、8...个元素，第n个输出应该包含输入的第n、2n、3n...个元素。例如：skips "ABCD" == ["ABCD", "BD", "C", "D"] skips "hello!" == ["hello!", "el!", "l!", "l", "o", "!"] skips [1] == [[1]] skips [True,False] == [[True,False], [False]] skips [] == []注意输出的列表数量和原输入列表的长度是一致的我的解答skips :: [a] -> a skips xs = if length xs == 0 then [] else map (\n -> map snd $ filter (\(x,y) -> x `mod` n == 0) $ zip [1..length xs] xs) [1..length xs]解释：这里利用了if-then-else语法糖省略了一个模式匹配。即上述函数声明等效如下：skips :: [a] -> a skips [] = [] skips xs = map (\n -> map snd $ filter (\(x,y) -> x `mod` n == 0) $ zip [1..length xs] xs) [1..length xs]若输入为空列表，那么输出自然也是空列表。若不为空，则首先从1开始为输入列表中的每个元素标上号（利用双元组和zip），对于输出的第i项，可以判断标号是否是i的倍数，是就留下，不是就扔掉（利用filter和匿名函数\(x,y) -> mod x n == 02）。而map函数则最终将上述产生每一项输出的函数作用到从1开始到length xs为止的列表的每一个元素上（相当于将每个元素作为参数传给函数，然后保持原有顺序将函数的输出保存为一个新列表）。最终得到的列表即为所求。练习 2 极大值极大值是一个数列中严格大于左右两个邻位的元素。例如[2,3,4,1,5]的唯一极大值是4，因为它比它左右两个邻居都大。而5因为右边没有元素，所以不是极大值。写如下函数：localMaxima :: [Integer] -> [Integer]他的输出是输入数列的极大值列表。例如：localMaxima [2,9,5,6,1] == [9,6] localMaxima [2,3,4,1,5] == [4] localMaxima [1,2,3,4,5] == []我的解答localMaxima :: [Integer] -> [Integer] localMaxima xs = if length xs < 3 then [] else case xs of (x:y:z:xs) -> if x < y && y > z then y : localMaxima (y:z:xs) else localMaxima (y:z:xs) 解读：这里的if语法糖和上面的效果一样，等效于：localMaxima :: [Integer] -> [Integer] localMAxima [] = [] localMAxima [a] = [] localMAxima [a,b] = [] localMaxima (x:y:z:xs) = if x < y && y > z then y : localMaxima (y:z:xs) else localMaxima (y:z:xs) 即输入的数列长度小于等于2时，是没有极大值的，因此直接返回空列表。长度大于2时判断第二个元素是不是极大值。如果是就把当前元素留下，随后去掉第一个元素（相当于整个数列往前挪了一位）递归调用localMaxima；如果不是，那就去掉第一个元素直接递归调用。整体效果类似遍历输入的第2到n-1个元素是否为极大值，是则加入到输出列表。其中n为输入数组的元素个数。练习 3 直方图对于这个任务，写如下函数：histogram :: [Integer] -> String该函数接受一个由0到9（包含）组成的Integer类型的列表，并输出一个垂直的直方图来表示输入列表中每个数字的数量。你可以假设输入不会包含任何小于0或大于9的数字，但函数不应该受到不合规数字的影响。你的输出必须精确的符合下面的输出：histogram [1,1,1,5] == * * * * ========== 0123456789 histogram [1,4,5,4,6,6,3,4,2,4,9] == * * * * ****** * ========== 0123456789重要的提示：如果你在ghci中执行类似histogram [3,5]的命令，你应该见到如下输出：" * * \n==========\n0123456789\n"这个是函数返回值String的文本表示，其中包含的\n表示另起一行。为了真正的可视化这个函数的返回值，利用putStr函数：putStr (histogram [3,5])。我的解答histogram :: [Integer] -> String histogram xs = (helper $ map (\n -> fromIntegral $ length $ filter (==n) xs) [0..9]) ++ "==========\n0123456789\n" where helper ys = if foldl (+) 0 ys == 0 then [] else unlines $ (lines $ helper $ map (\x -> if x > 0 then (x-1) else 0) ys) ++ [line ys] line num = if length num == 0 then [] else case num of (z:zs) -> if z > 0 then "*" ++ line zs else " " ++ line zs解读：显而易见，该函数的最后两行是固定的输出，因此直接放在最后和前面的图形连接起来（++ "==========\n0123456789\n" ）。同样显而易见的是，不大可能不利用递归来完成这件事，而利用递归，也不大可能通过对自己的调用完成这件事（我认为即便能，也将十分复杂冗长）。因此我定义了两个额外函数。首先是helper函数，他接受一个列表，这个列表的元素表明了对应角标的数字在原输入中有多少个。即判断原输入中等于0到9的元素个有多少个（map (\n -> fromIntegral $ length $ filter (==n) xs) [0..9])，其中fromIntegral是将length的Int型返回值转换为Integer类型以交给helper处理；length $ filter (==n) xs，filter f list将函数f依次应用到list的元素上，若f返回值是True则该元素留下，否则弃之。(==n)相当于一个匿名函数，接收一个整数，判断是否等于n。最后由length求出留下列表的长度，这里就是对应数字的个数）。helper函数接收到列表之后，首先判断这个列表是否所有数字都是0（这里利用foldl来实现，但理论上折叠方向无所谓，但是左折叠是惰性求值的，如果列表过长可能会占用过多的内存，但是考虑到这里就只是10个数字，惰性求值也无所谓的），如果是0则说明这个直方图处理完了，返回空列表。否则哪个数字不为0，本行对应的地方就应该有个星号（由函数line完成）。随后将包含个数的列表的非0项减一，表明已经处理了一行（由匿名函数\x -> if x > 0 then (x-1) else 0完成，判断给定x是否大于0，大于就减一，否则就返回0。再由map映射到列表的每一项，实现目的），最后将所有行组成一个列表，利用unlines函数将列表拼成一个字符串，列表的每一项由换行符\n分隔。line函数接收包含个数的列表，空列表返回空列表，否则进行模式匹配取第一个元素，如果大于0就写个星号，否则写一个空格，再将余下的列表递归调用自己。效果是遍历包含个数的列表，如果对应项为0，就是空格，若不为0，就是星号。由此可产生一个从上到下从有星号到没星号的直方图。由于我们要的是星号在下面，因此组合每一行时要把顺序调整过来。即在helper函数中最后放本行的（在最下面），先处理个数减一的。由此递归产生的效果是由下至上从有星号到无星号。我的结语这次这个作业真的让我领略到了Haskell这门语言的简洁。也让我领略到了函数式编程的一大特色：与指令式编程不同的是，你不要尝试教编译器如何做一个事，那样你会彻头彻尾的失败。你要做的是告诉编译器你要做什么事。用函数的语言描述你要做的事情，而不是像在C或Java里那样告诉程序怎么循环哪个数据要怎么变之类的细枝末节。只要你正确的描述了问题，那么问题就已经解决的一大半，剩下就是做什么的问题了。而一旦有了合适的函数，那么问题就轻而易举的解决了。我觉得我或许在学习的过程中逐渐喜欢上了Haskell这门语言，以及相对的，不免觉得C或Java这些语言略微的有些繁琐（从上周的二叉树就能看出来，如果是C，那我得写死在电脑前）。或许这个是初学时的错觉，也或许是我还没深入到能够看清这种抽象结构第一这种机制的缺点所在。总而言之，我接下来会继续深入下去，能够接触到Haskell，不至于说不枉此生，但真的不白费这份折腾，非常值得。 代码高尔夫是指利用最简短的代码实现算法。 ↩ 这里以中置函数调用普通函数的符号被markdown判定为行中代码，因此这里还原为了正常的函数调用形式。下同。 ↩
真是没想到，这个系列还能有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那么这次就是这些了，我们下次见。
按照上一篇文章中说的，这篇文章将记述 CIS194 Homework1中的第二个练习，三柱和四柱（选做）汉诺塔问题。三柱汉诺塔三柱汉诺塔应当说是入门递归的一个经典问题，简单地说就是：你面前有三根柱子和n个大小不一的碟子，一开始这n个碟子从上到下由小到大依次顺序摞在第一个柱子上，你需要借助第三根柱子把这些碟子移动到第二根柱子上（或者借助第二根柱子移动到第三根柱子上）。其中你需要遵守如下两条规则：每次只能移动一个盘子大盘子不能被放在小盘子上这种问题通常有两种问法，一种是问n个盘子对应最少的操作次数；另一个是操作的顺序。前者很好说，可以从n=1开始列，列出两三个之后就能够找到规律，用数学归纳法得出最小操作数为$2^n - 1$的结论。而后者才算是真正需要用递归完成的。有关于三柱汉诺塔的视频，我推荐3Blue1Brown的Binary, Hanoi and Sierpinski, part 1和Binary, Hanoi, and Sierpinski, part 2。这两个视频虽然不是全部在讲汉诺塔，但是其中有关汉诺塔递归的问题配合视频演示做的非常不错，十分推荐一看。总而言之，要解决n个碟子的三柱汉诺塔问题，应当有如下步骤（此处随题意借助第三根柱子将碟子从第一根挪到第二根）：将第一根柱子上面的$n-1$个碟子借助第二根柱子挪到第三根上将第$n$个碟子从第一根挪到第二根上将先前的$n-1$个碟子借助第一根柱子从第三根挪回第二根在这个练习中，定义如下：type Peg = String type Move = (Peg, Peg) hanoi :: Integer -> Peg -> Peg -> Peg -> [Move]将String类型用Peg代替，类似C语言中的typedef，同理下面的Move本质上则是（String, String）。这样做的目的是方便阅读和书写程序。第三行定义的则是主要的函数。这个函数接收一个整数类型和三个Peg类型的参数，整数代表碟子的数量，后面三个Peg代表柱子的名字。最终函数输出一个Move类型的列表，表示操作的顺序。关于变量的解读，应当作如下解释：假设有代码：hanoi n "a" "b" "c"，则应该是“将n个盘子借助c从a挪到b”。接下来是代码：hanoi3 :: Integer -> Peg -> Peg -> Peg -> [Move] hanoi3 1 a b c = [(a,b)] hanoi3 n a b c = (hanoi3 (n-1) a c b ) ++ [(a,b)] ++ (hanoi3 (n-1) c b a) 这里假设三根柱子分别叫做a，b，c。按照前面说的，首先要将$n-1$个碟子借助b从a移动到c，然后将第$n$个盘子从a移动到b，再将$n-1$个碟子借助a挪回b此时需要考虑递归终止的条件。即$n-1$递归到1，只剩下一个碟子时，无需再借助别的柱子，直接移动即可。在主函数中运行程序：main :: IO() main = putStrLn $ show $ hanoi3 2 "a" "b" "c"输出应当如下：[("a","c"),("a","b"),("c","b")]和Homework1中给的样例没有差异。四柱汉诺塔四柱汉诺塔和三柱汉诺塔其实差不多，无非是多了一根柱子，可以选择哪一部分挪到第三根柱子，余下的挪到第四根柱子（此处假设还是从第一根挪到第二根）。这样，就有了如下的思路（假设先保留$x$个盘子不动）：借助第二、四根柱子将$n-x$个碟子从第一根挪到第三根上借助第四根柱子将余下的$x$个碟子从第一根挪到第二根上再将上面的$n-x$个碟子借助第一、四根挪回到第二根上那么问题来了，这$x$是多少？在指令式编程中可以直接用循环遍历 $\forall x \in [1,n)$ 然后取其中的最小值。同样在Haskell中也可以。定义函数：hanoi4Helper :: Integer -> Peg -> Peg -> Peg -> Peg -> Integer -> [Move] hanoi4Helper 1 a b _ _ _ = [(a,b)] hanoi4Helper n a b c d x = (hanoi4 (n - x) a c b d ) ++ (hanoi3 x a b d) ++ (hanoi4 (n - x) c b a d) main :: IO () main = putStrLn $ show $ minimum $ map (length . hanoi4Helper 15 "a" "b" "c" "d") [1..14]其中hanoi4Helper定义了一个类似三柱汉诺塔的函数（hanoi3 函数是上面写的三柱汉诺塔函数），只是在一个整数和四个Peg之后额外多了一个整数，这个就是作为待定的$x$。执行如下的主函数：main = putStrLn $ show $ minimum $ map (length . hanoi4Helper 15 "a" "b" "c" "d") [1..14]从右往左看，第一个是map函数，他将一个值到值的函数应用到列表中的每一个数字，通过柯里化将hanoi4Helper和已有的参数15 "a" "b" "c" "d"打包成一个Integer -> [Move]的函数。而括号里还有一个length .这里.表示将右边的函数复合到左边的函数里，类似：$f.g \space x = f(g(x))$的效果。而这里左边的汉诺塔函数被复合到length函数求列表的长度。因此整个括号里面是一个Integer -> Integer的函数，输入待定的x，输出对应的操作数。而被应用的列表正是待定的从1到14（此处n为15）。随后这个列表又被传给minimum函数，这个函数找出列表中的最小值，之后由更左边的函数输出打印到屏幕上。如果要查看对应x的操作数构成的列表，可以删去minimum $，这样输出的将是一个列表。如果没有差错，最小值输出应该是129。列表是[227,197,169,145,129,145,193,305,545,1049,2065,4105,8197,16385]。可见不同的x对于操作次数的影响还是极大的。通过谷歌，在这篇文章中提到了对于给定n求x的公式：$x = \frac {(\sqrt{8*n+1}-1)}{2}$对应的Haskell代码是：x = (floor(sqrt(fromIntegral(8 * n + 1))) - 1) `div` 2因此完善四柱汉诺塔的函数：hanoi4 :: Integer -> Peg -> Peg -> Peg -> Peg -> [Move] hanoi4 1 a b _ _ = [(a,b)] hanoi4 n a b c d = (hanoi4 (n - x) a c b d ) ++ (hanoi3 x a b d) ++ (hanoi4 (n - x) c b a d) where x = (floor(sqrt(fromIntegral(8 * n + 1))) - 1) `div` 2全文完。
许久不见，最近我打算重新拾起Haskell这门语言。要问为什么，就是简单的一句话，我想学Haskell。非要说个什么原因的话，就是高一那时候真的没搞懂Haskell，现在都大一了，或许就能学明白呢？总不能让过去限制自己的能力吧。好了，废话少说。这次我选择的教程不是先前买的那本《魔力Haskell》了，那确实是本好书，但是我没时间回家取，可能本周末会回家拿这本书，但是就现在而言，我选择的是宾夕法尼亚大学2013年春季的CIS194。众所周知在2016年Joachim Breitner更新了这份教程，但是我简单地翻看了一下，感觉类似Go语言官方给的教程，搭建一个沙盒然后让你在里面随便耍。个人觉得这样子比较适合零编程基础起步，类似趣学指南一样，并不能简明扼要地涉及到一门语言的思想和底层，但确实能够有效的激发兴趣。总之人各有所向，我选择旧版的教程。写这一系列文章的目的并不是为了把整个教学文档翻译一遍，而是更偏向记录我自己在学习中的一些过程。本文将记录我完成的 Homework 1 中的 Validating Credit Card Numbers。先贴原题：你是否想过网站是如何验证你的信用卡号码的？他们并没有查询一个庞大的数据库，也没有使用魔法。事实上，许多信用卡发卡行采用校验和公式来区分有效的信用卡号和一些随机的数字（亦或是错误的输入）。在这一节，你需要实现验证的一些步骤，所列如下：从右边第二个数字起每隔一个都翻倍。例如[1,3,8,6]变成[2,3,16,6]将所有数字相加。注意是数字不是数。因此[2,3,16,6]相加应当是2+3+1+6+6 = 18将和除以十取余数，若为零则卡号是有效的。接上面的例子，10 % 10 = 8，是无效的号码。再贴提示：首先我们需要找到每个数对应的数字。定义如下函数：toDigits :: Integer -> [Integer] toDigitsRev :: Integer -> [Integer]toDigits应当将正整数转换为数字的列表。对于0和负数输入，应当返回一个空列表。toDigitsRev在上面的基础上输出逆序的列表。例如：toDigits 1234 == [1,2,3,4] toDigitsRev 1234 == [4,3,2,1] toDigits 0 == [] toDigits (-17) == []所有数都正确排列后，我们该将他们中的一些翻倍了。定义函数：doubleEveryOther :: [Integer] -> [Integer]需要注意的是该函数从右边起开始翻倍。所以应有如下输出：doubleEveryOther [8,7,6,5] == [16,7,12,5] doubleEveryOther [1,2,3] == [1,4,3]doubleEveryOther函数的输出中混有一位数和两位数，定义如下函数将他们的数字相加求和：sumDigits :: [Integer] -> Integer例如：sumDigits [16,7,12,5] = 1 + 6 + 7 + 1 + 2 + 5 = 22最后将上述功能组合起来，定义函数：validate :: Integer -> Bool这个函数将接受一个信用卡号码，并输出一个布尔值来表明那是否是有效的信用卡号。例如：validate 4012888888881881 = True validate 4012888888881882 = False最后贴我写的代码：module Main where toDigitsRev :: Integer -> [Integer] toDigitsRev n | n >= 10 = (mod n 10) : toDigitsRev (div n 10) | n < 10 && n > 0 = [n] | n <= 0 = [] revIntegerList :: [Integer] -> [Integer] revIntegerList [] = [] revIntegerList (x : zs) = revIntegerList zs ++ [x] toDigits :: Integer -> [Integer] toDigits n = revIntegerList $ toDigitsRev n doubleEveryOtherHelper :: [Integer] -> [Integer] doubleEveryOtherHelper [] = [] doubleEveryOtherHelper (x : []) = [x] doubleEveryOtherHelper (x : (y : zs)) = x : (2 * y) : doubleEveryOtherHelper zs doubleEveryOther :: [Integer] -> [Integer] doubleEveryOther zs = revIntegerList $ doubleEveryOtherHelper $ revIntegerList zs sumDigitsHelper :: Integer -> Integer sumDigitsHelper n | n >= 10 = mod n 10 + sumDigitsHelper (div n 10) | n < 10 = n sumDigits :: [Integer] -> Integer sumDigits [] = 0 sumDigits (x : zs) = sumDigitsHelper x + sumDigits zs validate :: Integer -> Bool validate n = (sumDigits $ doubleEveryOther $ toDigits n) `mod` 10 == 0 main :: IO () main = do putStrLn $ show $ validate 4012888888881881 putStrLn $ show $ validate 4012888888881882 我不大清楚我写的代码是否是符合Haskell规范的最简洁的代码。毕竟折腾了一个半小时，感觉在逻辑上思考问题的方式和C或Java这些语言迥然不同。例如将数字分解成列表，我就是模仿C中的实现思路，先对十取余数，然后再除以十，以此循环，直到原来的数除成零。另外我还对好多函数写了额外的Helper，最明显也是我觉得最不恰当的应该是doubleEveryOther这个函数。这个函数本身很简单，就是把一个数表逆序过来交给Helper处理然后在逆序回来。需要逆序的原因是我需要从前往后处理这个列表，虽然我知道有foldr和foldl这样的存在，但是我并不会用，或者说我也不太清楚CIS194这篇教程是否假定我知道一些Haskell中的基本函数。总之我没有使用那些高级的函数，转而采用一种较为低级的实现。我依稀记得在《魔力Haskell》这本书中提到了fold这一家子函数的具体实现，但是那是年龄尚小、头发尚密，没能理解。或许在今后我学明白那些之后会回过头来把这些再重写得更简洁些，现在，这应当是我能想到的并且不是那么复杂的最好的结果了。下一篇关于Haskell的文章，不出意外的话应当是Homework 1中余下的汉诺塔问题。包括题目中的3根柱子的汉诺塔以及附加的4根柱子的汉诺塔。
本文将在Win10系统上使用Sublime Text 3 搭配插件 SublimeHaskell搭建一个IDE环境。[...]