89310846066c — Chris Cannam 11 months ago
For foldli/foldri, avoid using T.foldli/foldri because they have to reconstruct the key; instead do our own counting. Also fix incorrect index passed to f in the slice foldli/foldri functions (they were passing the array index rather than the slice index).
2 files changed, 23 insertions(+), 14 deletions(-)

M persistent-array-slice.sml
M persistent-array.sml
M persistent-array-slice.sml +14 -12
@@ 84,22 84,24 @@ structure PersistentArraySlice :>
         T.foldlRange f acc (trie, makeRange s)
                                                           
     fun foldli f acc (s as S { array = A.A { size, trie }, start, count }) =
-        T.foldliRange (fn (w, x, acc) => f (Word32.toInt w, x, acc))
-                      acc (trie, makeRange s)
+        case T.foldlRange (fn (x, (i, acc)) => (i + 1, f (i, x, acc)))
+                          (0, acc)
+                          (trie, makeRange s) of
+            (_, acc) => acc
                                                           
     fun foldr f acc (s as S { array = A.A { size, trie }, start, count }) =
         T.foldrRange f acc (trie, makeRange s)
                                                           
     fun foldri f acc (s as S { array = A.A { size, trie }, start, count }) =
-        T.foldriRange (fn (w, x, acc) => f (Word32.toInt w, x, acc))
-                      acc (trie, makeRange s)
-                                            
-    fun app f (s as S { array = A.A { size, trie }, start, count }) =
-        T.foldliRange (fn (_, x, _) => f x)
-                      () (trie, makeRange s)
-                                            
-    fun appi f (s as S { array = A.A { size, trie }, start, count }) =
-        T.foldliRange (fn (w, x, _) => f (Word32.toInt w, x))
-                      () (trie, makeRange s)
+        case T.foldrRange (fn (x, (i, acc)) => (i - 1, f (i, x, acc)))
+                          (count - 1, acc)
+                          (trie, makeRange s) of
+            (_, acc) => acc
+                                        
+    fun app f s =
+        foldl (fn (x, _) => ignore (f x)) () s
+                  
+    fun appi f s =
+        foldli (fn (i, x, _) => ignore (f (i, x))) () s
 
 end

          
M persistent-array.sml +9 -2
@@ 67,13 67,20 @@ structure PersistentArrayImpl = struct
         T.foldl f acc trie
 
     fun foldli f acc (A { size, trie }) =
-        T.foldli (fn (w, x, acc) => f (Word32.toInt w, x, acc)) acc trie
+        (* T.foldli is much slower than T.foldl, because it has to reconstruct
+           the keys as it goes. It's quicker for us just to count them *)
+        case T.foldl (fn (x, (i, acc)) => (i + 1, f (i, x, acc)))
+                     (0, acc) trie of
+            (_, acc) => acc
 
     fun foldr f acc (A { size, trie }) =
         T.foldr f acc trie
 
     fun foldri f acc (A { size, trie }) =
-        T.foldri (fn (w, x, acc) => f (Word32.toInt w, x, acc)) acc trie
+        (* as foldli *)
+        case T.foldr (fn (x, (i, acc)) => (i - 1, f (i, x, acc)))
+                     (Word32.toInt size - 1, acc) trie of
+            (_, acc) => acc
 
     fun find f (A { size, trie }) =
         T.search f trie