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

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的值，再进行运算就是了。

练习 2

UI部门已经实现了焦点小组的研究，并且已经准备好和你协同了。他们已经开发了前端用户接口：一个用于解析所选语言的文本解析器。他们发给你了一个模组Parser.hs，其中的parseExp函数用于解析。如果你将ExprT的构造函数作为参数传给它，它则将一个字符串以ExprT类型的算术表达式重新表示。例如¹：

*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 catering
to 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 that

mul (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 Lit

at 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 => a

What 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 = id

To 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 like

reify $ 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类型。

练习 4

The 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:

• Integer

  • works like the original calculator

• Bool

  • every 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 and

• MinMax

  • "addition" is taken to be the max function, while "multiplication" is the min function

• Mod7

  • all 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 Mod7

Try 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 that

stackVM 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 function

compile :: String -> Maybe Program

which 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") :: VarExprT

But 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. Add

import qualified Data.Map as M

at 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，如果有值，那么就取出来看第二个表达式。第二个表达式同理，只有两个都有值时才做运算，并在运算后包装回原来的数据类型。

-全文完-

---

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