Geek Answers Handbook

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

EDIT: It seems that I call "lazy" here, not what lazy means. I am not sure what the correct term is. Some people say that the term I am looking for is “productive,” but I cannot find any definitions of the term in this context. What I want is a function that can work with infinite lists. I will change any “lazy” to “productive” using my best understanding of the term.

Function

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

generates an endless list in a productive way. Due to what a:is in front of every other assessment.

This means that you can do it take 10 (f 0)and it’s normal.

However function

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

is not productive and will never stop. Because it a ++is inside another assessment. Because of this, you cannot do it head (h [0]), although it is clear that it is 0.

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

In particular, the problem I'm trying to solve is to make the following productive by lazily consuming my second argument:

binarily a [] = a
binarily a (b:bs) = binarily (a ++ map (b+) a) bs
+4
source share
4 answers

hgenerates a growing sequence. For [0]example:

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

Note that it shows a pattern [x, f x, f (f x), …]- at each step, you calculate another iteration of the function. That which means iterate :: (a -> a) -> a -> [a]a fold ++is equal to concat:

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

binarily :

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 take While bs (snd) not . null - , , concat (map fst).

, takeWhile, , snd - []. , , , , (fix) .:)

+6

" " , , .

f (:), . , f (a-1). .

h , , - " ".

binarily "": ,

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

.

+2

, , , ""...

head (h [10]) . : h [10] => h [10,9] => h [10,9,9,8] => h [10,9,9,8,9,8,8,7] => .... , , 10, . , , f 10 => [10,9,8,7,....

,

binarily a [] = a
binarily a (b:bs) = binarily (a ++ map (b+) a) bs
{-  try it out with [b1,b2,b3,b4] :
a                          b1     the arguments received;
a1@(a  ++ (map (b1+) a))   b2     if we've already produced a, we just need 
                                       to produce  (map (b1+) a)  next
a2@(a1 ++ (map (b2+) a1))  b3     if we've already produced a1, we just need 
                                       to produce  (map (b2+) a1)  next
a3@(a2 ++ (map (b3+) a2))  b4     ai@... name the interim values
a4@(a3 ++ (map (b4+) a3))  []     a4 is returned  -}


import Data.List (mapAccumL)

-- mapAccumL :: (acc -> x -> (acc, y)) -> acc -> [x] -> (acc, [y])

binarily a bs = (last . snd) (mapAccumL g a bs)
 where
   g a b = let anew = a ++ map (b+) a
           in (anew, anew)             -- (next_accum, part_result)

mapAccumL . :: [y] ( snd ) , y, , x :: [x] ( (b:bs)). , fst , .

, :

binarily a bs = a ++ (concat . snd) (mapAccumL g a bs)
 where
   g a b = let                     -- for each b in bs:
               res = map (b+) a    --    this part of the result
               anew = a ++ res     --    next accumulator value
           in (anew, res)
+2

, , "" / binarily:

binarily a l = a ++ binRest a l

binRest a [] = []
binRest a (b:bs) = a' ++ binRest (a ++ a') bs
  where
    a' = map (b+) a

EDIT: - . , binarily , binarily a (b1:b2:b3:...):

a
a ++ map (b1+) a
a ++ map (b1+) a ++ map (b2+) (a ++ map (b1+) a)
a ++ map (b1+) a ++ map (b2+) (a ++ map (b1+) a) ++ map (b3+) (a ++ map (b1+) a ++ map (b2+) (a ++ map (b1+) a))

, a ++, map (b1+) , concat $ iterate ... a, @JonPurdy, , . , bs, scanl iterate.

, , : , , , , , concat $ scanl ... .

It turns out, in fact, that the part produced at the very first step does not correspond to the regular pattern of all the others.

Thus, I divided into two functions: first binarily, which processes what needs to be done in the first step, and then proceeds to binRestfor all other steps.

Secondly, binRestwhich takes as a first argument everything that has been created so far, and uses it to calculate what will be done at this stage, and then recursively.

+2
source

More articles:


All Articles