Can lazy evaluation be implemented by a monadic type?

Question

I'm currently studying lazy evaluation in conjunction with monads in Javascript and what use cases may evolve from these. So I tried to implement a lazy type, which implements the functor/monad type class. The corresponding constructor is meant to be lazy in its arguments and in its result. Here is what I came up with:

// a lazy type

// (() -> a) -> () -> b
const Lazy = thunk => () => thunk();

// (b -> a -> b) -> b -> Lazy a -> b
Lazy.fold = f => acc => tx => f(acc) (tx());

// (a -> b) -> Lazy a -> Lazy b
Lazy.map = f => tx => Lazy(() => f(tx()));

// Lazy (a -> b) -> Lazy a -> Lazy b
Lazy.ap = tf => tx => Lazy(() => tf() (tx()));

Lazy.of = Lazy;

// Lazy (Lazy a) -> Lazy a
Lazy.join = ttx => ttx();

// (a -> Lazy b) -> Lazy a -> Lazy b
Lazy.chain = ft => tx => Lazy.join(Lazy.map(ft) (tx));

// recursive bind (or chain in Javascript)

// Number -> (a -> b) -> a -> Lazy b
const repeat = n => f => x => {
  const aux = m => y => m === 0
   ? Lazy(() => y)
   : Lazy.chain(aux(m - 1)) (Lazy(() => f(y)));

  return aux(n) (x);
};

// impure function to observe the computation

const inc = x => (console.log(++x), x);

// and run

console.log(repeat(5) (inc) (0)); // logs 1, 2, 3, 4, 5, () => thunk()

Now this evidently makes no sense, since the action sequence isn't lazy at all. Lazy.join simply triggers the evaluation prematurely. Hence, the following questions have emerged:

• are sequences of monadic actions in Haskell always eagerly evaluated?
• is lazy evaluation an effect that cannot be implemented by a monad in a strictly evaluated language?

I am not even sure if my research makes any sense, so feel free to vote for closing this question.

Answer 1

It depends on what you mean by "implementing lazy evaluation". You can certainly make a "Delay" type and it will be a monad. But normally we think of a function with type A -> State S B as being a "stateful function from A to B". With something like A -> Delay B, it seems that for the argument A we've already "forced" it. It seems like we'd really want something more like Delay A -> Delay B.

It turns out that there are multiple ways of converting an expression to monadic style. A call-by-value way, which is the usual way, and a call-by-name way. This is discussed by Phil Wadler in his 1992 paper Comprehending Monads (PDF). Not surprisingly, these are related to a similar fact that there are two translations into continuation-passing style (CPS): a call-by-value one and a call-by-name one. Indeed, these are exactly the call-by-value/-name monadic style translations just with the continuation monad. The purpose of CPS was to separate the order of evaluation of a target, implementation language from the order of evaluation of the source language. If you use the call-by-value CPS transform to implement a source language, it will have call-by-value semantics regardless of what the evaluation order of the target language is. Similarly, if you use the call-by-name CPS transform, you will likewise get call-by-name semantics regardless of the evaluation order of the target language.

I don't know exactly how things would play out when using a call-by-value translation with a Delay monad, but I suspect it will often be "just a bit" off and "correcting" it will move more towards a call-by-name translation.

Answer 2

this evidently makes no sense, since the action sequence isn't lazy at all. Lazy.join simply triggers the evaluation prematurely

Yes. So just don't do that:

// (() -> (() -> a)) -> (() -> a)
Lazy.join = ttx => Lazy(() => ttx()());
//                         ^^ this function prevents `ttx` from being evaluated immediately

(though you can, and possible should for performance reasons, drop the Lazy wrapper or make Lazy = id)

are sequences of monadic actions in Haskell always eagerly evaluated?

No, Haskell doesn't evaluate anything until you tell it to do. Monads are no exception, they work like any other data type.

is lazy evaluation an effect that cannot be implemented by a monad in a strictly evaluated language?

No, it works perfectly fine.

