Re: RFC: Should Data.IntMap.Strict be value-strict in the function arguments or the map itself

27 Oct 2011

      Here's the definition of Tip.

    data IntMap a = Bin {-# UNPACK #-} !Prefix {-# UNPACK #-} !Mask !(IntMap a) !(IntMap a)
                  | Tip {-# UNPACK #-} !Key a
                  | Nil

So we effectively have:

     insert :: Key -> a -> IntMap a -> IntMap a
     insert k x t =
       case t of
         Bin p m l r
           | nomatch k p m -> join k (Tip k x) p t
           | zero k m -> Bin p m (insert k x l) r
           | otherwise -> Bin p m l (insert k x r)
         Tip ky _
           | k==ky -> Tip k x
           | otherwise -> join k (Tip k x) ky t
         Nil -> k `seq` Tip k x

So it does not terminate in this case.

Edward

Excerpts from Johan Tibell's message of Thu Oct 27 13:13:56 -0400 2011:
...
On Thu, Oct 27, 2011 at 10:03 AM, Edward Z. Yang  wrote:
...
I'd like to remark that the situation with keys is not /quite/ comparable.
Even if we don't need to look at the key for inserting into an empty map,
it will get forced anyway because IntMaps are spine-strict (in particular,
they
are strict in their keys.)
I'm not quite sure if I follow. Here's Data.IntMap.insert:
insert :: Key -> a -> IntMap a -> IntMap a
    insert k x t = k `seq`
      case t of
        Bin p m l r
          | nomatch k p m -> join k (Tip k x) p t
          | zero k m -> Bin p m (insert k x l) r
          | otherwise -> Bin p m l (insert k x r)
        Tip ky _
          | k==ky -> Tip k x
          | otherwise -> join k (Tip k x) ky t
        Nil -> Tip k x
Without the explicit `seq`
insert undefined 1 Nil
terminates but with the `seq` it's _|_.
Are you saying it will eventually get force if someone e.g. does a lookup
after the insert?
-- Johan