(++) and operator (:) and lazy evaluation

Question

Chapter 8 RealWorldHaskell

globToRegex' (c:cs) = escape c ++ globToRegex' cs 

This function is not tail recursive and says that the answer is based on an unconfigured (lazy) Haskell evaluation strategy. A simple definition of the operator (++) is as follows and it is not tail recursive.

 (++) :: [a] -> [a] -> [a] (x:xs) ++ ys = x : (xs ++ ys) [] ++ ys = ys 

In a strict language, if we evaluate "foo" ++ "bar" , the entire list is built and then returned. A lax assessment postpones most of the work until it is needed.

If we require the expression element "foo" ++ "bar" , then the first function definition template will match, and we will return the expression x : (xs ++ ys) . Since the constructor (:) not strict, the evaluation of xs ++ ys may be delayed: we generate more result elements to whatever degree they are needed. When we generate more results, we will no longer use x , so the garbage collector can return it. Since we generate result elements on demand and do not occupy the parts that we are finished with, the compiler can evaluate our code in a constant space .

(Emphasis added.)

The explanation in bold above is significant for Haskell, but

• How can we understand this?
• What happens in the base?
• " x:(xs ++ ys) will change in constant space", how? It seems that tail recursion!

Answer 1

Remember that "foo" is just syntactic sugar for 'f':'o':'o':[] .

That is, String is just an alias for [Char] , which is just a linked list of characters.

When client code consumes a linked list, it decomposes it back into the head and tail (for example, x:xs ), does something with the head (if desired), and then recurses for the tail.

When your code creates a linked list, due to a lazy evaluation, all it needs to do is return thunk or promise that it will return the linked list when asked. When the head is dereferenced, it is provided on demand, and the tail remains as a promise for the rest of the list.

It should be easy to see that until the list is copied or otherwise saved, each thunk will be used once and then discarded, so that the total storage space is constant.

Many strict languages ​​set up a mechanism (often called a generator) for creating the same kind of lazy list, but with a lazy rating, such functions appear “for free” as part of the language - in fact, all Haskell lists are generators!

Answer 2

Relying on lazy evaluations rather than tail recursion is a Haskell characteristic compared to other FP languages. These two functions play a role in terms of limiting memory usage; which is a suitable mechanism depends on the data received.

If your output can be consumed gradually, then you should prefer to use a lazy estimate, since the output will be generated only as needed, thus limiting the consumption of the heap. If you readily construct the output, you refuse to use the heap, but you can at least save the stack by getting tail recursiveness.

If your output cannot be consumed gradually - perhaps you are calculating Int - then laziness can leave you with an unwanted bunch of blood clots whose rating will hit your stack. In this case, a strict accumulator and tail recursion are required.

So, if you want you to lose a bunch by creating a big data structure. If you are lazy, you can defer simplification (for example, decreasing 1 + 1 to 2 ) to the heap, in order to eventually unload your stack when paying with piper.

To play with both sides of the coin, foldl' and foldr .

Answer 3

The tail recursion will maintain the stack constant, but in strict language the heap will grow when calculating x : (xs ++ ys) . In Haskell, since it is not strict, x will be freed before the next value is computed (if the caller did not use the x reference unnecessarily), so the heap will also be constant.