TransWikia.com

How to create mutually referencing data structures in Haskell?

Stack Overflow Asked by Alejandro Navas on January 11, 2021

I’ve exploited the fact that when the JVM creates an object (immutable or not), its pointer is created before its fields are initialized.

That allows me to create something like this:

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

That’s not the case (as far as I know) with Haskell, and if that’s the case anyway, Haskell doesn’t give me the tools to exploit that (gives me no reference to "this").

So I’m wondering, how do I achieve that in Haskell?

I thought that maybe th fix function could do the trick, but that would not actually give me a "this" reference, but a reference to a thunk that when calculated, would have, theoretically, the same structure as the created BackRefdNode

3 Answers

Haskell actually goes one step further here. It is lazily evaluated, which means you can get a reference to anything before it is initialised, not just objects with fields. Using the data types

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

you can create a function

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

Notice how result is referenced in the expression that initialises result itself. This works perfectly fine and efficiently shares the tree objects with circular references amongst them.

What will be harder than in Scala is unraveling this data structure, as there is no reference equality in Haskell. The invariant that every child of a BackRefdNode has it as its parent cannot be tested, it must be proven from the construction.

Answered by Bergi on January 11, 2021

More generally, you can create this sort of cyclicality without exploiting JVM behavior with the Future/Promise combo (or Deferred from Cats Effect, for that matter):

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) }
}

You pay the price by making one direction of the cycle the chain monadic(-ish), but note that you're not depending at all on this or other vagaries of JVM implementation.

So if there's a Haskell equivalent (perhaps Data.Promise?) to Scala's Promise/Future, the translation should be straightforward.

Answered by Levi Ramsey on January 11, 2021

Isn't Scala code

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)
  }
}

similar to Haskell code

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))

?

Or with a type class in Haskell

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))

i.e. in double translation into Scala

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)
}

Or maybe you mean that in Java/Scala dispatch on this is dynamic (on contrary to static dispatch with type classes). Then please see

Dynamic dispatch in Haskell

Is the dispatch of a Haskell TypeClass dynamic?

Does GHC use dynamic dispatch with existential types?

Answered by Dmytro Mitin on January 11, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP