1

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

2

3 Answers 3

3

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.

1

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?

6
  • 1
    @user Well, if a function is pure, you can rerun it as many times as you want, but the output is the same if input is the same. children "being a part of BRN" is a function of input parameter this. The difference I can see is whether function parameter is resolved statically or dynamically. Oct 11, 2020 at 0:17
  • @user Well, this.children "has to be computed each time" when this changes: backRefdNode1.children, backRefdNode2.children ... Memoization can be added (via State for example). Oct 11, 2020 at 0:29
  • 1
    @user "Bergi's answer seems to stay truer to the OP's intent" Well, I'm not sure I understand OP's intent. The code seems misleading for me (since I'm not sure I understand what principal difference between Scala/JVM-based languages and Haskell OP meant). Oct 11, 2020 at 0:37
  • 1
    @user Regarding Bergi's answer it's mostly about laziness but we can do laziness in Scala as well (lazy val, by-name =>, Stream/LazyList ...), this is just not the default behavior. Oct 11, 2020 at 0:40
  • @user Anyway first time it has to be computed. Ok, after that it's about memoization. As I've said memoization can be added. So I'm still not sure what principal difference this is about :) Oct 11, 2020 at 0:59
-2

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.

1
  • I don't think you need a promise, Haskell is lazy anyways
    – username
    Oct 11, 2020 at 0:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.