| Safe Haskell | Safe-Inferred |
|---|---|
| Language | Haskell2010 |
PlutusTx.Optimize.SpaceTime
Description
Utilities for space-time tradeoff, such as recursion unrolling.
Documentation
Arguments
| ∷ ∀ a b. Int | How many recursion steps to move outside of the recursion loop. |
| → (SpliceQ (a → b) → SpliceQ (a → b)) | Function that given a continuation splice returns a splice representing a single recursion step calling this continuation. |
| → SpliceQ (a → b) |
Given n, and the step function for a recursive function, peel n layers
off of the recursion.
For example peel 3 (self -> [[| case [] -> 0; _ : ys -> 1 + self ys||])
yields the equivalence of the following function:
lengthPeeled :: [a] -> a
lengthPeeled xs =
case xs of -- first recursion step
[] -> 0
_ : ys -> 1 +
case ys of -- second recursion step
[] -> 0
_ : zs -> 1 +
case zs of -- third recursion step
[] -> 0
_ : ws -> 1 +
( fix self qs -> -- rest of recursion steps in a tight loop
case qs of
[] -> 0
_ : ts -> 1 + self ts
) ws
Arguments
| ∷ ∀ a b. Int | How many recursion steps to perform inside the recursion loop. |
| → (SpliceQ (a → b) → SpliceQ (a → b)) | Function that given a continuation splice returns a splice representing a single recursion step calling this continuation. |
| → SpliceQ (a → b) |
Given n, and the step function for a recursive function,
unroll recursion n layers at a time
For example unroll 3 (self -> [|| case [] -> 0; _ : ys -> 1 + self ys ||])
yields the equivalence of the following function:
lengthUnrolled :: [a] -> a
lengthUnrolled =
fix self xs -> -- beginning of the recursion "loop"
case xs of -- first recursion step
[] -> 0
_ : ys -> 1 +
case ys of -- second recursion step
[] -> 0
_ : zs -> 1 +
case zs of -- third recursion step
[] -> 0
_ : ws -> 1 + self ws -- end of the "loop"