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

December 23, 2018 • Read: 1913 • 瞎折腾

CIS194 Spring13的Homework 5,有关类型类(typeclass)的作业。

  • 你应当提交一个Calc.hs的文件,同时文件中应当包含一个同名的模块(module)。

如我们在课上所见,Haskell的类型类提供了特殊的多态性(ad-hoc polymorphism),即能够根据输入的类型决定做什么。 这次作业探讨了在构建特定领域语言(domain-specific languages)时类型类的一个有趣用法。


假设有一天你的新工作是一个软件工程师,你被要求为公司的新重磅产品编程:一个计算器。但这不只是一个普通的计算器!广泛的焦点小组(Extensive focus group)分析表明,人们真正想让他们的计算器拥有的功能无非是能够做整数加法和乘法。额外的功能只会让界面变得更杂乱。


data ExprT = Lit Integer
           | Add ExprT ExprT
           | Mul ExprT ExprT
  deriving (Show, Eq)

这个类型能够兼容涉及到整数常量、加法、乘法的算术表达式。例如表达式 $(2+3)\times4$ 应该能够表示成:Mul (Add (Lit 2) (Lit 3)) (Lit 4)


练习 1


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



练习 2


*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*"


evalStr :: String -> Maybe Integer

该函数对一个字符串类型的算术表达式求值,如果输入的字符串是无效的,那么输出Nothing,如果输入有效,就输出Just nn是输入所对应的值。


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的判断有更好的函数,例如isNothingfromMaybe,但是我总觉得对于本题模式匹配更简单吧。如果是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。而addmul则接受两个类型相同的表达式,做出计算并封装回原来的类型,因此上述两个函数应当是a -> a -> a


练习 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,因此使用idaddmul就是整数的运算。


关于MinMax类型,lit函数就相当于MinMax的构造函数,因为其本质还是整数,所以不需要额外的转换。加法和乘法都使用了模式匹配,将MinMax里面包含的整数直接取出来,进行相应运算之后再调用lit包装回MinMax类型。此处利用了Haskell的类型推断:对于该add实现,应该是MinMax -> MinMax -> MinMax,因而Haskell会自动找到返回值是MinMaxlit实现,而不会导致错误。


*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。而加法和乘法则是默认对栈顶的两个数字操作,因此实现就是先把要操作的两个数字放在栈顶,而对于两个列表,每个列表如果正确的话执行完后将会把结果放在栈顶,后续操作的结果会摞在原先的栈顶上。因此ab分别代表两个程序列表,执行后就相当于[PushI x, PushI y],其中xy分别就是ab执行后的结果。最后连接上对应的操作即可。

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")
*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


然后具体的VarExprT类型,除了包含ExprT的三个构造函数之外,还应该有一个额外的处理变量的构造函数,即Var String



后面关于两个函数类型的实例,其中HasVars就是一个查询。(M.Map String Integer -> Maybe Integer)是给定一个映射表要返回一个可能的整数,而要M.lookup加上一个字符串,剩下的刚好就是这个,即给定一个要查询的变量名,返回一个接收映射表(即从哪查询)并返回查到的数值(有就是Just,没有就是Nothing)。下面的Expr同理。



  1. 这里的显示的代码是在GHCi中执行的。进入GHCi后使用:l [filename]加载对应的文件,此处应该是:l Calc.hs或者直接省略.hs直接使用模组名。加载成功后当前光标所在行应当以*Calc>开头,随后可以复制粘贴对应代码框中*Calc>后面的代码,在GHCi中运行即可。其中偶数行代表执行上一行代码后的输出。

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

Last Modified: December 24, 2018
Archives QR Code
QR Code for this page
Tipping QR Code
Leave a Comment

已有 1 条评论
  1. 好长,我居然看完了qwq