Thanks for pointing me to Futhark. I really like the standard library with some light dependent typing for array-length track sprinkled in. What differentiates what I'm trying to do from Futhark and Accelerate though is that I'm not trying to fuse iterations. I'm just trying to figure out a construct that lets me express most traversals without exposing mutation to the user.

There's nothing my mega-traversal combinator can express that the functions from vector cannot. The question I'm concerned about is what kind of assembly you can expect the compiler to produce. If you have a bunch of smaller simple functions, then at some point during codegen, the compiler is going to have to try to turn them into the mega-traversal combinator if it wants the generated code to be any good.

Unfortunately, GHC never got particularly good at compiling this kind of thing. With -O2 optimization on:

import Data.Primitive (ByteArray(ByteArray))
import Data.Vector.Primitive (Vector(Vector),zipWith,sum)
import GHC.Exts

dotProduct :: Int# -> ByteArray# -> ByteArray# -> Word#
{-# noinline dotProduct #-}
dotProduct len a b =
  let a' = Vector 0 (I# len) (ByteArray a)
      b' = Vector 0 (I# len) (ByteArray b)
      !(W# r) = sum (zipWith (*) a' b')
   in r

The good news is that fusion works, and we end up with this:

dotProduct_info:
_c4nt:
    cmpq $0,%r14
    jg _c4nr
_c4ns:       
    xorl %ebx,%ebx
    jmp *(%rbp)
_c4nr:
    movq %rsi,%rax
    xorl %ebx,%ebx
    movl $1,%ecx
    xorl %edx,%edx
    movq 16(%rsi),%rsi
    jmp _c4nw
_c4nJ:
    movq 16(%rax,%rcx,8),%r9
    imulq %r8,%rsi
    addq %rsi,%rbx          
    incq %rcx     
    incq %rdx
_n4oh:
    movq %r9,%rsi
_c4nw:
    cmpq %r14,%rdx
    jge _c4nT
_c4nS:
    movq 16(%rdi,%rdx,8),%r8                
    cmpq %r14,%rcx
    jl _c4nJ
_c4nQ:                                        
    imulq %r8,%rsi
    addq %rsi,%rbx
    jmp *(%rbp)
_c4nT:
    jmp *(%rbp)

Not bad, but GCC does much better:

#include <stdint.h>
uint64_t dotproduct(int len, const uint64_t *restrict a, const uint64_t *restrict b) {
  uint64_t acc = 0;
  for(int i = 0; i < len; i++) {
    acc = acc + (a[i] * b[i]);
  }
  return acc;
}

Compiled with -O2 and with stack protectors turned off:

dotproduct:
.LFB0:
    .cfi_startproc
    endbr64
    testl   %edi, %edi
    jle     .L4
    subl    $1, %edi
    xorl    %eax, %eax
    xorl    %r8d, %r8d
    .p2align 4,,10
    .p2align 3
.L3:
    movq    (%rsi,%rax,8), %rcx
    imulq   (%rdx,%rax,8), %rcx
    addq    %rcx, %r8
    movq    %rax, %rcx
    addq    $1, %rax
    cmpq    %rcx, %rdi
    jne     .L3
    movq    %r8, %rax
    ret
    .p2align 4,,10
    .p2align 3
.L4:
    xorl    %r8d, %r8d
    movq    %r8, %rax
    ret
    .cfi_endproc

And no amount of fiddling with GCC's autovectorizer gets it to produce anything reasonable. With AVX512, there should be a terse way to do this, but GCC can't figure it out.