4 ms·
Technically this is only correct if a and b have the same length so you would need to do a length check prior: foldZip a b | T.length a /= T.length b
by Tarean 9y ago
Technically this is only correct if a and b have the same length so you would need to do a length check prior:
foldZip a b
| T.length a /= T.length b = Nothing
| otherwise = foldl' step 0 (T.zip a b)
where step acc (l, r) = if l == r then acc+1 else acc
This is slightly awkward because T.length is an O(n) operation, though. I think the optimal implementation would be a hyper optimized variant that depends on correct byte alignment and this as slow fallback method if that fails.
- kqr 9y agoI discovered yesterday that my previous benchmarks were wrong for some reason. Zip+fold isn't actually that fast: http://i.xkqr.org/scrot_20170615223112.png http://i.xkqr.org/scrot_20170615223112.png What is fast – without reaching into the Text object internal representation – is good old tail-call recursion. And you can even integrate the length check into the traversal! Making it an O(min(n,m)) operation in total.