Haskell似乎有几种现成的优先级队列实现.例如,有:
两者似乎都是纯优先级队列数据结构.前者基于手指树,这是一种我不熟悉的数据结构; 后者是Data.Map的包装器.还有
它定义了纯功能堆数据结构,从中可以轻松地创建优先级队列..还有
它们都使用Brodal/Okasaki数据结构实现纯功能可融合堆,我认为这类似于非纯函数域中的二项式堆数据结构.
(哦,还有
它的功能对我来说不清楚,但它似乎与monad相关的构建优先级队列,并且无论如何似乎都建立在Data.Map之上.在这个问题中,我关注纯粹的功能优先级队列,所以我认为priority-queue-0.2.2包是无关紧要的.但如果我错了,请纠正我!)
对于我正在构建的项目,我需要一个纯函数优先级队列数据结构.我想知道是否有人可以提供任何智慧的话语,因为我决定了hackage提供的财富的尴尬.特别:
在Windows下的Haskell中使用控制台I/O来处理Unicode字符似乎相当困难.这是悲惨的故事:
SetConsoleCPwin32命令.(那么你需要绑定到Win32库.)或者,如果您不想这样做,您可以期望程序的用户为您更改代码页(然后他们必须chcp在运行您之前调用命令程序).WriteConsoleW.在这里,您可以直接向窗口发送UTF16,这使得它很愉快:没有编码不匹配的危险,因为Windows 总是希望UTF16具有这些功能.不幸的是,这些选项都不适用于Haskell.首先,我知道没有使用选项B的库,所以这并不容易.这留下了选项A.如果你使用Haskell的I/O库(putStrLn等等),这就是库的功能.在现代版本的Haskell中,它会仔细询问windows当前代码页是什么,并以正确的编码输出字符串.这种方法存在两个问题:
chcp cp65001在他们运行您的程序之前(您可能会发现强迫您的用户执行此操作令人反感).或者你需要绑定SetConsoleCP并在程序中执行等效操作(然后使用hSetEncoding以便Haskell库使用新编码发送输出),这意味着你需要包装win32库的相关部分以使它们可见Haskell .上面列出的错误仍未解决,并列为低优先级; 基本结论是选项A(在我上面的分类中)是不可行的,需要切换到选项B以获得可靠的结果.目前尚不清楚解决这个问题的时间表是什么,因为它看起来像是一些相当大的工作.
问题是:与此同时,任何人都可以建议一种解决方法,允许在Windows下的Haskell中使用Unicode控制台I/O.
另请参阅此python错误跟踪器数据库条目,解决Python 3中的相同问题(已提出修复,但尚未被接受到代码库中),以及此stackoverflow答案,为Python中的此问题提供了一种解决方法(基于'选项B'在我的分类中).
我知道memoization似乎是关于堆栈溢出的haskell标记的一个常年话题,但我认为这个问题以前没有被问过.
我知道几个不同的'现成'Haskell的memoization库:
Cmpfor Hashable和Data.Mapfor Data.HashMap和添加appropraite imports,你得到一个基于哈希的版.)但是,我不知道任何基于对象标识而不是对象值查找答案的库.这可能很重要,因为有时用作备忘录表的键的对象类型(即,作为被记忆的函数的输入)可能很大---如此之大以至于完全检查对象以确定是否之前看到它本身就是一个缓慢的操作.慢,而且也没有必要的,如果你将一次又一次地施加memoized函数被存储在给定的"位置在存储器"的对象1.(例如,如果我们正在记忆一个函数,这个函数是在一些具有大量结构共享的大型数据结构上递归调用的.)如果我们之前已经在那个确切的对象上计算了memoized函数,我们可以已经知道了答案,即使没有看对象本身!
实现这样的memoization库涉及一些微妙的问题,并且正确地执行它需要语言的几个特殊支持.幸运的是,GHC提供的特殊功能,我们需要的,是有纸的佩顿-琼斯,马洛和Elliott基本上担心这些问题多数为你解释如何建立一个坚实的实现.他们没有提供所有细节,但他们接近了.
我可以看到哪一个可能应该担心的细节,但是他们不担心的是线程安全---他们的代码显然根本不是线程安全的.
我的问题是:有没有人知道一个打包的库,它在Peyton-Jones,Marlow和Elliott论文中讨论了那种记忆,填写了所有的细节(最好还填写了适当的线程安全性)？
如果做不到这一点,我想我将不得不自己编写代码:是否有人对其他细微之处(除了线程安全和论文中讨论的内容)有任何想法,这样的库的实现者会记住哪些？
UPDATE
按照@ luqui的建议,下面是关于我面临的确切问题的更多数据.我们假设有一种类型:
data Node = Node [Node] [Annotation]
这种类型可以用来表示内存中一种简单的有根DAG,其中Nodes是DAG节点,root只是一个区分Node,每个节点都注明了一些Annotations,我认为其内部结构不需要关注我们(但是如果它很重要,那就问一下,我会更具体.)如果以这种方式使用,请注意Node内存中的s 之间可能存在显着的结构共享- 可能会有指数级的路径从根到a节点比节点本身.我从一个外部库中获得了这种形式的数据结构,我必须与它接口; 我无法更改数据类型.
我有一个功能
myTransform : Node -> Node
细节不需要我们关注(或者至少我是这么认为的;但如果需要的话,我可以更具体).它将节点映射到节点,检查它给出的节点的注释,以及它的直接子节点的注释,以提出Node具有相同子节点但可能具有不同注释的新节点.我想写一个函数
recursiveTransform : Node -> Node
其输出与数据结构"看起来一样",就像你做的那样:
recursiveTransform Node originalChildren annotations = …我有一个关于bytestring库中的Data.ByteString.Lazy.Char8库的问题.具体来说,我的问题涉及readFile函数,其记录如下:
将整个文件懒惰地读入ByteString.在Windows上使用"文本模式"来解释换行符
我对声称此功能将"在Windows上使用文本模式来解释换行符"感兴趣.该函数的源代码如下:
-- | Read an entire file /lazily/ into a 'ByteString'. Use 'text mode'
-- on Windows to interpret newlines
readFile :: FilePath -> IO ByteString
readFile f = openFile f ReadMode >>= hGetContents
我们看到,从某种意义上说,文档中的声明是完全正确的:使用了openFile函数(而不是openBinaryFile),因此将为文件启用换行转换.
但是,该文件将被传递给hGetContents.这将调用Data.ByteString.hGetNonBlocking(参见此处和此处的源代码),这是一个非阻塞版本Data.ByteString.hGet(参见文档); 和(最后)Data.ByteString.hGet调用GHC.IO.Handle.hGetBuf(参见文档或源代码).这个函数的文档说明了这一点
hGetBuf忽略Handle当前使用的任何TextEncoding,并直接从底层IO设备读取字节.
这表明我们使用readFile而不是readBinaryFile无关紧要地打开文件的事实:尽管在问题开头提到的文档中提出了索赔,但数据将在不改变换行符的情况下被读取.
那么,问题的核心:1.我错过了什么吗？是否有一种意义上的声明'那个Data.ByteString.Lazy.Char8.readFile在Windows上使用文本模式来解释换行符'是真的吗？或者文档只是误导？
PS测试还表明,这个功能,至少在我使用它时天真地使用,在Windows上没有换行转换.
我想写一个python程序,它读取包含unicode文本的文件.这些文件通常用UTF-8编码,但可能不是; 如果不是,则将在文件的开头显式声明备用编码.更确切地说,它将使用与Python本身使用的完全相同的规则来声明,以允许Python源代码具有显式声明的编码(如在PEP 0263中,请参阅https://www.python.org/dev/peps/pep- 0263 /更多细节).为了清楚起见,正在处理的文件实际上并不是python源,但它们确实使用相同的规则声明了它们的编码(当不是UTF-8时).
如果在打开文件之前知道文件的编码,Python提供了一种非常简单的方法来自动解码文件:codecs.open命令; 例如,有人可能会:
import codecs
f = codecs.open('unicode.rst', encoding='utf-8')
for line in f:
print repr(line)
line我们进入循环的每一个都是一个unicode字符串.是否有一个Python库做类似的事情,但根据上面的规则选择编码(我认为这是Python 3.0的规则)？(例如,Python是否公开了'使用自我声明编码的'读取文件'来读取语言的来源？)如果没有,那么实现所需效果的最简单方法是什么？
一种想法是使用通常打开文件open,读取前两行,将它们解释为UTF-8,使用PEP中的regexp查找编码声明,如果找到一个使用声明的编码开始解码所有后续行.为了确保这一点,我们需要知道,对于Python在Python源代码中允许的所有编码,通常的Python readline会正确地将文件拆分成行 - 也就是说,我们需要知道Python允许的所有编码Python源代码,字节串'\n'总是真正意味着换行符,并不是编码另一个字符的多字节序列的一部分.(事实上我也需要担心'\ r \n'.)有人知道这是否属实？文档不是很具体.
另一个想法是查看Python源代码.有谁知道在Python源代码中源代码编码处理的位置是什么？
众所周知,实现Haskell类型类的一种方法是通过'类型类词典'.(这当然是ghc中的实现,尽管我强制要求其他实现是可能的.)为了解决这个问题,我将简要介绍一下这是如何工作的.类声明就像
class (MyClass t) where
test1 :: t -> t -> t
test2 :: t -> String
test3 :: t
可以机械地转换为数据类型的定义,如:
data MyClass_ t = MyClass_ {
test1_ :: t -> t -> t,
test2_ :: t -> String,
test3_ :: t,
}
然后我们可以将每个实例声明机械地转换为该类型的对象; 例如:
instance (MyClass Int) where
test1 = (+)
test2 = show
test3 = 3
变成
instance_MyClass_Int :: MyClass_ Int
instance_MyClass_Int = MyClass_ (+) show 3
类似地,具有类型类约束的函数可以变成一个带有额外参数的函数; 例如:
my_function :: (MyClass t) => t -> String
my_function …有谁知道在Haskell中是否可以进行无锁编程？我对于是否有适当的低级基元是否可用以及(如果有的话)关于在纯函数上下文中使用这些基元来构建工作大规模系统的任何信息感兴趣.(我以前从未在纯函数上下文中完成无锁编程.)例如,据我所知,Control.Concurrent.Chan通道是建立在MVars之上的,据我所知,它使用了锁 - - 原则上可以构建Chan原语的版本,这些版本在内部是无锁的吗？希望获得多少性能提升？
我也shoudl说,我熟悉TVars的存在,但并不了解其内部实现---我一直在考虑要明白,他们大多是无锁的,但我不知道,如果他们完全锁定免费.所以关于TVars内部实现的任何信息也会有所帮助!
(这个帖子提供了一些讨论,但我想知道是否有更新更新/更全面.)
该stringsearch包提供快速查找/ Haskell的字节串替换功能.是否存在Data.Text包中定义的文本字符串的相应功能？
我现在能看到的唯一方法是使用stringsearch编码为UTF8,然后转换回来 - 这不是很理想!
假设我有一个Data.Dynamic.Dynamic对象,它包装了一个IO动作(也就是某些类型IO a可能未知的类型a).我觉得我应该能够执行这个IO操作并获得它的结果,包含在Dynamic(它将具有类型a)中.有没有标准的库函数可以做到这一点？(有点像dynApply,但是对于IO动作性能而不是函数应用程序.)
该函数的实现可能看起来像
dynPerform :: Dynamic -> Maybe IO Dynamic
dynPerform (Dynamic typ act)
= if (typeRepTyCon typ) /= ioTyCon then Nothing else Just $
do result <- (unsafeCoerce act :: IO Any)
return Just . Dynamic (head $ typeRepArgs typ) $ result
exampleIOAction = putChar
typeOfIOAction = typeOf exampleIOAction
ioTyCon = typeRepTyCon typeOfIOAction
但显然这是使用几个不安全的操作,所以我宁愿从库中取出它.(事实上,由于Data.Dynamic.Dynamic类型的不透明性,我所编写的内容在Data.Dynamic之外不起作用.)
我发现自己需要在我正在开发的Haskell程序中使用字符串表.特别是,我想要一个允许将任何String插入(比如说)'Atom'的系统; 给定一个Atom,你应该能够恢复它来自的原始字符串,并且(批判性地)比较两个Atom的相等性应该与指针比较一样快(或几乎同样快).
(人们可以很容易地为这个功能设计一个引用透明的接口;实现将在unsafePerformIO内部使用,但库的用户不需要知道这些细节.)
Hackage上的两个库似乎在正确的球场:stringtable-atom和simple-atom.有没有人有使用这些库的经验？特别是,对于一方对另一方的好处是什么,有什么建议吗？
我知道如果一个 C++ 结构是普通旧数据（“POD”），那么这保证了它的内存结构中没有魔法，所以这意味着 amemcpy到一个字节数组并且memcpyback 是安全的。
我也知道在标准中 POD 结构不应该有用户定义的构造函数。在我现在拥有的项目中，有一些普通结构（只有数据字段），定义了一个默认构造函数，将数据成员初始化为 0。我看到其他客户端memset(&obj, 0, sizeof obj);在使用该结构之前会使用。
memset在使用非 POD 结构之前，它是否可以或安全？