0

Haskell is one of the few non-strict languages out there.

In his paper Why Functional Programming Matters, John Hughes uses (memoized) lazy evaluation (as well as higher-order functions) to implement a couple of nice algorithms where he is able to separate:

  • how data is generated.
  • how this data might be manipulated.
  • how finally the resulting data might be consumed.

He shows two examples:

  1. Using an infinite stream to generate ever-increasing approximations of interesting numerical values (like a square root, a derivative or an integral)
  2. Using an infinite multi-way tree to explore possible future positions of a game board.

In my own work in a wide plethora of languages, I sometimes have seen lazyness used as well, but almost always it has been in one of these two contexts: Either a linear (finite or infinite) stream, or a multi-way tree.

Are there any other data structures whose consumption is advantageous if done in a lazy fashion?

Improve this question
2

1 Answer 1

Reset to default
3

Some other situations that jump to mind:

  • Iterative processes that need to use the results of some earlier values but not others (which provides for simple ways of efficiently implementing processes like the Fibonacci sequence, or the Collatz conjecture)
  • Returning multiple results from a function (e.g. in a tuple or a record) where the caller may only require one of the values calculated without wasting effort on calculating the others
  • Providing a simple way to implement streaming I/O, e.g. returning a lazy list of lines from a file, like Haskell's hGetContents (note that due to the way Haskell is implemented, this can cause problems where files never get closed, so in Haskell it should only be used with care, but in principle the method is extremely helpful1.
  • Implementing processes which produce and consume streams of data incrementally -- this doesn't need any complex support, unlike languages like Java where streams require a lot of infrastructure, or Python where they need a special language feature (generator functions): a function can simply return a list and it can be consumed directly1.
  • One from a project I'm working on sporadically: elaborating the states of a finite state machine only when they are used (a key requirement for efficient implementation of the ALL(*) parsing algorithm)2.

1. while these are cases where streams are being used, I think they are different enough from the example in the question that should be considered a separate use of the facility.

2. this produces a DAG, which is somewhat tree-like, but again I consider the application far-enough removed that it's worth mentioning.

Improve this answer

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.