小编Kra*_*ntz的帖子

我实现了一种算法，在其中使用了优先级队列。我受到这个问题的启发： Transform a std::multimap into std::priority_queue

我将存储多达 1000 万个具有特定优先级值的元素。

然后我想迭代直到队列为空。每次检索元素时，它也会从队列中删除。

在此之后，我重新计算元素优先级值，因为之前的迭代它可以改变。

如果值确实增加了，我将再次将元素插入队列中。这种情况更常发生，取决于进度。（前 25% 不会发生，接下来的 50% 会发生，最后 25% 会发生多次）。

接收到下一个元素并且不重新插入后，我将对其进行处理。这对于 I 不需要此元素的优先级值，而是此元素的技术 ID。

这就是我直觉地选择 astd::multimap来实现这一点的原因，.begin()用于获取第一个元素，.insert()插入并.erase()删除它。此外，我没有直观地std::priority_queue直接选择，因为本主题的其他问题回答std::priority_queue最有可能仅用于单个值而不是映射值。

阅读上面的链接后，我使用优先级队列类似于链接中的另一个问题重新实现了它。我的运行时间似乎并没有那么不平等（在 10 个 mio 元素上大约一个小时）。现在我想知道为什么std::priority_queue更快。

std::multimap由于多次重新插入，我实际上希望更快。也许问题是multimap的重组太多了？

假设我有一个多参数类型类:

class B b => C a b | a -> b where
    getB :: a -> (T, b)

然后我想要一个功能:

f :: C a b => a -> c
f = g . getB

它使用其他功能g :: B b => (T, b) -> c和getB,因此一个实例C a b是必要的.

(免责声明:真正的问题要复杂得多,上面提到的只是简化版.)

问题是,鉴于功能依赖性C a b | a -> b,我们知道b可以完全决定a,所以理论上我应该可以不提b类型f(因为它不在别处使用,但在实例中C a b),但我没有发现任何实现这一目标的方法.

还要注意,由于B b类中存在约束C,我认为我不能使用TypeFamilies扩展,因为它的语法无法使类型约束生效B …

这可能与功能数据结构有关，但我没有找到有关此主题的标签。

假设我有一个语法树类型Tree，它通过简单地共享公共子表达式来组织为 DAG。例如，

data Tree = Val Int | Plus Tree Tree

example :: Tree
example = let x = Val 42 in Plus x x

然后，在这个语法树类型上，我有一个纯函数simplify :: Tree -> Tree，当给定 a 的根节点时，它Tree通过首先简化该根节点的子节点来简化整个树，然后处理根节点本身的操作。

由于simplify是纯函数，并且某些节点是共享的，因此我们希望不会simplify在这些共享节点上多次调用。

问题来了。整个数据结构是不变的，共享对程序员是透明的，因此似乎无法确定两个节点是否实际上是同一个节点。

在处理所谓的“打结”结构时也会出现同样的问题。通过打结，我们为原本无限的数据结构生成了有限的数据表示，例如let xs = 1 : xs in xs。这里xs本身是有限的，但调用map succ它并不一定会产生有限的表示。

这些问题可以归结为：当数据被组织在一个不变的有向图中时，我们如何避免重新访问同一个节点，做重复的工作，甚至在图恰好是循环的时候导致不终止？

我想到的一些想法：

1. 将Tree类型扩展为Tree a，使每个节点都拥有一个额外的a. 生成图形时，将每个节点与一个唯一a值相关联。尽管垃圾收集器可能随时移动任何堆对象，但内存地址应该在这里有效。
2. 对于语法树示例，我们可能会STRef (Maybe Tree)在简化版本的每个节点中存储 …

根据Haskell Wiki，在 Haskell FFI 中，我们可以使用“wrapper”包装器从 Haskell 函数中创建一个 C 函数：

foreign import ccall "wrapper" createFunPtr :: (Int -> Int) -> IO (FunPtr (Int -> Int))

如果我理解正确的话，这意味着f <- createFunPtr (+ 42)在-block 中给出了C类型的do函数指针。fint (*)(int)

在 Haskell 中，类型的函数Int -> Int内部可能有一些本地绑定（例如 lambda 表达式可能引用外部作用域中的变量），而在 C 中，函数指针仅仅是函数的内存地址，调用这些函数指针只是类似于原始跳跃的东西。因此 Haskell 函数的附加数据没有其他地方可以存放FunPtr。

C++ 中的 Lambda 表达式是对象，调用它们会传递operator()隐式this指针。但是FunPtrs 的处理方式与 C 中的普通函数指针一样，因此不可能传递一些额外的参数。

那么GHC是如何实现这个“wrapper”包装器的呢？（我猜测可能是通过直接向内存中的代码部分写入指令来传递额外的参数来实现的，但我记得代码部分通常是只读的。）

lambda 表达式（作为返回值）中的按值捕获 ( [x]) （或 C++14 移动捕获[x = std::move(x)]）中的复制（移动）构造是否可能（或保证）被省略？

auto param_by_value(Widget w) {
    // manipulating w ...
    return [w] { w.doSomeThing(); };
}
auto param_by_move(Widget w) {
    // manipulating w ...
    return [w = std::move(w)] { w.doSomeThing() };
}
auto local_by_value() {
    Widget w;
    // manipulating w ...
    return [w] { w.doSomeThing(); };
}
auto local_by_move() {
    Widget w;
    // manipulating w ...
    return [w = std::move(w)] { w.doSomeThing() };
}

我的问题是：

1. 上述函数中的复制（移动）是否w可能（甚至保证）被省略？（我记得显式std::move有时会阻止复制省略，并且参数的复制/移动是不可能被省略的。） …

我尝试使用Agda 2.6.1.3和Agda stdlib 1.5编译hello-world示例。下面是代码：

module hello-world where

open import IO

main = run (putStrLn "Hello, World!")

用Agda( agda --compile hello-world.agda)编译时，报如下错误：

Unsolved metas at the following locations:
  $HOME/hello-world.agda:5,8-11

报告的位置 ( 5,8-11) 对应于 token run。

我在 Agda 和 Agda-stdlib Issues 中都没有找到任何相关信息，在 SO 或其他网站上也没有找到任何相关信息。文档是否已过时，或者我是否犯了任何错误？

笔记：

• Agda 编译器是通过stack install Agda解析器安装的lts-17.5。
• 我还尝试从 GitHub 源（分支）手动编译release-2.6.1.3。
• 在$HOME/.agda/libraries我有：

  $HOME/agda-stdlib/standard-library.agda-lib
  

  Run Code Online (Sandbox Code Playgroud)
• 在$HOME/.agda/defaults我有：

  standard-library
  

  Run Code Online (Sandbox Code Playgroud)