<div dir="ltr">Hi Carter,<div><br></div><div>I've <a href="https://github.com/haskell/vector/issues/228">created a ticket</a> as requested and have reproduced the text here:</div><div><br></div><div><p style="box-sizing:border-box;margin-bottom:16px;color:rgb(36,41,46);font-family:-apple-system,system-ui,"Segoe UI",Helvetica,Arial,sans-serif,"Apple Color Emoji","Segoe UI Emoji","Segoe UI Symbol";font-size:14px;margin-top:0px">I've implemented a hand rolled version, and another two versions based on a combination of <code style="box-sizing:border-box;font-family:SFMono-Regular,Consolas,"Liberation Mono",Menlo,Courier,monospace;font-size:11.9px;background-color:rgba(27,31,35,0.05);border-radius:3px;margin:0px;padding:0.2em 0.4em">mapM</code> and the lazy and strict versions of <code style="box-sizing:border-box;font-family:SFMono-Regular,Consolas,"Liberation Mono",Menlo,Courier,monospace;font-size:11.9px;background-color:rgba(27,31,35,0.05);border-radius:3px;margin:0px;padding:0.2em 0.4em">State</code> monad.</p><p style="box-sizing:border-box;margin-bottom:16px;margin-top:0px;color:rgb(36,41,46);font-family:-apple-system,system-ui,"Segoe UI",Helvetica,Arial,sans-serif,"Apple Color Emoji","Segoe UI Emoji","Segoe UI Symbol";font-size:14px"><a class="gmail-issue-link gmail-js-issue-link" href="https://github.com/haskell-works/hw-prim/pull/38" style="box-sizing:border-box;background-color:initial;color:rgb(3,102,214);text-decoration-line:none">haskell-works/hw-prim#38</a></p><p style="box-sizing:border-box;margin-bottom:16px;margin-top:0px;color:rgb(36,41,46);font-family:-apple-system,system-ui,"Segoe UI",Helvetica,Arial,sans-serif,"Apple Color Emoji","Segoe UI Emoji","Segoe UI Symbol";font-size:14px">The benchmarks show that the hand rolled versions run two times faster than the lazy state monad version and 16 times faster than the strict state monad.</p><p style="box-sizing:border-box;margin-bottom:16px;margin-top:0px;color:rgb(36,41,46);font-family:-apple-system,system-ui,"Segoe UI",Helvetica,Arial,sans-serif,"Apple Color Emoji","Segoe UI Emoji","Segoe UI Symbol";font-size:14px">I found the slow performance of the strict monad version most surprising.</p><p style="box-sizing:border-box;margin-bottom:16px;margin-top:0px;color:rgb(36,41,46);font-family:-apple-system,system-ui,"Segoe UI",Helvetica,Arial,sans-serif,"Apple Color Emoji","Segoe UI Emoji","Segoe UI Symbol";font-size:14px">I'm aware that the version that using <code style="box-sizing:border-box;font-family:SFMono-Regular,Consolas,"Liberation Mono",Menlo,Courier,monospace;font-size:11.9px;background-color:rgba(27,31,35,0.05);border-radius:3px;margin:0px;padding:0.2em 0.4em">mapM</code> might enable fusion, however it is a fair bit slower than a hand rolled version that defeats fusion.</p><p style="box-sizing:border-box;margin-top:0px;color:rgb(36,41,46);font-family:-apple-system,system-ui,"Segoe UI",Helvetica,Arial,sans-serif,"Apple Color Emoji","Segoe UI Emoji","Segoe UI Symbol";font-size:14px;margin-bottom:0px">I would love to have a fusion-enabled version that runs as fast as the hand rolled version. Would that be possible?</p><p style="box-sizing:border-box;margin-top:0px;color:rgb(36,41,46);font-family:-apple-system,system-ui,"Segoe UI",Helvetica,Arial,sans-serif,"Apple Color Emoji","Segoe UI Emoji","Segoe UI Symbol";font-size:14px;margin-bottom:0px"><br></p><p style="box-sizing:border-box;margin-top:0px;color:rgb(36,41,46);font-family:-apple-system,system-ui,"Segoe UI",Helvetica,Arial,sans-serif,"Apple Color Emoji","Segoe UI Emoji","Segoe UI Symbol";font-size:14px;margin-bottom:0px">Cheers,</p><p style="box-sizing:border-box;margin-top:0px;color:rgb(36,41,46);font-family:-apple-system,system-ui,"Segoe UI",Helvetica,Arial,sans-serif,"Apple Color Emoji","Segoe UI Emoji","Segoe UI Symbol";font-size:14px;margin-bottom:0px"><br></p><p style="box-sizing:border-box;margin-top:0px;color:rgb(36,41,46);font-family:-apple-system,system-ui,"Segoe UI",Helvetica,Arial,sans-serif,"Apple Color Emoji","Segoe UI Emoji","Segoe UI Symbol";font-size:14px;margin-bottom:0px">-John</p></div></div><br><div class="gmail_quote"><div dir="ltr">On Fri, 9 Nov 2018 at 01:18, Carter Schonwald <<a href="mailto:carter.schonwald@gmail.com">carter.schonwald@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div><div dir="auto">I thought about it a teeny bit more </div><div dir="auto"><br></div><div dir="auto">This should be trivially definable using mapM or equivalent using state t </div><div dir="auto"><br></div><div dir="auto">Have you tried doing that simple high level definition? I think that works with vector fusion quite nicely. </div><div dir="auto"><br></div><div dir="auto">... ohhh. I see. There’s two vectors of inputs. I’ll have to think about this more. </div><br><div class="gmail_quote"><div dir="ltr">On Thu, Nov 8, 2018 at 8:14 AM Carter Schonwald <<a href="mailto:carter.schonwald@gmail.com" target="_blank">carter.schonwald@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div><div dir="auto">Hey John</div></div><div dir="auto">: </div><div dir="auto">I’m happy to help you contribute to to vector. </div><div dir="auto"><br></div><div dir="auto">1). This might not actually be needed with stream fusion on ... though perhaps this sort of shared computation needs to be its own combinators because of the sharing meaning that the stream fusion on map and foldl might not work. (Have you tried doing let x = map ... in let y = foldl ... in something with x and y? Even eg just writing map accum l in terms of just that? It could very well fuse ... though I don’t think it can with the current vector fusion framework. Though I think one of the more exotic fusion frameworks Amos Robinson did a few years ago could handle that fusion. Sadly that one requires an ILP solver at compile time. But there’s some tricks I think we could do )</div><div dir="auto"><br></div><div dir="auto">2) writing it in stream fusion form / as map accum l for streams will actually be simpler I think </div><div dir="auto"><br></div><div dir="auto">3) put a ticket on our GitHub. I’ve a huge backlog (life and stuff got me a bit slow), but this sounds like a super reasonable feature request </div><div dir="auto"><br></div><div dir="auto"><br></div><div><br><div class="gmail_quote"><div dir="ltr">On Thu, Nov 8, 2018 at 6:31 AM John Ky <<a href="mailto:newhoggy@gmail.com" target="_blank">newhoggy@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Hello,<div><br></div><div>I'd like to add the <span style="background-color:rgb(39,40,34);color:rgb(166,226,46);font-family:"Fira Code";font-size:12px;white-space:pre-wrap">mapAccumL</span> function to the <span style="background-color:rgb(39,40,34);color:rgb(102,217,239);font-family:"Fira Code";font-size:12px;font-style:italic;white-space:pre-wrap">vector</span> package.</div><div><br></div><div>Specifically the <span style="color:rgb(102,217,239);font-family:"Fira Code";font-size:12px;font-style:italic;white-space:pre-wrap;background-color:rgb(39,40,34)">Data.Vector.Storable</span> module, but it would also be useful other vector modules.</div><div><br></div><div>This is my attempt at an implementation:</div><div><br></div><div><div style="color:rgb(248,248,242);background-color:rgb(39,40,34);font-family:"Fira Code";font-size:12px;line-height:18px;white-space:pre-wrap"><div style="line-height:18px"><div>{-# <span style="color:rgb(249,38,114)">LANGUAGE</span> ScopedTypeVariables #-}</div><br></div><div><span style="color:rgb(166,226,46)">mapAccumL</span> <span style="color:rgb(249,38,114)">::</span> <span style="color:rgb(249,38,114)">forall</span> a b c. (<span style="color:rgb(102,217,239);font-style:italic">Storable</span> b, <span style="color:rgb(102,217,239);font-style:italic">Storable</span> c)</div><div> <span style="color:rgb(249,38,114)">=></span> (a <span style="color:rgb(249,38,114)">-></span> b <span style="color:rgb(249,38,114)">-></span> (a, c))</div><div> <span style="color:rgb(249,38,114)">-></span> a</div><div> <span style="color:rgb(249,38,114)">-></span> <span style="color:rgb(102,217,239);font-style:italic">DVS</span>.<span style="color:rgb(102,217,239);font-style:italic">Vector</span> b</div><div> <span style="color:rgb(249,38,114)">-></span> (a, <span style="color:rgb(102,217,239);font-style:italic">DVS</span>.<span style="color:rgb(102,217,239);font-style:italic">Vector</span> c)</div><div>mapAccumL f a vb <span style="color:rgb(249,38,114)">=</span> <span style="color:rgb(174,129,255)">DVS</span><span style="color:rgb(249,38,114)">.</span>createT <span style="color:rgb(249,38,114)">$</span> <span style="color:rgb(249,38,114)">do</span></div><div> vc <span style="color:rgb(249,38,114)"><-</span> <span style="color:rgb(174,129,255)">DVSM</span><span style="color:rgb(249,38,114)">.</span>unsafeNew (<span style="color:rgb(174,129,255)">DVS</span><span style="color:rgb(249,38,114)">.</span>length vb)</div><div> a' <span style="color:rgb(249,38,114)"><-</span> go <span style="color:rgb(174,129,255)">0</span> a vc</div><div> return (a', vc)</div><div> <span style="color:rgb(249,38,114)">where</span> go <span style="color:rgb(249,38,114)">::</span> <span style="color:rgb(102,217,239);font-style:italic">Int</span> <span style="color:rgb(249,38,114)">-></span> a <span style="color:rgb(249,38,114)">-></span> <span style="color:rgb(102,217,239);font-style:italic">DVS</span>.<span style="color:rgb(102,217,239);font-style:italic">MVector</span> s c <span style="color:rgb(249,38,114)">-></span> <span style="color:rgb(102,217,239);font-style:italic">ST</span> s a</div><div> go i a0 vc <span style="color:rgb(249,38,114)">=</span> <span style="color:rgb(249,38,114)">if</span> i <span style="color:rgb(249,38,114)"><</span> <span style="color:rgb(174,129,255)">DVS</span><span style="color:rgb(249,38,114)">.</span>length vb</div><div> <span style="color:rgb(249,38,114)">then</span> <span style="color:rgb(249,38,114)">do</span></div><div> <span style="color:rgb(249,38,114)">let</span> (a1, c1) <span style="color:rgb(249,38,114)">=</span> f a0 (<span style="color:rgb(174,129,255)">DVS</span><span style="color:rgb(249,38,114)">.</span>unsafeIndex vb i)</div><div> <span style="color:rgb(174,129,255)">DVSM</span><span style="color:rgb(249,38,114)">.</span>unsafeWrite vc i c1</div><div> go (i <span style="color:rgb(249,38,114)">+</span> <span style="color:rgb(174,129,255)">1</span>) a1 vc</div><div> <span style="color:rgb(249,38,114)">else</span> return a0</div><div>{-# <span style="color:rgb(249,38,114)">INLINE</span> mapAccumL #-}</div></div></div><div><br></div><div>The implementation should obey the following law:</div><div><br></div><div><div style="color:rgb(248,248,242);background-color:rgb(39,40,34);font-family:"Fira Code";font-size:12px;line-height:18px;white-space:pre-wrap"><div><div style="line-height:18px"><div><span style="color:rgb(249,38,114)">import</span> <span style="color:rgb(249,38,114)">qualified</span> Data.List <span style="color:rgb(249,38,114)">as</span> L</div><div><span style="color:rgb(249,38,114)">import</span> <span style="color:rgb(249,38,114)">qualified</span> Data.Vector.Storable <span style="color:rgb(249,38,114)">as</span> DVS</div><div><span style="color:rgb(249,38,114)"></span></div></div></div><div><br></div><div>(<span style="color:rgb(174,129,255)">DVS</span><span style="color:rgb(249,38,114)">.</span>toList <span style="color:rgb(249,38,114)"><$></span> <span style="color:rgb(174,129,255)">DVS</span><span style="color:rgb(249,38,114)">.</span>mapAccumL f a (<span style="color:rgb(174,129,255)">DVS</span><span style="color:rgb(249,38,114)">.</span>fromList bs)) <span style="color:rgb(249,38,114)">===</span> <span style="color:rgb(174,129,255)">L</span><span style="color:rgb(249,38,114)">.</span>mapAccumL f a bs</div></div></div><div><br></div><div>Cheers,</div><div><br></div><div>-John</div><div><br></div></div>
_______________________________________________<br>
Libraries mailing list<br>
<a href="mailto:Libraries@haskell.org" target="_blank">Libraries@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries</a><br>
</blockquote></div></div>
</blockquote></div></div>
</blockquote></div>