函数作为haskell中的类型

Question

我使用函数类型混淆了.

假设我想实现一个字典,当给出a和b时返回Maybe b.

type Dict a b = a->Maybe b

如何为此字典实现插入功能？

insertDict :: (Eq a) => a -> b -> (Dict a b)-> (Dict a b)

我想出了以下的事情

insertDict x y mydict = \a->Just y

但它不正确,将丢弃以前的字典.

Answer 1

您可以使用"责任链"模式:insert函数检查结果 的参数是否Dict与其自己的键匹配,否则它会委托前Dict一个作为参数接收的参数.

type Dict a b = a -> Maybe b

insertDict :: (Eq a) => a -> b -> Dict a b -> Dict a b
-- Note that the k' is the argument of the result dict function
insertDict k v dict k' = if k == k' then Just v else dict k'

emptyDict :: Dict a b
emptyDict _ = Nothing

ghci中的一些例子:

? insertDict 'a' (1::Int) emptyDict $ 'a'
Just 1
? insertDict 'b' 2 (insertDict 'a' (1::Int) emptyDict) $ 'a'
Just 1
? insertDict 'b' 2 (insertDict 'a' (1::Int) emptyDict) $ 'x'
Nothing

将地图表示为函数作为第一近似是好的,但是这种表示具有许多缺点:

• 搜索值的复杂性在键的数量上是线性的.
• 函数非常"不透明",这意味着您无法像使用数据类型那样检查或序列化地图.

Answer 2

这是您可以用来帮助自己编写这些函数的一种方法.首先,写下类型签名:

insertDict :: (Eq k) => k -> v -> Dict k v -> Dict k v

我已经使用k并v为"关键"和"价值"这里的清晰度.接下来,首先将实现写为漏洞:

insertDict key value dict
  = _

编译器(或GHCI)应该给你喜欢"发现孔消息:_ :: Dict k v[...]相关的绑定包括:dict :: Dict k v,value :: v,key :: k.所以在这里你看到你可以返回dict因为类型匹配,但那会忽略key和value.

既然你知道这Dict k v是一个函数类型,你可以通过添加一个带有另一个洞的lambda来查看编译器提供的内容:

insertDict key value dict
  = \ key' -> _

现在我们有_ :: Maybe v,value :: v,key' :: k,key' :: k,dict :: Dict k v.我们总是可以返回Just value,但正如您所观察到的那样,这并不能达到我们想要的效果 - 它代表的是一个字典总是回答"是的,那个键在字典中,它的值是value",对于您询问的任何键!(这是一个有用的东西,能够代表,这不是我们正在写的东西.)

所以看起来我们不能只用这些来取得进展 - 但是等等,我们也有一个Eq k约束!而只有两件事情,我们可以比较有key和key',让我们这个扩大到if使用==:

insertDict key value dict
  = \ key' -> if key == key' then _1 else _2

现在编译器报告_1 :: Maybe v和_2 :: Maybe v.我们应该在每种情况下返回什么？让我们考虑如何实际使用此函数的一些示例 - 如果在插入键值对后在字典中查找键,您当然应该找到值:

(insertDict key value dict) key == Just value
                                   ----------

所以_1我们可以写Just value:

insertDict key value dict
  = \ key' -> if key == key' then Just value else _2
                                  ----------

如果您查找与刚刚插入的密钥不同的密钥,则最近插入的键值对无关紧要; 它应该在字典中进一步查找关键字:

(insertDict key value dict) key' == dict key'  -- If key /= key'
                                    ---------

所以_2我们可以写dict key':

insertDict key value dict
  = \ key' -> if key == key' then Just value else dict key'
                                                  ---------

我们完成了!:d

在Haskell中编写时,这种类型导向编程和等式推理的组合非常有用,特别是对于具有有限数量的可能(理智)实现的多态函数.