关于 scala：如何在 Haskell 中创建相互引用的数据结构？

codeneng 2023-03-28 原文

How to create mutually referencing data structures in Haskell?

我利用了这样一个事实，即当 JVM 创建一个对象(不可变或不可变)时，它的指针是在其字段初始化之前创建的。

这让我可以创建这样的东西：

1
2
3
4
5

class BackRefdNode(val parent:Option[BackRefdNode],
node:ClassicNode){
val children=node.children.map{c=>
new BackRefdNode(Some(this), c)
}

Haskell 不是这种情况(据我所知)，如果是这种情况，Haskell 不会给我工具来利用它(我没有提到"this")。

所以我想知道，我如何在 Haskell 中实现这一点？

我认为也许 th fix 函数可以解决问题，但这实际上不会给我一个"this"引用，而是一个对 thunk 的引用，在计算时，理论上它的结构与创建了 BackRefdNode

Haskell 确实允许使用 let 进行循环引用。
相关：如何实现双向链表

Haskell 实际上在这里更进一步。它是惰性求值的，这意味着您可以在初始化之前获得对任何东西的引用，而不仅仅是带有字段的对象。使用数据类型

1 2	data ClassicNode = ClassicNode { children :: [ClassicNode] } data BackRefdNode = BackRefdNode { parent :: Maybe BackRefdNode, children :: [BackRefdNode] }

你可以创建一个函数

1
2
3

backRefdNode :: Maybe BackRefdNode -> ClassicNode -> BackRefdNode
backRefdNode parent node = let result = BackRefdNode parent (backRefdNode result <$> children node)
in result

请注意在初始化 result 本身的表达式中如何引用 result。这可以很好地工作并且有效地共享具有循环引用的树对象。

比 Scala 更难的是解开这种数据结构，因为 Haskell 中没有参考 eq 实体。 BackRefdNode 的每个孩子都将其作为其父母的不变量无法测试，必须从构造中证明。

不是 Scala 代码

1
2
3
4
5
6
7
8
9
10

trait ClassicNode {
def children: List[ClassicNode]
}

class BackRefdNode(val parent: Option[BackRefdNode],
node: ClassicNode) {
val children = node.children.map { c =>
new BackRefdNode(Some(this), c)
}
}

类似于 Haskell 代码

1
2
3
4
5
6
7
8
9

data ClassicNode

data BackRefdNode = BRN { parent :: Maybe BackRefdNode, node :: ClassicNode }

children1 :: ClassicNode -> [ClassicNode]
children1 _ = undefined

children :: BackRefdNode -> [BackRefdNode]
children this = map (\\c -> BRN (Just this) c) (children1 (node this))

或者使用 Haskell 中的类型类

1
2
3
4
5
6
7
8
9
10
11
12

class GetChildren a where
children :: a -> [a]

data ClassicNode

data BackRefdNode = BRN { parent :: Maybe BackRefdNode, node :: ClassicNode }

instance GetChildren ClassicNode where
children _ = undefined

instance GetChildren BackRefdNode where
children this = map (\\c -> BRN (Just this) c) (children (node this))

即双重翻译成 Scala

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

trait ClassicNode

class BackRefdNode(val parent: Option[BackRefdNode],
val node: ClassicNode)

trait GetChildren[A] {
def children(a: A): List[A]
}
object GetChildren {
implicit val classicNodeGetChildren: GetChildren[ClassicNode] = _ => ???
implicit val backRefdNodeGetChildren: GetChildren[BackRefdNode] = a =>
a.node.children.map { c =>
new BackRefdNode(Some(a), c)
}
}

implicit class GetChildrenOps[A](val a: A) extends AnyVal {
def children(implicit getChildren: GetChildren[A]): List[A] =
getChildren.children(a)
}

或者你的意思是在 Java/Scala 中 this 上的调度是动态的(与类型类的静态调度相反)。那么请看

Haskell 中的动态调度

Haskell TypeClass 的调度是动态的吗？

GHC 是否对存在类型使用动态调度？

@user好吧，如果一个函数是纯函数，您可以根据需要多次重新运行它，但是如果输入相同，则输出是相同的。 children "作为 BRN 的一部分" 是输入参数 this 的函数。我可以看到的区别是函数参数是静态解析还是动态解析。
@user 好吧，当 this 更改时， this.children "必须每次都计算"： backRefdNode1.children, backRefdNode2.children ...可以添加记忆(例如通过 State )。
@user "Bergi\\ 的回答似乎更符合 OP\\ 的意图" 好吧，我不确定我是否理解 OP\\ 的意图。该代码对我来说似乎具有误导性(因为我不确定我是否理解基于 Scala/JVM 的语言和 Haskell OP 之间的主要区别是什么意思)。
@user关于Bergi的回答主要是关于懒惰，但我们也可以在Scala中做懒惰(lazy val，按名称=>，Stream/LazyList ...)，这是只是不是默认行为。
@user 无论如何，第一次必须计算它。好的，然后是关于记忆的。正如我所说，可以添加备忘录。所以我仍然不确定这是什么主要区别:)
嗯，我只是在挑剔

