Is there a sense of 'object equality' in H

Question

If I have a singly linked list in Haskell:

data LL a = Empty | Node a (LL a) deriving (Show, Eq)

I can easily implement methods to insert at the end and at the beginning. But what about inserting after or before a particular element? If I have a LL of Integer, can I make a distinction in Haskell between inserting 4 after a particular node containing a 1, rather than the first 1 that it sees when processing the list?

Node 1 (Node 2 (Node 3 (Node 1 Empty)))

I'm curious how an insertAfter method would look that you would be able to specify "insert 5 after this particular node containing a 1". If I wanted to insert after the first node containing 1, would I have to pass in the entire list to specify this, and for the last node, only Node 1 Empty?

I'm not sure if it's right to address this as 'object equality'- but I'm wondering if there's a way to refer to particular elements of a type with the same payload in a data structure like this.

Answer 1

Kristopher Micinski remarked that you actually can do something similar with the ST monad, and you can do it with IO as well. Specifically, you can create an STRef or IORef, which is a sort of mutable box. The box can only be accessed using IO or ST actions as appropriate, which maintains the clean separation between "pure" and "impure" code. These references have identity—asking if two are equal tells you if they are actually the same box, rather than whether they have the same contents. But this is not really so pleasant, and not something you're likely to do without a good reason.

Answer 2

As others have pointed, in Haskell every value is immutable and there is no object. To specify an unique node, you either need to specify it structually (the first node in the linked list that contains 1, for example) or give every node an extra tag somehow (simulating what happens in an imperative world) so that we can distinguish them.

To structurally distinguish a node from others, we basically need to know the location of that node, e.g. a zipper that not only gives you the value at the point, but also its "neighborhoods".

And more detailed about "giving every node an extra tag":

First of all, you need to make every value an object, that requires you to generate unique tags at runtime. This is usually done by an allocator, the simplest allocator might just keep an integer, bump it when we need to create a new object:

-- | bumps counter
genId :: (Monad m, Functor m, Enum e) => StateT e m e
genId = get <* modify succ

-- | given a value, initializes a new node value
newNode :: (Monad m, Functor m, Enum e) => a -> StateT e m (a,e)
newNode x = genId >>= return . (x,)

And if you want to make an existing linked list work, we need to walk through it and give every node value a tag to make it an object:

-- | tags the llnked list with an extra value
tagged :: (Traversable f, Enum e, Monad m, Functor m)
       => f a -> StateT e m (f (a,e))
tagged = traverse newNode

And here is the full demo, it does look Maybe "a little" awkward:

{-# LANGUAGE DeriveFunctor, DeriveFoldable, DeriveTraversable, TupleSections #-}
import Control.Applicative
import Control.Monad.State hiding (mapM_)
import Data.Traversable
import Data.Foldable
import Prelude hiding (mapM_)

data LL a = Empty | Node a (LL a)
    deriving (Show, Eq, Functor, Foldable, Traversable)

-- | bumps counter
genId :: (Monad m, Functor m, Enum e) => StateT e m e
genId = get <* modify succ

-- | given a value, initializes a new node value
newNode :: (Monad m, Functor m, Enum e) => a -> StateT e m (a,e)
newNode x = genId >>= return . (x,)

example :: LL Int
example = Node 1 (Node 2 (Node 3 (Node 1 Empty)))

-- | tags the llnked list with an extra value
tagged :: (Traversable f, Enum e, Monad m, Functor m)
       => f a -> StateT e m (f (a,e))
tagged = traverse newNode

insertAfter :: (a -> Bool) -> a -> LL a -> LL a
insertAfter cond e ll = case ll of
    Empty -> Empty
    Node v vs -> Node v (if cond v
                           then Node e vs
                           else insertAfter cond e vs)

demo :: StateT Int IO ()
demo = do
    -- ll1 = Node (1,0) (Node (2,1) (Node (3,2) (Node (1,3) Empty)))
    ll1 <- tagged example
    nd <- newNode 10
    let tagIs t = (== t) . snd
        ll2 = insertAfter (tagIs 0) nd ll1
        -- ll2 = Node (1,0) (Node (10,4) (Node (2,1) (Node (3,2) (Node (1,3) Empty))))
        ll3 = insertAfter (tagIs 3) nd ll1
        -- ll3 = Node (1,0) (Node (2,1) (Node (3,2) (Node (1,3) (Node (10,4) Empty))))
    liftIO $ mapM_ print [ll1,ll2,ll3]

main :: IO ()
main = evalStateT demo (0 :: Int)

In this demo, tagIs is essentially doing the "object equality" thing because it is only interested in the extra tag we added before. Notice here I cheated in order to specify two nodes with their "values" being 1: one tagged 0 and the other tagged 3. Before running the program, it's impossible to tell what the actually tag would be. (Just like hard-coding a pointer value and hope it happens to work) In a more realistic setting, you would need another function to scan through the linked list and collect you a list of tags with a certain value (in this example, if you search the linked list to find all the nodes with "value" 1, you would have [0,3]) to work with.

"object equality" seems more like a concept from imperative programming languages, which assumes that there are allocators to offer "references" or "pointers" so that we can talk about "object equality". We have to simulate that allocator, I guess this is the thing that makes functional programming a little awkward to deal with it.

Answer 3

No, there is no such thing. The only way to tell apart values is by their structure; there is no identity like objects in some languages have. That is, there's no way you could tell apart these two values: (Just 5, Just 5) behaves exactly the same as let x = Just 5 in (x, x). Likewise, there is no difference between "this Node 1" and "some other Node 1": they are indistinguishable.

Usually the "solution" to this problem is to think of your problem in some other way so that there's no longer a need to distinguish based on identity (and usually there in fact is no need). But, as mentioned in the comments, you can emulate the "pointer" mechanic of other languages yourself, by generating distinct tags of some sort, eg increasing integers, and assigning one to each object so that you can tell them apart.

Answer 4

No, because it would break referential transparency. The results from calling a method with the same input multiple times should be indistinguishable, and it should be possible to replace it transparently with calling the method with that input once and then re-using the result. However, calling a method that returns some structure multiple times may produce a new copy of the structure every time -- structures with different "identity". If you could somehow tell that they have different identities, then it violates referential transparency.