benchmark.purs

benchFromFoldableTco :: Benchmark 
benchFromFoldableTco = mkBenchmark 
  { slug  : "fromFoldableTco"
  , title : "fromFoldable via repeated insert"
  , sizes : (0..10 <#> (*) 100) <> (1..10 <#> (*) 1000)
  , sizeInterpretation : "Number of entries" 
  , inputsPerSize : 10
  , gen : \n -> resize n (arbitrary :: Gen (List (Tuple Int Int)))
  , functions : [ benchFn "fromFoldable direct"     fromFoldable 
                , benchFn "fromFoldable stack-safe" fromFoldable' 
                , benchFn "fromFoldable native"     OCMap.fromFoldable
                ]
  }

example.purs

insert :: forall k v. Ord k => Fn3 k v (Map k v) (Map k v) 
insert = go 
  where
    comp :: k -> k -> Ordering 
    comp = compare 

    go = mkFn3 \k v t -> case t of 
      Bin n k' v' l r -> case comp k k' of 
        LT -> runFn4 balanceL k' v' (runFn3 go k v l) r  
        GT -> runFn4 balanceR k' v' l (runFn3 go k v r) 
        _  -> Bin n k v l r 
      _ -> Bin 1 k v sharedTip sharedTip 

data FromContext k v = FromLeft  k v (Map k v) 
                     | FromRight k v (Map k v) 
              
insert' :: forall k v. Ord k => k -> v -> Map k v -> Map k v 
insert' = go 
  where 
    comp :: k -> k -> Ordering 
    comp = compare
    
    go k v = down Nil 
      where
        down path Tip               = up path (Bin 1 k v sharedTip sharedTip) 
        down path (Bin _ k' v' l r) = case comp k k' of 
          LT -> down (FromLeft  k' v' r : path) l 
          GT -> down (FromRight k' v' l : path) r       
          _  -> up path (runFn4 bin k v l r) 

        up Nil                        t = t 
        up (FromLeft  k' v' r : path) t = up path (runFn4 balanceL k' v' t r) 
        up (FromRight k' v' l : path) t = up path (runFn4 balanceR k' v' l t)