在Haskell树中查找最接近整数参数的键 [英] Find keys closest to an integer argument in Haskell tree

问题描述

有很多解决方案，如何以命令式语言在二叉树中查找最接近的上下键，但是在像Haskell这样的纯函数样式中进行操作时，缺少相同的问题.我很好奇，想知道在遇到两个最接近的键之前如何绕过二叉树.到目前为止，有一个功能和一些模式匹配:

There is a plenty of solutions how to find closest lower and upper keys in binary tree in imperative languages, but a lack of same questions for doing it in purely functional style like that of Haskell. I'm curious to learn how it's possible to walk around a binary serch tree ahead of meeting both closest keys. There is a function and some pattern matches I've so far:

data TreeMap v = Leaf | Node { pair::(Integer, v), l::TreeMap v, r::TreeMap v} deriving (Show, Read, Eq, Ord)

closestLess :: Integer -> TreeMap v -> (Integer, v)
closestLess i Leaf = error "Tree doesn't include any element"
closestLess i (Node pair tree_r tree_l)
        | i < fst pair = closestLess i tree_l
        | i == fst pair = closestLess i tree_r
        | otherwise = precise i pair tree_r 

我使用此函数来获取一个较低的键，但最接近Integer参数.我认为，除了实现精确"之类的辅助功能外，没有什么必要，尽管我对它确切需要什么定义感到困惑.我的建议是将整数值节点放入精确"右子树中，以找到最接近目标的任何键.因此，我将有一些技巧或假设，也适用于上下键.

I use this function to get a lower key, but closest to an Integer argument. In my opinion, there is nothing but necessity to implement some auxiliary function like "precise", although I'm confused what definition it needs exactly. My suggestion is to put that Integer value, node into "precise", right subtree also to find any key which is just closest one to the target. Therefore I would have some tips or assumptions how to make it for lower and upper keys as well.

推荐答案

这是我的处理方式:

data TreeMap v = Leaf | Node Integer v (TreeMap v) (TreeMap v) deriving (Show, Read, Eq, Ord)

closestLess :: Integer -> TreeMap v -> Maybe (Integer, v)
closestLess i = precise Nothing where
  precise :: Maybe (Integer, v) -> TreeMap v -> Maybe (Integer, v)
  precise closestSoFar Leaf = closestSoFar
  precise closestSoFar (Node k v l r) = case i `compare` k of
    LT -> precise closestSoFar l
    EQ -> Just (k, v)
    GT -> precise (Just (k, v)) r

有关此尝试与您尝试之间的区别的一些注意事项:

A few notes regarding the differences between this and your attempt:

• 您为Node构造函数使用了记录语法.在总和类型上使用记录语法是一种不好的形式，因为函数将是部分的(例如，pair Leaf将是底部).由于您实际上并没有使用它们，因此也没有必要，因此我将其删除.
• 您将键和值包装在一个元组中，没有明显的原因.我将它们分离出来，然后将它们直接放在类型中.
• 您的closestLess函数的返回类型为(Integer, v)，即使它不能总是返回该类型的东西.我将其更改为Maybe (Integer, v)，以便它可以返回Nothing，而不必使用error. (旁注:您的错误消息在技术上是错误的.如果您调用closestLess，其中搜索值小于所有节点，那么即使树中确实包含元素，它也会失败.)
• 您的代码在节点的左侧和右侧是不一致的.在我的代码中，左侧分支始终是数据构造函数中左侧的分支.
• 您在单独的防护罩中使用了i < fst pair和i == fst pair.通过对compare的输出进行大小写匹配，您只需进行一次比较即可，而无需进行两次比较.
• 您需要使用precise函数的方向正确，但是实际上需要包含在closestLess中的很多逻辑.

• You used record syntax for the Node constructor. It's bad form to use record syntax on sum types, since the functions would then be partial (for example, pair Leaf would be bottom). Since you didn't actually use these and they're not necessary, I removed them.
• You wrapped the key and value in a tuple, with no apparent reason why. I separated them out and placed them directly in the type.
• Your closestLess function had a return type of (Integer, v), even though it couldn't always return something of that type. I changed it to Maybe (Integer, v), so that it can return Nothing instead of having to use error. (Side note: your error message was technically wrong. If you called closestLess where the search value is smaller than all of the nodes, it would fail even though the tree did have elements.)
• Your code is inconsistent as to which is the left and which is the right branch of the nodes. In my code, the left branch is always the one that's on the left in the data constructor.
• You used i < fst pair and i == fst pair in separate guards. By case-matching on the output of compare instead, you only have to do the comparison once instead of twice.
• You were on the right track with needing a precise function, but a lot of the logic that you had in closestLess actually needed to be in it.

这是一个快速的测试案例，使用您链接的站点上的示例:

Here's a quick test case, using the example at the site you linked:

Prelude> tree = Node 9 () (Node 4 () (Node 3 () Leaf Leaf) (Node 6 () (Node 5 () Leaf Leaf) (Node 7 () Leaf Leaf))) (Node 17 () Leaf (Node 22 () (Node 20 () Leaf Leaf) Leaf))
Prelude> closestLess 4 tree
Just (4,())
Prelude> closestLess 18 tree
Just (17,())
Prelude> closestLess 12 tree
Just (9,())
Prelude> closestLess 2 tree
Nothing

---

您还可以使其变得更懒惰(一旦找到一个候选者，立即生成外部Just)，但会变得更加复杂:

---

You can also make it lazier (yielding the outer Just as soon as a single candidate is found), at the expense of being a bit more complex:

import Data.Functor.Identity

data TreeMap v = Leaf | Node Integer v (TreeMap v) (TreeMap v) deriving (Show, Read, Eq, Ord)

closestLess :: Integer -> TreeMap v -> Maybe (Integer, v)
closestLess i = precise Nothing
  where
    precise :: Applicative t => t (Integer, v) -> TreeMap v -> t (Integer, v)
    precise closestSoFar Leaf = closestSoFar
    precise closestSoFar (Node k v l r) = case i `compare` k of
      LT -> precise closestSoFar l
      EQ -> pure (k, v)
      GT -> pure . runIdentity $ precise (Identity (k, v)) r

有关此问题的详细信息，请参见我对此的疑问.

See my question about this for more details about it.

这篇关于在Haskell树中查找最接近整数参数的键的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！