如何在不重复自己的情况下使该算法变得更懒惰? [英] How do I make this algorithm lazier without repeating myself?

问题描述

(受到我对这个问题的回答的启发.)

考虑以下代码(应该查找小于或等于给定输入的最大元素):

Consider this code (it's supposed to find the largest element that's less than or equal to a given input):

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

这不是很懒.输入GT大小写后，我们肯定会知道最终的返回值将是Just而不是Nothing，但是Just直到结束才可用.我想制作这个懒惰器，以便在输入GT大小写后立即可以使用Just.我的测试用例是，我希望Data.Maybe.isJust $ closestLess 5 (Node 3 () Leaf undefined)评估为True而不是触底.这是我可以想到的一种方法:

This isn't very lazy. Once the GT case is entered, we know for sure that the final return value will be Just something rather than Nothing, but the Just still isn't available until the end. I'd like to make this lazier so that the Just is available as soon as the GT case is entered. My test case for this is that I want Data.Maybe.isJust $ closestLess 5 (Node 3 () Leaf undefined) to evaluate to True rather than bottoming. Here's one way I can think to do this:

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

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

但是，我现在要重复一遍:closestLess和precise中都包含了核心逻辑.我该怎么写，以免偷懒而不重复我自己?

However, I'm now repeating myself: the core logic is now in both closestLess and in precise. How can I write this so that it's lazy but without repeating myself?

推荐答案

可以使用类型系统，而不是使用显式包装器.请注意，precise的版本将Maybe用于您的第一个代码段:

Rather than use explicit wrappers, you can leverage the type system. Note that the version of precise that uses Maybe for your first code snippet:

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

与第二个代码段中不带Maybe的precise版本几乎完全相同，可以在Identity函子中写为:

is almost exactly the same algorithm as the version of precise without Maybe from your second code snippet, which could be written in the Identity functor as:

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

这些可以在Applicative中统一为一个多态版本:

These can be unified into a version polymorphic in the Applicative:

precise :: (Applicative f) => f (Integer, v) -> TreeMap v -> f (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 -> precise (pure (k, v)) r

就其本身而言，并不能完成很多事情，但是如果我们知道GT分支将始终返回值，则可以强制其在Identity函子中运行，而不管启动函子是什么.也就是说，我们可以从Maybe函子开始，然后递归到GT分支的Identity函子:

By itself, that doesn't accomplish much, but if we know that the GT branch will always return a value, we can force it to run in the Identity functor, regardless of the starting functor. That is, we can start in the Maybe functor but recurse into the Identity functor in the GT branch:

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

这可以很好地与您的测试用例配合使用

This works fine with your test case:

> isJust $ closestLess 5 (Node 3 () Leaf undefined)
True

是多态递归的一个很好的例子.

and is a nice example of polymorphic recursion.

从性能的角度来看，此方法的另一个好处是-ddump-simpl表示没有包装程序或字典.在这两个函子的特殊功能下，所有这些在类型级别上都被删除了:

Another nice thing about this approach from a performance point of view is that the -ddump-simpl shows that there are no wrappers or dictionaries. It's all been erased at the type level with specialized functions for the two functors:

closestLess
  = \ @ v i eta ->
      letrec {
        $sprecise
        $sprecise
          = \ @ v1 closestSoFar ds ->
              case ds of {
                Leaf -> closestSoFar;
                Node k v2 l r ->
                  case compareInteger i k of {
                    LT -> $sprecise closestSoFar l;
                    EQ -> (k, v2) `cast` <Co:5>;
                    GT -> $sprecise ((k, v2) `cast` <Co:5>) r
                  }
              }; } in
      letrec {
        $sprecise1
        $sprecise1
          = \ @ v1 closestSoFar ds ->
              case ds of {
                Leaf -> closestSoFar;
                Node k v2 l r ->
                  case compareInteger i k of {
                    LT -> $sprecise1 closestSoFar l;
                    EQ -> Just (k, v2);
                    GT -> Just (($sprecise ((k, v2) `cast` <Co:5>) r) `cast` <Co:4>)
                  }
              }; } in
      $sprecise1 Nothing eta

这篇关于如何在不重复自己的情况下使该算法变得更懒惰?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！