However, you might want to notice that you haven't yet implemented lazy implementation completely, which also implies sharing of results instead of re-evaluation. This does require mutability though, and works well only if the evaluated functions are pure.

Answer 3

Playing around

Your question is fun and I haven't yet explored such a monad so I wanted to play around with it.

As Bergi points out, there's no need for the additional thunk wrapper in your data constructor – ie, Lazy expects its argument to be a thunk already.

Your join was broken – as counter-intuitive as it might seem, you have to make sure you wrap the unwrapping process! Think of it as adding one wrapper, but removing two; you still remove one layer of nesting, which achieves the intended result

Your monadic return (or of in this case) is also broken; return is not always the same as your data constructor – ie Lazy.of(2) should be equivalent to Lazy($ => 2)

Your code inspired me, so I tinkered with it until I wound up with this. I think you will be pleased ^_^ Bergi also suggested that Lazy should not re-evaluated its result. I handled that with a safe memoisation inside the runLazy method. Feedback on this would be appreciated <3

personal code style

As a convention, I write thunks as $ => expr instead of () => expr. When writing functional programs in JavaScript, you end up with a lot of ()s, often times adjacent to other ()s which can sometimes hurt readability. I think Lazy($ => f()) reads (at least) slightly better than Lazy(() => f()). Since this is meant to be an educational site, I figure this is worth mentioning. I feel like small change helps with readability, but I also don't want to confuse anyone.

For anyone that's stuck, feel free to substitute () for all $ in the code below. Moving along now ...

// data Lazy = Lazy (Unit -> a)
const Lazy = t => ({
  memo: undefined,
  // runLazy :: Lazy a -> Unit -> a
  runLazy () {
    return this.memo === undefined
      // console.log call just for demonstration purposes; remove as you wish
      ? (this.memo = t(), console.log('computed:', this.memo), this.memo)
      : this.memo
  },
  // chain :: Lazy a -> (a -> Lazy b) -> Lazy b
  chain (f) {
    return Lazy($ => f(this.runLazy()).runLazy())
  }
})

// Lazy.of :: a -> Lazy a
Lazy.of = x =>
  Lazy($ => x)
  
// repeat :: Int -> (a -> a) -> a -> Lazy a
const repeat = n => f => x =>
  n === 0
    ? Lazy.of(x)
    : Lazy.of(f(x)).chain(repeat (n-1) (f))

// m :: Lazy Number
const m = repeat (5) (x => x * 2) (1)

console.log('computations pending...')
// ...
console.log(m.runLazy()) // (1 * 2 * 2 * 2 * 2 * 2) => 32
console.log(m.runLazy()) // => 32

As for satisfying the other categories, here's some more method implementations for Lazy. I got hung up on the Monoid for empty, but maybe you or someone else has some ideas there !

I also saw that you derived chain from f => join(map(f)) which is perfectly fine too

Functor

// map :: Lazy a -> (a -> b) -> Lazy b
map (f) {
  return Lazy($ => f(this.runLazy()))
}

Applicative

// apply :: (a -> b) -> a -> b
const apply = f => x => f (x)

// ap :: Lazy (a -> b) -> Lazy a -> Lazy b
ap (m) {
  return Lazy($ => apply (this.runLazy()) (m.runLazy()))
}

Monad

// Lazy.of :: a -> Lazy a
Lazy.of = x =>
  Lazy($ => x)

// chain :: Lazy a -> (a -> Lazy b) -> Lazy b
chain (f) {
  return Lazy($ => f(this.runLazy()).runLazy())
}

// join :: Lazy (Lazy a) -> Lazy a
join () {
  return Lazy($ => this.runLazy().runLazy())
}

Monoid

// empty
empty () {
  // unsure on this one
}

// concat :: (Monoid a) => Lazy a -> Lazy a -> Lazy a
concat (m) {
  return Lazy($ => this.runLazy().concat(m.runLazy()))
}

---

open exploration

This topic is very fun for me so I'm happy to discuss anything I've written about here or any other comments about the ideas presented in this question/answer. Let's have more fun!