Laziness

[polytypic]

Laziness can be useful with algebraic types. I recently implemented an experimental approach to laziness in my partial.lenses library. The idea is briefly discussed in issue 56.

The experimental approach used in partial.lenses is based on having an optional delay operation.

Concretely, in the case of Monoids, the optional delay has a signature like:

delay :: Monoid a => (() -> a) -> a

And in the case of Applicatives, the delay has a signature like:

delay :: Applicative c => (() -> c a) -> c a

In some cases, it is possible to derive the delay operation from other operations. In the case of Monads:

const deriveDelayForMonad = M => u2xM =>
  M.chain(_ => u2xM(), M.of(undefined))

The support for laziness in partial.lenses is considered experimental partly due to not having the concept in the Static Land Specification. Perhaps Static Land could be enhanced with support for laziness?

Addition: The F# Computation Expression Zoo paper contains some relevant discussion on considerations for impure effects and delayed computations in a strict language in conjunction with algebraic types (mostly Monads).

[rpominov]

Interesting. Basically delay() would allow to provide a function returning value of type a whenever we're supposed to provide a value of type a. It's like we can replace any value with something like Haskell's thunk containing the value.

Nice idea! I have no strong opinion about adding this to the spec yet though. Very curious what others think.

[ivenmarquardt]

When I think of lazy evaluation in Javascript currying/partial application or function composition comes to my mind. However, I have difficulties to imagine how lazy evaluation with thunks is useful in the context of iterative functions. Here is a plain and simple example:

const sequence = (n, acc) => () => n >= 0 ? sequence(n - 1, acc.concat(n)) : acc;
sequence(5, [])(); // ?
sequence(5, [])()()()()()()(); // [5,4,3,2,1,0]

With sequence you can't use any intermediate results, because you don't have access to the accumulator. Besides you never know if the next call yields another function or a value. Thus reflection like typeof x === "function" would be necessary, wouldn't it? What were a useful application for such a lazy computation? Just to better comprehend the concept.

[polytypic]

how lazy evaluation with thunks is useful in the context of iterative functions

It allows e.g. iteration to be stopped after a fixed point has been reached.

Here is a self-contained example. Note that I'm writing the code here in a naïve, inefficient, way to make it clearer.

As we are programming in an eager language, we need some explicit machinery to express laziness. Here is a kind of minimal vocabulary for laziness:

// lazy :: (() -> a) -> Lazy a
const lazy = th => () => {
  if (typeof th === "function")
    th = {value: th()}
  return th.value
}

// force :: Lazy a -> a
const force = delayed => delayed()

lazy introduces a lazy computation and force extracts the result of such a computation.

Here is a lazy monoid for computing disjunctions:

const LazyOr = {
  delay(th) {
    return lazy(() => force(th()))
  },
  empty() {
    return lazy(() => false)
  },
  concat(lhs, rhs) {
    if (force(lhs))
      return lhs
    else
      return rhs
  }
}

The implementation of delay may seem odd. The type of a LazyOr element is:

type LazyOr = Lazy Bool

and the type of delay is:

delay :: (() -> LazyOr) -> LazyOr

This explains the delay. First of all it must return a LazyOr value without immediately invoking the thunk. So, it must call lazy with a new thunk. Inside the new thunk it must first invoke the given thunk to get a LazyOr value. But this is not sufficient. The LazyOr value must also be forced.

A monoid can be lifted to an applicative:

function ConstOf(Monoid) {
  const Const = {
    map(_, x) {return x},
    ap: Monoid.concat,
    of(_) {return Monoid.empty()}
  }
  if (Monoid.delay)
    Const.delay = Monoid.delay
  return Const
}

Here is the lazy traversal from the partial.lenses issue without Ramda:

const traverse = (A, x2yA, xs) => A.delay(() =>
  xs.length === 0
  ? A.of([])
  : A.ap(A.map(x => xs => [x].concat(xs), x2yA(xs[0])),
         traverse(A, x2yA, xs.slice(1))))

We can now use traverse to fold over lists lazily:

force(traverse(ConstOf(LazyOr),
               x => (console.log(x), lazy(() => x > 3)),
               [3, 1, 4, 1, 5, 9]))
// 3
// 1
// 4
// true

[ivenmarquardt]

@polytypic thanks for this in-depth reply. The sketch is impressing!

I think e.g. purescript forgoes general lazy evaluation because with Javascript as compile target it gets pretty expensive. And directly encoded in Javascript the resulting code is somehow hard to read or at least looks unfamiliar.

The crucial question is, what benefits entail with laziness that you can't achieve by other means.

For instance, I use a special version of fold when I want to exit an iteration prematurely. Admittedly, foldable is not traversable, but I guess you can implement a corresponding traverse easily:

const foldlk = f => acc => xs => {
  const next = (acc, i) => xs.length === i
   ? acc
   : f(acc, xs[i], i) (acc => next(acc, i + 1));

  return next(acc, 0);
};

const any = f => foldlk(
  (acc, x) => k => f(x)
   ? true
   : k(acc)
) (false);

const xs = [3, 1, 4, 1, 5, 9];
const gt = y => x => (console.log(x), x > y);
any(gt(3)) (xs); // 3, 1, 4, true