识别函数不会生成特定输出的输入值 [英] Identifying input values for which a function does NOT generate a specific output

问题描述

我建立了一个函数形式的数据结构，输出某些字符串以响应某些输入字符串，如下所示：

 键入mydict = String  - >字符串
 
 emptydict :: mydict 
 emptydict _ =未找到
  

  addentry :: String  - >现在我可以通过以下操作将条目添加到此字典中：字符串 - > mydict  - > mydict 
 addentry s1 s2 d s 
 | s1 == s = s2 
 |否则= ds 
  

要查找s2，我只需输入s1并查看我的字典

  looky :: String  - > mydict  - >字符串
 looky s1 d = d s1  - 赠送s2 
  

我的目标是创建另一个函数 patternmatch ，其中我可以检查哪些s1与以特定模式开始的s2相关联。现在模式匹配本身不是问题，但我不知道如何跟踪我输入的条目，即哪个输入是输出而不是not found？

我的想法是试着跟踪我在 addentry 函数中输入的所有s1，并将它们添加到一个单独的列表。在 patternmatch 中，我会将列表元素提供给 looky ，这样我就可以取回关联的s2并检查它们是否是他们匹配模式。

所以我的问题：

1）这个列表建立的方法是否好，还是有更好的方法来识别2）如果它是一个函数被定义为未找到？

正确的做法，我将如何跟踪S1的？我在想：

  addentry s1 s2 d s 
 |最后（保存s1）== s = s2 
 |否则= d s1 
  

然后保存s1 是一个用所有s1生成列表的函数。然后 last（save s1）会返回最近的 s1 。希望在执行保存s1 或者从这里开始的其他路线的帮助。非常感谢。

解决方案

您的设计是硬编码的，因此找到关键字的唯一标准是通过呈现相同的准确键。您需要的是一种更灵活的方法，可以让您提供除平等以外的标准。我冒昧地让你的代码更加通用，并且为这些函数使用更传统的名称：
$ b $ pre $ import $ Prelude hiding（lookup）

- 而不是k - >也许v，我们将字典表示为
- （k - > Bool） - >可能v其中k - > Bool是标准
- 用于匹配密钥。通过使用Maybe v，我们可以发出
的信号 - 通过返回Nothing
- 而不是找到
newtype Dict kv = Dict（（k - > Bool ） - >可能v）

空:: Dict kv
空= Dict $ const Nothing

- 插入一个新的键/值对
insert :: k - > v - > Dict k v - > Dict k v
insert k v d = Dict $ \f - >如果f k，那么Just v else lookupBy f d

- 使用给定标准查找
lookupBy ::（k - > Bool） - > Dict k v - >可能v
lookupBy f（Dict d）= d f

- 使用默认条件查找（与给定键相等）
lookup :: Eq k => k - > Dict k v - >也许v
lookup k = lookupBy（k ==）

- 您的标准
startsWith :: String - >字符串 - > Bool
startsWith s = undefined - TODO

lookupByPrefix :: String - >字典字符串v - >也许v
lookupByPrefix = lookupBy。 startsWith

我应该提到，虽然这对于函数式编程实践和一般大脑扩展来说是一个很好的练习，这是实施地图的一种可怕方式。

作为一个方面说明，我们可以很容易地定义一个 Functor 对于这种类型：



  instance Functor（Dict k）其中
 fmap fd = Dict $ \g  - > fmap f（lookupBy g d）
  




I built a data structure in form of a function that outputs certain strings in response to certain input strings like this:

type mydict = String -> String

emptydict :: mydict
emptydict _ = "not found"

Now I can add entries into this dictionary by doing the following:

addentry :: String -> String -> mydict -> mydict
addentry s1 s2 d s 
| s1 == s = s2
| otherwise = d s

To look for s2's I can simply enter s1 and look in my dictionary

 looky :: String -> mydict -> String
 looky s1 d = d s1  --gives s2

My goal is now to create another function patternmatch in which I can check which s1's are associated with an s2 that starts with a certain pattern. Now the pattern matching itself isn't the problem, but I am not sure how can I keep track of the entries I entered, i.e. for which input is the output not "not found" ?

My idea was to try to keep track of all the s1's I entered in the addentry function and add them to a separate list. In patternmatch I would feed the list elements to looky, such that I can get back the associated s2's and check whether they match the pattern.

So my questions:

1) Is this list building approach good or is there a better way of identifying the inputs for which a function is defined as something other than "not found"?

2) If it is the right approach, how would I keep track of the s1's? I was thinking something like:

addentry s1 s2 d s
| last (save s1) == s = s2
| otherwise = d s1

And then save s1 being a function generating the list with all s1's. last (save s1) would then return the most recent s1. Would appreciate any help on implementing save s1 or other directions going from here. Thanks a lot.

解决方案

Your design is hard-coded such that the only criteria for finding a key is by presenting the same exact key. What you need is a more flexible approach that lets you provide a criteria other than equality. I took the liberty of making your code more general and using more conventional names for the functions:

import Prelude hiding (lookup)

-- instead of k -> Maybe v, we represent the dictionary as
-- (k -> Bool) -> Maybe v where k -> Bool is the criteria
-- on which to match the key. by using Maybe v we can signal
-- that no qualifying key was found by returning Nothing
-- instead of "not found"
newtype Dict k v = Dict ((k -> Bool) -> Maybe v)

empty :: Dict k v
empty = Dict $ const Nothing

-- insert a new key/value pair
insert :: k -> v -> Dict k v -> Dict k v
insert k v d = Dict $ \f -> if f k then Just v else lookupBy f d

-- lookup using the given criteria
lookupBy :: (k -> Bool) -> Dict k v -> Maybe v
lookupBy f (Dict d) = d f

-- lookup using the default criteria (equality with some given key)
lookup :: Eq k => k -> Dict k v -> Maybe v
lookup k = lookupBy (k==)

-- your criteria
startsWith :: String -> String -> Bool
startsWith s = undefined -- TODO

lookupByPrefix :: String -> Dict String v -> Maybe v
lookupByPrefix = lookupBy . startsWith

I should mention that while this is a great exercise for functional programming practice and general brain-expansion, it's a terrible way to implement a map. A list of pairs is equivalent and easier to understand.

As a side note, we can easily define an instance of Functor for this type:

instance Functor (Dict k) where
  fmap f d = Dict $ \g -> fmap f (lookupBy g d)

这篇关于识别函数不会生成特定输出的输入值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！