Lazy evaluation

Questions
1

Hi

as a follow-up to An endless list makes the REPL work for a long time and this is intentional (updated title), I was wondering if there is a way to make some computations explicitly lazy.

There are algorithms that can be expressed much more directly when using “infinite” structures. As a second example, a find follow by a map over a large list can become faster if the list the computation stops at the first element that matches the predicate.

Is there way to express such semantics in DAML?

Regards,
Alex

1 Like
2

There is no opt-in or explicit laziness or list fusion. So you have to manually merge the map with the find. In this case, the findOptional function in the standard library makes that relatively easy:

find p (map f xs)

becomes

find (\x -> let y = f x in if p y then Some y else None) xs
4 Likes
3

I’d also note that, while generalized laziness à la Haskell needs to be a language feature, building lazy lists as a library in an eager language is not difficult. If you really need to work with lazy lists a lot, you could build that yourself. Here is a minimal definition for find p (map f xs):


module Main where

import Daml.Script

data LazyList a = Nil | Cons {head: a, tail: () -> LazyList a}

(...) : a -> (() -> LazyList a) -> LazyList a
a ... f = Cons a f

lazy_map : (a -> b) -> LazyList a -> LazyList b
lazy_map f Nil = Nil
lazy_map f Cons{head, tail} = f head ... \() -> lazy_map f (tail ())

lazy_find : (a -> Bool) -> LazyList a -> Optional a
lazy_find p Nil = None
lazy_find p Cons{head, tail} = if p head then Some head else lazy_find p (tail ())

ints : LazyList Int
ints = 1 ... \() -> lazy_map (+1) ints

setup : Script ()
setup = script do
  debug $ lazy_find (> 5) ints
  return ()

There’s obviously going to be a performance overhead, so you should only do this if you really plan to have very long lists. This also doesn’t serialize (functions are not serializable), so you can’t put that into a template, but you can trivially convert back and forth:

to_lazy : [a] -> LazyList a
to_lazy [] = Nil
to_lazy (a::as) = a ... \() -> to_lazy as

from_lazy : LazyList a -> [a]
from_lazy Nil = []
from_lazy Cons{head, tail} = head :: from_lazy (tail ())

and lazy_find p (lazy_map f (to_lazy xs)) would give you the laziness you want here (i.e. f would only be called as many times as it takes to find the first match).

4 Likes