函数的类型类实例

Question

我正在研究CIS 194的作业问题.
我被困在家庭作业5,问题6.

类型Expr类HasVars用于表示包含变量的任何表达式的表达式和类型类.
该问题要求实现Exprfor 的实例M.Map String Integer -> Maybe Integer,其中M是Data.Map.

class Expr a where 
  add :: a -> a -> a
  mul :: a -> a -> a
  lit :: Integer -> a

下面是实例代码Expr的Integer.

instance Expr Integer where
  add m n = m + n
  mul m n = m * n
  lit m = m 

对于HasVars函数的实例,

instance HasVars (M.Map String Integer -> Maybe Integer) where
   var s  = M.lookup s 

我很困惑如何Expr为函数类型创建实例.如何进行模式匹配或从函数中提取值？类型是a-> a -> a,所以我没有Map提取值和var从ShowVars用于转换String为所述函数.

我没有提出问题的其他部分的解决方案,因为它可能包含剧透.

Answer 1

好吧,首先写出签名,以便清楚应该是什么东西.为了使它更具可读性,

type MS2I = M.Map String Integer
type Integer' = Maybe Integer

然后

add :: (MS2I -> Integer') -> (MS2I -> Integer') -> (MS2I -> Integer')

所以你可以先开始吧

add m n = o
 where m, n, o :: MS2I -> Integer'

这o是一个采用地图的函数......您可以定义:

add m n = o
 where o ms2i = ...

那时你就有了一张地图.您可以将其提供给参数:

add m n = o
 where o ms2i = let i1 = m ms2i
                    i2 = n ms2i
                    i1, i2 :: Integer'
                in ...?   

其余应该是显而易见的,你只需要将两个结合Maybe Integer到一个新的.(最好用Applicative.)

有趣和参考,这是一个超级浓缩版本:

import Control.Arrow
instance Expr (Kleisli Maybe MS2I Integer) where
  add m n = arr (uncurry(+)) . (m&&&n)