Is there a good strategy to make a function a productive function?

Question

_{EDIT: It seems what I was calling "lazy" here, isn't what "lazy" means. I am not sure what the proper term is. Some people are saying that the term I am looking for is "productive", but I can't find any definitions of that term in this context. What I want is a function that can work with infinite lists. I will change any "lazy" into "productive", using my best understanding of the term.}

The function

f a = a:(f (a-1))

generates an infinite list, in a productive way. Because of the a: being in front of every other evaluation.

This means you can do take 10 (f 0) and it's fine.

However, the function

h a = h (a ++ (map (-1) a))

isn't productive, and will never terminate. Since the a ++ is inside of another evaluation. Because of this, you cannot do head (h [0]), even though it is clear that it is 0.

Is there a general strategy I can apply to turn a non-productive function into a productive function?

Specifically, the problem I'm trying to solve is to make the following productive while lazily consuming its second argument:

binarily a [] = a
binarily a (b:bs) = binarily (a ++ map (b+) a) bs

Answer 1

h generates a growing sequence. On [0] for example:

[0] ++
[0, -1] ++
[0, -1, -1, -2] ++
[0, -1, -1, -2, -1, -2, -2, -3] ++ ...

Note that it shows the pattern [x, f x, f (f x), …]—at each step, you’re computing one more iteration of the function. That’s exactly what iterate :: (a -> a) -> a -> [a] is for, and the fold of ++s is exactly concat:

h = concat . iterate go
  where go x = x ++ map (subtract 1) x

Here’s one implementation of binarily using the same principle:

binarily a bs
  = concatMap fst
  . takeWhile (not . null . snd)
  $ iterate go (a, bs)
  where
  go (acc, b : bs) = (acc ++ map (b +) acc, bs)
  go x = x

We iterate the function and take elements from the stream While bs (snd) is not . null—if it’s infinite, then this just takes the whole stream—and then we concat the intermediate accumulators (map fst).

You’ll notice that if you didn’t have the takeWhile in there, you would end up with an infinitely repeating series of tuples where the snd is []. So what we’re doing is streaming until we hit a fixed point, i.e., turning recursion (fix) into streaming. :)

Answer 2

The 'general strategy' is to define your function so that it can compute a part of the result value before recursing.

In f, the topmost expression is an application of the (:) function, which is non-strict in its second argument. This means that it doesn't even need to evaluate f (a-1). if you don't need the remainder of the list.

In h, the first thing the function does is to recurse - i.e. it doesn't produce a "partial result".

Your binarily function actually is "lazy": it's non-strict in its first argument, so

take 10 $ binarily [1..] [1..5]

terminates.