更一般地说，您可以在不利用 Future/Promise 组合(或 Cats Effect 中的 Deferred)利用 JVM 行为的情况下创建这种循环：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class BackRefdNode(val parent: Option[BackRefdNode]) {
private[this] val leftPromise: Promise[Option[BackRefdNode]]()
private[this] val rightPromise: Promise[Option[BackRefdNode]]()

// leftChild.value will be:
// None if we haven't completed yet
// Some(Success(None)) if there will never be a left child
// Some(Success(Some(node))) if node is the left child
// (technically this Future never fails, but that's an implementation detail
def leftChild: Future[Option[BackRefdNode]] = leftPromise.future
def rightChild: Future[Option[BackRefdNode]] = rightPromise.future

def leftChildIs(nodeOpt: Option[BackRefdNode]): Try[Unit] =
Try { leftPromise.success(nodeOpt) }
def rightChildIs(node: Option[BackRefdNode]): Try[Unit] =
Try { rightPromise.success(nodeOpt) }
}

您通过将循环的一个方向设为链单子(-ish)来付出代价，但请注意，您根本不依赖于 this 或其他变幻莫测的 JVM 实现。

所以如果有一个 Haskell 等价物(也许是 Data.Promise？) Scala\\ 的 Promise/Future，翻译应该很简单。

我认为你不需要Promise，Haskell 是懒惰的

中创何在 span class br code-translation cyclic-reference haskell scala

有关关于 scala：如何在 Haskell 中创建相互引用的数据结构？的更多相关文章

