CODEWITHSUNDEEP
haskelloptimizationiteration
Ford O.
Ford O.

Reputation: 1498

How stream fusion works in Haskell?

Can I write my own map function that is subject to stream fusion in Haskell?

Why recursive iteration over list isn't subject to fusion? That completely kills the nice expressiveness of Haskell pattern matching: foo (x:xx) ...!

Are Prelude loop functions fused?

Upvotes: 3

Views: 780

Answers (1)

Christof Schramm
Christof Schramm

Reputation: 343

Stream fusion in Haskell is done using rewrite rules (see the ghc documentation for more info). These are rules that you can specify in code using the RULES pragma.

The basic idea of rewirte rules is, that you specify a set of ways that code could be rewritten at compile time for example if you defined your own version of map as map', you could do something like

{-# RULES 
   "map'/map'" forall f g xs. map' f (map' g xs) = map' (f . g) xs
  #-}

This introduces a rewrite rule called map'/map'. What this rule would do, is that it would rewrite every mapping of a function f over a list that is in turn a g mapped over some xs into one single mapping of (f . g) over these xs.

There are a number of further sublteties to using rewrite rules. For example you can specify at what phase in the compiler a rule is applied, and the compiler doesn't have a way to check if those rules are correct.

The rewrite results are still typechecked, but if you did something semantically incorrect in a rewrite rule, that is purely on you.

Upvotes: 1

Related Questions