Add nondeterminstic map `delete` and `insertIfAbsent`

[robstewart57]

The Data.LVar.SLMap.insert function throws the runtime error "Multiple puts to one entry in an IMap!" if a 2nd insertion for the same key is attempted.

-- | Put a single entry into the map.  (WHNF) Strict in the key and value.
insert :: (Ord k, Eq v, HasPut e) =>
          k -> v -> IMap k s v -> Par e s ()
insert !key !elm (IMap (WrapLVar lv)) = WrapPar$ putLV lv putter
  where putter slm = do
          putRes <- SLM.putIfAbsent slm key $ return elm
          case putRes of
            Added _ -> return $ Just (key, elm)
            Found _ -> throw$ ConflictingPutExn$ "Multiple puts to one entry in an IMap!"

Is there a fundamental objection to an additional insertIfAbsent in SLMap with different semantics, namely that the 1st value written to a key entry succeeds, subsequent attempts to the same key are silently ignored? With the same type, i.e.

insertIfAbsent :: (Ord k, Eq v, HasPut e) => k -> v -> IMap k s v -> Par e s ()

This is the implementation of the underlying putIfAbsent_ used by putIfAbsent:

putIfAbsent_ (Bottom m) shortcut k vc0 _coin install = retryLoop vc0 where 
  -- The retry loop; ensures that vc is only executed once
  retryLoop vc = do
    searchResult <- liftIO $ LM.find (fromMaybe m shortcut) k
    case searchResult of
      LM.Found v      -> return $ Found v
      LM.NotFound tok -> do
        v <- vc
        maybeMap <- liftIO $ LM.tryInsert tok v
        case maybeMap of
          Just m' -> do
            install m' v                  -- all set on the bottom level, now try indices
            return $ Added v
          Nothing -> retryLoop $ return v -- next time around, remember the value to insert

It looks like the putIfAbsent in the skip list map module simply ignores subsequent write attempts to a key entry, returning Found v if a value already exists. Could this be lifted into the SLMap API as an alternative insertion function insertIfAbsent in the way I describe?

Not sure who subscribes to GitHub issues for the lvars repo, cc @osa1 @rrnewton .

[robstewart57]

I've pushed a commit for insertIfAbsent here: https://github.com/robstewart57/lvars/commit/98e958e00686fe433dfae2fa111f3ad312f9a9ba

Is this a sensible addition to the SLMap module? If so, I'd happily submit a pull request. If not, I'd be interested in knowing why. Thanks!

[rrnewton]

Thanks! Yes, this is sensible, but the type has to be right. This is a nondeterministic effect.

Thus in addition to HasPut it should have HasIO. IO is the sin bin and is the name for everything nondeterministic here.

Note this will mean that any computation containing this operation can be only be done with a runParIO type of operation.

[rrnewton]

@DreamLinuxer - can Ctrie implement this easily or not?

[rrnewton]

Ditto for delete operations.