>lazy evaluation is one of those features where i have absolutely no idea what benefit it actually provides
Good question.
Let's say you have a program like this little python example:
inputs = [raw_read() for i in range(1000)] # Read numbers from command line
numbers = map(int, inputs) # Turn them into integers
for num in numbers: # Check for 42
if num == 42:
return true
return false # It's not there
If you use lazy evaluation, each item in the "map" object will only be calculated as needed. So if the first item in the "inputs" list is "42", it will only do a single string-to-integer conversion.
If you use greedy evaluation, it will map all strings to integers at once, which might be wasteful.
There are other benefits as well; this is the most obvious.
Lazy evaluation gets you all that, with no extra code, all the time.
Imagine writing that iterator stuff for every single applicable thing in the entire program. There are also other places where lazy evaluation is useful and you can't use iterators, like a function that will only use a portion of its arguments depending on some condition.
This is nothing too interesting, but now let's say you want to write a function to find the minimum value of a list
In Python, this would probably be done like this:
def min_list(lst):
current_minimum = lst[0]
for e in lst[1:]:
if e < current_minimum:
current_minimum = e
return current_minimum
However, in Haskell, a very similar procedure can be defined like this:
minimum xs = head (quicksort xs)
(head returns the first element of a list)
Now, if have the slightest care for efficiency, you would never, ever write a function like this in a strict language.
However, in Haskell, minimum [5,2,7,1,3] would be evaluated like this:
> minimum [5,2,7,1,3]
> head (quicksort [5,2,7,1,3])
Now, head 'demands' one element from quicksort, so quicksort would start getting evaluated
> head (lesser ++ ...) [p = 5]
(++) is nonstrict, and only evaluates the elements you really need. Since right now only one element is demanded, we
can expect that nothing to the right of (++) would be evaluated
> head ((quicksort (filter (<5) [2,7,1,3]) ) ++ ...)
Now filter is also lazy, and it will only evaluate elements as needed. Right now, only one element is demanded by
quicksort(notice the (p:xs) in the definition. quicksort only cares about the 'p' right now)
Now, quicksort demands another element from filter (<2) ..., so filter (<5) runs until it finds the first element that
is also (<2)
> head ((quicksort (1:(filter (<2) (filter (<5) [3] ++ ...))
) ++ ...) ++ ...)
Filter will run through the entire list, comparing each element to 5,2 and 1 in order, and find nothing, returning [], which will hit the base case for quicksort []= []
> head ( [] ++ [1] ++ ...)
Simplifying to
> head ([1] ++ ...)
(++) has enough evaluated elements to give '1' to head, which finally returns
> 1
Notice that we passed through the list only once, just like in the python, in contrast to running an entire quicksort. While this is not as efficient as the python version as it keeps a few unnessary elements in memory, and compares elements to all previously found minimums, it is much more efficient than evaluating quicksort, and is pretty damn cool. With some GHC magic, the memory usage is also reduced somewhat.
I personally believe that the expressiveness gained through this procedure(we wrote quicksort and gained minimum for free!) offsets the loss in efficiency.
|| and && operators in C-like languages are "short-circuited", i.e. (true || predicate) just returns (true) without evaluating (predicate). This is a form of lazy evaluation.
Seems very close in implementation to RxCPP for push based streams and IxCPP for pull based, which has been created by Microsoft and now controlled by Microsoft Open Technologies. This library though does not require C++14 and is being actively developed: https://github.com/Reactive-Extensions/RxCPP
@wwwwwwwwww you have been hell-banned and I dont see anything particularly offensive in your immediate comment history.
> is there any reason to add lazy evaluation to c++ [...]
I think you are suffering from a misapprehension. Nothing is being added to C++ the language. This is just an implementation of lazy streams in C++14. Think of it as an optional 3rd party library.
> lazy evaluation is one of those features where i have absolutely no idea what benefit it actually provides
Let me give you two examples. First try and solve this problem in your favorite language. Produce a sequence of k numbers that are multiples of 2,3 and 5 only, but produce them in sorted order. Yes of course this is contrived, but it will give you and idea of the conveniences that laziness can give you. [sorry, I gave away the important spoiler]
Second example say you want to compute
(x + y)*z - w
where each of them are objects representing long vectors. You also want to keep the code readable and close to the mathematical notation of the domain. Naive way to do it will create lots of temporaries and unnecessary loops. Every binary operation is going to create a temporary (and entail a loop). But if you have laziness you just need one loop.
[EDIT: If one has laziness one need not instantiate the actual vector (x+y). One can return an object that only represents the operation. So one can keep building on the parse tree and finally when the result is actually used somewhere do you evaluate the expression encoded in the parse tree. Now since you have the entire expression tree you can evaluate it in just one loop. If you are curious you can search for deforestation and expression templates. You can of course do the same thing even if the language does not support laziness, but laziness is the key enabler here, if the language does not support it, _you_ have to implement it].
Without this features it is pretty much impossible to approach Fortran like speeds and expressiveness in array operations in C++.
A reason why basic Numpy is slow is because is that written naively it creates all these temporaries. There are a few ways to avoid it. Numexpr uses laziness (and tiling). You could also use the 'out' feature of Numpy functions creatively.
So in short, laziness has a lot of practical value, and I am not even bringing up aspects of purity etc. I had to roll something on my own for these needs. Would have been happier if there were such libraries available. [Ok full disclosure, I would have likely rolled my own anyway to understand how it works] There are a few libraries that do these things or help a lot in building these things. Some of the are Spirit and Fusion. Although I am conflating two different topics (i) fusion/deforestation and (ii) laziness, but they are related enough.
@dang thanks for the clarification, wwwwwwww's comment was indeed showing up as dead on this thread. wwwwwwww must have deleted his comment because at that time there was only one.
where each of them are long vectors but want to keep the look of the code readable and explicit. Naive way to do it will create lots of temporaries and unnecessary loops. Every binary operation is going to create a temporary (and entail a loop). But if you have laziness you just need one loop.
Can you elaborate on this? Why can laziness provide better code here?
If each of the four variables is a vector, naively you might do (x + y) first, producing a new vector. Then you would multiply by z, producing a second new vector. Finally, subtract w, producing a third new vector. You have now iterated over the length of the vectors three times, and allocated three new vectors (two of which are no longer needed).
A better way to do all that would be to allocate a single result vector and populate it with the full computed expression for each element. This can be much faster for large vectors. Python's numexpr (among others) is designed to do just this.
Apologies, I did not see your question in time. Note that valarray is just a standard API, an implementer can write it as they wish. That said, these kinds of optimizations were indeed a motivation for creating valarray. Standard libraries do use exactly these optimizations in valarray (with some SIMD vectorization thrown in as well). You can also take a look at pixelglow's implementation, he has a comment downstream. It is pity that no one in the standards committee took ownership of valarray and it was included in a semi broken state.
Thanks for the reminder. I had come across cppitertools before and wanted to explore it and then totally forgot. Not sure why you got downvoted here, have tried to compensate.
BTW your handle rung a bell. I was wracking my brain to remember where have I heard of it before, then finally, oh yes MacSTL. It really deserves more love. Have not used it, but sure browsed the code.
lazy evaluation is one of those features where i have absolutely no idea what benefit it actually provides