3

Immutability along with referential transparency leads to a couple of desirable properties. But together they have two drawbacks:

  • deep copying
  • determination of equality

Both operations are expensive.

The first issue is mitigated by structural sharing. The List type is one of the simplest persistent data structures and as a result of structural sharing prepending to lists is rather cheap:

xs = [1, 2, 3] --     [1, [2, [3, []]]]
ys = 0 : xs    -- [0, [1, [2, [3, []]]]]

But how can I determine the equality between xs and ys without checking the equality of each element?

In an imperative language like Javascript I would simply conduct a physical equality check of the root node. Since this invalidates referential transparency, it is not possible in Haskell, of course.

Is there an approach/strategy to avoid the brute force method - at least for some cases?

What I am currently trying in Javascript is to create a equality type that implements the monad class, so that I can determine reference equality without losing RT. But I am too inexperienced to see if this is a promising approach.

  • 2
    Generally the best strategy is to **avoid equality comparisons**. They aren't really that useful – in fact if two values turn up that are equal, it hints that duplicate work has already been done. Best design algorithms so they simply don't care whether any values are equal. If you do compare, it's usually a good idea to **start with a hash** rather than the values themselves. – leftaroundabout Mar 09 '18 at 11:16
  • You could do that like in Javascript, but you should do that in IO or ST (which is default in Javascript). Just wrap your objects to IORef or STRef and you will can compare them. But if you want to be pure, you should not think about phisical comparison. – freestyle Mar 09 '18 at 11:30
  • @leftaroundabout I'd hoped a little bit that equality checks themselves are often the problem - like an indicator for poor or imperative programming (simply put). –  Mar 09 '18 at 11:34
  • @freestyle I didn't know `IORef`, thanks! –  Mar 09 '18 at 11:37
  • See also: [1](https://stackoverflow.com/questions/1976247) [2](https://stackoverflow.com/questions/5701893) [3](https://stackoverflow.com/questions/30175974) [4](https://stackoverflow.com/questions/18077428) [5](https://stackoverflow.com/questions/1717553) [6](https://stackoverflow.com/questions/27762441) – Daniel Wagner Mar 09 '18 at 12:43
  • 1
    @DanielWagner It's certainly a duplicate. I actually did some research before. It is amazing how many formulations there are for basically the same question. Thanks for the links. –  Mar 09 '18 at 12:59

0 Answers0