ruby - 如何在 Ruby 中顺序创建 PI - 2
出于纯粹的兴趣，我很好奇如何按顺序创建PI，而不是在过程结果之后生成数字，而是让数字在过程本身生成时显示。如果是这种情况，那么数字可以自行产生，我可以对以前看到的数字实现垃圾收集，从而创建一个无限系列。结果只是在Pi系列之后每秒生成一个数字。这是我通过互联网筛选的结果:这是流行的计算机友好算法，类机器算法:defarccot(x,unity)xpow=unity/xn=1sign=1sum=0loopdoterm=xpow/nbreakifterm==0sum+=sign*(xpow/n)xpow/=x*xn+=2sign=-signendsumenddefcalc_pi(digits
ruby - 使用 ruby 将 HTML 转换为纯文本并维护结构/格式 - 2
我想将html转换为纯文本。不过，我不想只删除标签，我想智能地保留尽可能多的格式。为插入换行符标签，检测段落并格式化它们等。输入非常简单，通常是格式良好的html(不是整个文档，只是一堆内容，通常没有anchor或图像)。我可以将几个正则表达式放在一起，让我达到80%，但我认为可能有一些现有的解决方案更智能。最佳答案首先，不要尝试为此使用正则表达式。很有可能你会想出一个脆弱/脆弱的解决方案，它会随着HTML的变化而崩溃，或者很难管理和维护。您可以使用Nokogiri快速解析HTML并提取文本:require'nokogiri'h
ruby - 如何在 buildr 项目中使用 Ruby 代码？ - 2
如何在buildr项目中使用Ruby？我在很多不同的项目中使用过Ruby、JRuby、Java和Clojure。我目前正在使用我的标准Ruby开发一个模拟应用程序，我想尝试使用Clojure后端(我确实喜欢功能代码)以及JRubygui和测试套件。我还可以看到在未来的不同项目中使用Scala作为后端。我想我要为我的项目尝试一下buildr(http://buildr.apache.org/)，但我注意到buildr似乎没有设置为在项目中使用JRuby代码本身!这看起来有点傻，因为该工具旨在统一通用的JVM语言并且是在ruby中构建的。除了将输出的jar包含在一个独特的、仅限ruby
ruby - 什么是填充的 Base64 编码字符串以及如何在 ruby 中生成它们？ - 2
我正在使用的第三方API的文档状态:"[O]urAPIonlyacceptspaddedBase64encodedstrings."什么是“填充的Base64编码字符串”以及如何在Ruby中生成它们。下面的代码是我第一次尝试创建转换为Base64的JSON格式数据。xa=Base64.encode64(a.to_json) 最佳答案他们说的padding其实就是Base64本身的一部分。它是末尾的“=”和“==”。Base64将3个字节的数据包编码为4个编码字符。所以如果你的输入数据有长度n和n%3=1=>"=="末尾用于填充n%
ruby - 解析 RDFa、微数据等的最佳方式是什么，使用统一的模式/词汇(例如 schema.org)存储和显示信息 - 2
我主要使用Ruby来执行此操作，但到目前为止我的攻击计划如下:使用gemsrdf、rdf-rdfa和rdf-microdata或mida来解析给定任何URI的数据。我认为最好映射到像schema.org这样的统一模式，例如使用这个yaml文件，它试图描述数据词汇表和opengraph到schema.org之间的转换:#SchemaXtoschema.orgconversion#data-vocabularyDV:name:namestreet-address:streetAddressregion:addressRegionlocality:addressLocalityphoto:i
ruby-on-rails - 如何在 ruby 中使用两个参数异步运行 exe？ - 2
exe应该在我打开页面时运行。异步进程需要运行。有什么方法可以在ruby中使用两个参数异步运行exe吗？我已经尝试过ruby命令-system()、exec()但它正在等待过程完成。我需要用参数启动exe，无需等待进程完成是否有任何rubygems会支持我的问题？最佳答案您可以使用Process.spawn和Process.wait2:pid=Process.spawn'your.exe','--option'#Later...pid,status=Process.wait2pid您的程序将作为解释器的子进程执行。除
ruby - 如何在续集中重新加载表模式？ - 2
鉴于我有以下迁移:Sequel.migrationdoupdoalter_table:usersdoadd_column:is_admin,:default=>falseend#SequelrunsaDESCRIBEtablestatement,whenthemodelisloaded.#Atthispoint,itdoesnotknowthatusershaveais_adminflag.#Soitfails.@user=User.find(:email=>"admin@fancy-startup.example")@user.is_admin=true@user.save!ende
ruby - 如何在 Ruby 中拆分参数字符串 Bash 样式？ - 2
我正在为一个项目制作一个简单的shell，我希望像在Bash中一样解析参数字符串。foobar"helloworld"fooz应该变成:["foo","bar","helloworld","fooz"]等等。到目前为止，我一直在使用CSV::parse_line，将列分隔符设置为""和.compact输出。问题是我现在必须选择是要支持单引号还是双引号。CSV不支持超过一个分隔符。Python有一个名为shlex的模块:>>>shlex.split("Test'helloworld'foo")['Test','helloworld','foo']>>>shlex.split('Test"
ruby - 如何在 Lion 上安装 Xcode 4.6，需要用 RVM 升级 ruby - 2
我实际上是在尝试使用RVM在我的OSX10.7.5上更新ruby，并在输入以下命令后:rvminstallruby我得到了以下回复:Searchingforbinaryrubies,thismighttakesometime.Checkingrequirementsforosx.Installingrequirementsforosx.Updatingsystem.......Errorrunning'requirements_osx_brew_update_systemruby-2.0.0-p247',pleaseread/Users/username/.rvm/log/138121
ruby-on-rails - 如何在 ruby 交互式 shell 中有多行？ - 2
这可能是个愚蠢的问题。但是，我是一个新手......你怎么能在交互式rubyshell中有多行代码？好像你只能有一条长线。按回车键运行代码。无论如何我可以在不运行代码的情况下跳到下一行吗？再次抱歉，如果这是一个愚蠢的问题。谢谢。最佳答案这是一个例子:2.1.2:053>a=1=>12.1.2:054>b=2=>22.1.2:055>a+b=>32.1.2:056>ifa>b#Thecode‘if..."startsthedefinitionoftheconditionalstatement.2.1.2:057?>puts"f

关于 scala：如何在 Haskell 中创建相互引用的数据结构？

How to create mutually referencing data structures in Haskell?

有关关于 scala：如何在 Haskell 中创建相互引用的数据结构？的更多相关文章

随机推荐