How we made Haskell search strings as fast as Rust

Re:How we made Haskell search strings as fast as Rust by Tarean on Wednesday March 13, 2019 @04:19PM (#19383307)

Lazy data structures require allocation. GHC's lists use build/fold fusion to remove intermediate lists but that's basically just a less reliable way of converting to folds http://hackage.haskell.org/package/base-4.12.0.0/docs/src/GH...

The other common fusion technique used in haskell is stream fusion which is very similar to the mutual-recursion-encoded-as-sum-type version in the blog post.

There is also indexing-based fusion which the Repa library uses. It allows more control over traversal order (think optimizing stencil codes) but requires regular arrays, e.g. no filtering.

There are some other research projects like specialized compiler passes via hermit but afaik nothing really production ready.

[ Parent | on HN ]

Re:How we made Haskell search strings as fast as Rust by eridius on Wednesday March 13, 2019 @06:32PM (#19384621)

Ok so not using a lazy list for matches is basically just around avoiding the requisite allocation? I suppose if you consume the list immediately at the call-site the compiler could in theory after inlining convert it to the closure-based approach for you, but probably wouldn't.

[ Parent | on HN ]