是否有一个好的策略来使一个功能成为一种生产性功能？ [英] Is there a good strategy to make a function a productive function?

问题描述

_{编辑：看起来我在这里叫懒，不是什么懒的意思。我不确定什么是合适的名词。有些人说我所寻找的术语是富有成效的，但在这方面我找不到这个术语的任何定义。我想要的是一个可以使用无限列表的函数。我将使用我对术语的最佳理解将任何懒惰改变为生产性。}

函数

  fa = a：（f（a-1））
  

以高效的方式生成无限列表。因为 a：在所有其他评估之前。

这意味着您可以做取10（f 0），没关系。

然而，函数

  ha = h（a ++（map（-1）a））
  

没有生产力，并且永远不会终止。由于 a ++ 在另一个评估中。
正因为如此，你不能做 head（h [0]），即使它清楚地表明它是0。

是否可以应用一种通用策略将非生产性功能转换为生产性功能？

具体来说，我试图解决的问题解决的办法是在懒洋洋地消费第二个参数时提高生产率：

  binarily a [] = a 
二进制a（b：bs）= binarily（a ++ map（b +）a）bs 
  

解决方案

h 生成一个增长的序列。在 [0] 例如：

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

请注意，它显示模式 [x，fx，f（fx），...] - 在每一步中，您将计算该函数的一次迭代。这正是 iterate ::（a - > a） - > a - > [a] 是for，并且 ++ s的折叠正好是 concat ：

  h = concat。 iterate go 
 where x = x ++ map（subtract 1）x 
  

这是一个 binarily 使用相同的原则：

  binarily a bs 
 = concatMap fst 
。 takeWhile（not。null。snd）
 $ iterate go（a，bs）
其中
 go（acc，b：bs）=（acc ++ map（b +）acc，bs ）
 go x = x 
  

我们 iterate 函数和从流中取元素 while bs （ snd ）不是。 null - 如果它是无限的，那么这只需要整个流 - 然后我们 concat 中间累加器（ map fst ）。





您会注意到，如果您没有 takeWhile 在那里，你最终会得到无限重复的一系列元组，其中 snd 是 [] 。因此，我们正在做的是直到我们遇到一个固定点，即将递归（ fix ）转换为流。 ：）

_{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

解决方案

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. :)

这篇关于是否有一个好的策略来使一个功能成为一种生产性功能？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！