所以有时我需要编写一个我在Hackage上找不到的数据结构,或者我发现没有经过测试或质量不足以让我信任,或者只是我不想成为依赖项.我现在正在阅读冈崎的书,它很擅长解释如何设计渐近快速的数据结构.
但是,我正在专门研究GHC.常数因素对我的应用来说是一个大问题.内存使用对我来说也是一个大问题.所以我对GHC有特别的疑问.
特别是
我浏览了网络上的各个地方,我对如何使用GHC 有一个模糊的想法,例如,查看核心输出,使用UNPACK编译指示等.但我不确定我明白了.
所以我弹出了我最喜欢的数据结构库,容器,并查看了Data.Sequence模块.我不能说我理解他们正在做的很多事情,以使Seq快速.
引起我注意的第一件事就是定义FingerTree a.我认为这只是我对手指树不熟悉.引起我注意的第二件事是所有的SPECIALIZEpragma.我不知道这里发生了什么,我很好奇,因为这些都遍布整个代码.
许多函数也有一个INLINE与它们相关的编译指示.我可以猜到这意味着什么,但是如何判断何时INLINE起作用呢？
事情变得非常有趣~~475线,一个被称为"应用建筑"的部分.它们定义了一个newtype包装器来表示Identity monad,它们编写自己的严格状态monad副本,并且它们有一个被定义的函数applicativeTree,它显然专用于Identity monad,这增加了函数输出的共享.我不知道这里发生了什么.什么巫术被用来增加分享？
无论如何,我不确定从Data.Sequence中学到很多东西.是否有其他"模范程序"我可以阅读以获得智慧？我真的很想知道当我真正需要它们更快时,如何更新我的数据结构.有一件事特别是编写使融合变得容易的数据结构,以及如何编写良好的融合规则.
所以我一直在Haskell编写一个计算几何库,因为我在Hackage上找不到一个,而且我觉得无论如何都会很有趣.但是,我已经在一个特定的算法上被困了将近一个星期,我似乎无法进入一个很好的'类似haskell'的形式.该算法是用于在一组线段中找到交叉点的Bentley-Ottmann算法.如果您熟悉算法,可以跳到最后一段为我的求助:)
我选择实现此函数的方式是一个函数,它获取一个线段列表并返回一个点列表,以及在该点相交的线段.这让我们可以处理多个段在同一点相交的情况.
bentleyOttmann :: [Segment] -> [(Point, [Segment])]
该算法是扫描线算法.我们想象一条扫过飞机的线,在不同的点上进行算法工作.Bentley-Ottmann算法中的事件点是:
请注意,事件点可以以多种方式与多个线段相关联.为了跟踪哪些段对应于哪些端点,我使用容器包中的映射.此贴图的关键点是点,值是段的列表,标记为它们是从该点开始,在该点结束还是在该点处相交.
扫描线确定点的顺序.想象一下垂直线扫过飞机,在事件点停下来做功.事件点首先按其x值排序,首先处理较小的点.一般来说,这就是我们所需要的.在退化情况下,事件点可以具有相同的x坐标.我们还按其y坐标排序,如果存在x坐标关系,则首先处理具有较小y坐标的事件点.
所以我自然使用的结构是一个优先级队列.我使用的是来自Hackage的堆包.
我们在每个活动点做的工作是什么？好吧,首先我们检查哪些段与事件点相关联.如果有多个,则为交叉点.我们可以将它添加到目前为止我们找到的交叉点列表中.
这是棘手的部分.当我们扫过飞机时,我们会跟踪一组段,这些段相对于它们与扫描线相交的点排序.当我们处理事件点时,我们首先删除在该事件点结束的所有段.然后,在该点交叉的所有段按顺序颠倒.最后,我们将从该事件点开始的段添加到有序集.注意,由于这些段都在事件点处相交,因此必须针对前方略微扰动的扫描线进行排序.
在每个事件点,我们必须添加任何新的事件点,发生的新交叉点.因为我们跟踪与扫描线相交的段的相对顺序,所以我们做以下两件事之一:
如果我们交换了两个段或添加了一个新段,我们找到最下面的(相对于扫描线)修改的段,最顶层的修改段,并测试它们与它们的直接非修改邻居的交叉点.
如果我们没有交换或添加新的段,那么我们至少会移除一个段,从而使其前邻居现在相邻.我们测试这些新邻居的交叉点.
这是Bentley-Ottmann算法的关键,当我们扫过飞机时,我们只测试与其邻居的新候选区段.这意味着当交叉点相对较少时,我们击败了天真的O(n ^ 2)算法.
我的问题(最后,我很抱歉这是如此啰嗦)是这样的:我不知道如何实现这个排序逻辑.我不能使用Data.Set,因为顺序随着扫描而改变.我正在尝试实现我自己的数据结构以跟踪信息,但它是蹩脚的,错误的,可能是低效的,也是丑陋的!我讨厌丑陋的代码.
我知道Haskell就是漂亮的代码.我也相信如果我不能以一种漂亮的方式实现算法,那就意味着我并不真正理解它.任何人都可以让我深入了解这个算法吗？
编辑:我现在有一个"工作"的实现.我打算使用通用输入,以及在同一点和垂直段相交的多个段.它似乎通过我做的微不足道的测试来处理这些输入.它并没有在段重叠的工作.我不知道如何处理这些问题.我希望得到关于如何容纳它们的意见.目前,我的扫描线结构在同一节点中跟踪它们,但它只会在相交测试中使用其中一个,并且可能会产生不一致的结果.
我使用Data.Set作为我的事件队列,使用Data.Map进行查找,以及使用拉链的红黑树的实现,我在他的书中使用了Okasaki的.如果我的代码段没有足够的上下文,我可以添加更多内容.
我很欣赏关于重组实施的提示,所以它不那么难看.我不知道它是多么正确,它让我感到紧张.
代码可以在hpaste上找到
我现在对箭头机械的其余部分感到相当舒服,但我不知道循环是如何工作的.这对我来说似乎很神奇,这对我的理解不利.我也很难理解mfix.当我查看一个rec在块proc或do块中使用的代码时,我感到困惑.使用常规的monadic或箭头代码,我可以逐步完成计算并保持头脑中正在发生的事情.当我到达时rec,我不知道要保留什么图片!我卡住了,我无法推断这样的代码.
我试图解决的例子来自Ross Paterson关于箭头的论文,关于电路的论文.
counter :: ArrowCircuit a => a Bool Int
counter = proc reset -> do
rec output <- returnA -< if reset then 0 else next
next <- delay 0 -< output+1
returnA -< output
我假设如果我理解这个例子,我将能够理解循环,这将是理解mfix的一个很好的方法.他们对我的感觉基本上是一样的,但也许我有一个微妙的缺失？无论如何,我真正想要的是这些代码片段的操作画面,所以我可以在头脑中像"常规"代码一样介绍它们.
编辑:感谢Pigworker的回答,我开始考虑rec和满足要求.取counter实施例中,REC块的第一行需要一个叫做值output.我想象这可以创建一个盒子,标记它output,并要求rec块填充那个盒子.为了填充该框,我们为returnA提供一个值,但该值本身需要另一个值,称为next.为了使用这个值,必须要求rec块中的另一行,但是现在要求在rec块中的哪个行并不重要.
所以我们转到下一行,我们发现标有框next,我们要求另一个计算填充它.现在,这个计算需要我们的第一个盒子!所以我们给它一个盒子,但它里面没有任何价值,所以如果这个计算需要内容output,我们就会遇到无限循环.幸运的是,延迟占用了盒子,但产生了一个值而没有查看盒子内部.这填补next,然后允许我们填补output.现在output已经填充,当处理该电路的下一个输入时,前一个output框将具有其值,准备被要求以产生下一个next …
我可以使用GHC成功构建与OpenGL链接的可执行文件,但是我无法将软件包加载到GHCi中.这绝对是我的回归,因为它适用于32位GHC(至少我升级的版本).我不认为GHC版本很重要,只是因为我使用的是64位GHC系统.
根据维护者的建议,我明确地将正确的64位版本的opengl32成功引入了GHCi.这似乎是一个更高的问题.
这是相关的输出.不幸的是,详细输出同样具体.函数wglGetProcAddress用于查找opell api挂钩在dll中的位置.
$ ghcii.sh -package OpenGL
GHCi, version 7.6.1: http://www.haskell.org/ghc/ :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Loading package OpenGLRaw-1.2.0.0 ... linking ... ghc.exe: unable to load package `OpenGLRaw-1.2.0.0'
ghc.exe: C:\...\cabal\OpenGLRaw-1.2.0.0\ghc-7.6.1\HSOpenGLRaw-1.2.0.0.o: unknown symbol `__imp_wglGetProcAddress'
我正在寻找一个库来在GLFW和OpenGL之上编写GUI.我这样做是因为我对常见的UI库绑定不满意,我认为这些绑定太过于必要,而且我也希望严格控制UI的外观和感觉.我想要一种定义UI的声明方法.我正在尝试使用反应性香蕉(以及临时反应性香蕉-wx)来确定它是否符合我的需求.我在定义递归小部件时遇到问题.这是我最简单的测试用例:
第一个和第三个小部件具有递归关系.第一个小部件直观地是从两个按钮馈送的事件中stepper的一个union.但是,重置按钮是fmap计数器的一个,然后事件流依赖于重置按钮!什么是要做？
除了这个问题,我还关注事件处理:由于我想在我的代码中处理设备输入和输入焦点而不是依赖于框架,我发现在以可伸缩的方式正确调度事件方面存在困难.理想情况下,我将定义一个data封装窗口小部件的层次结构,一种在元素之间安装事件回调的方法,然后编写遍历该数据结构的函数,以便定义设备输入处理和图形输出.我不确定如何获取事件流并将其拆分为可以合并事件流.
由于Data.List提供了这些函数,我对Sequence类型的接口中缺少这些函数感到困惑.这里是否存在效率问题,或者仅仅缺乏对这些功能的需求？
由于它们不属于Data.Sequence,我如何才能有效地实现它们？
这个问题困扰着我.我正在测试一些Haskell绑定到OpenGL,我创建了一个顶点着色器,一个片段着色器,编译程序,并在转换顶点后在屏幕上绘制一个纹理矩形......除了屏幕是空白的.
当我渲染矩形平白而不是在片段着色器中使用采样器时,它工作正常.当我进入gdebugger并使用选项将所有纹理替换为存根纹理时,它也可以正常工作.
当我在gdebugger中查看分配的纹理时,没有纹理对象,只有默认的2d纹理.当我在glTexImage2d上设置断点时,我看到它被调用了,但是当我用gdebugger查看它时,内存中没有纹理对象出现.
这是怎么回事？我忘了设置一些环境变量吗？我很沮丧.踢球者之前我遇到过这个问题,然后我设法解决了这个问题,但我忘记了问题所在.我讨厌自己> _>