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

Dmytro Mitin
  • 48,194
  • 3
  • 28
  • 66
caeus
  • 3,084
  • 1
  • 22
  • 36
  • 1
    Haskell does allow circular references with `let`. – Bergi Oct 10 '20 at 03:59
  • Related: [How to implement doubly linked lists](https://stackoverflow.com/questions/10386616/how-to-implement-doubly-linked-lists) – user Oct 10 '20 at 23:20

3 Answers3

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.

Bergi
  • 630,263
  • 148
  • 957
  • 1,375
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?

Dmytro Mitin
  • 48,194
  • 3
  • 28
  • 66
  • 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. – Dmytro Mitin Oct 11 '20 at 00: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). – Dmytro Mitin Oct 11 '20 at 00: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). – Dmytro Mitin Oct 11 '20 at 00: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. – Dmytro Mitin Oct 11 '20 at 00: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 :) – Dmytro Mitin Oct 11 '20 at 00:59
  • Meh, I’m just being nitpicky – user Oct 11 '20 at 03:36
-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.

Levi Ramsey
  • 18,884
  • 1
  • 16
  • 30