是否可以将呈现的案例优化为一个循环？

Question

假设我有两个函数f :: [a] -> b和g :: [a] -> c.我有以下两个问题:

1. 如果我执行(f &&& g) xs,其中xs :: [a],如果都f和g涉及循环,有可能是编译器这两个循环优化成一个？(请注意,我不是在问一些特定的Haskell编译器是否实现了这一点.我想知道这样的事情是否可行.)

2. 类型类中的traverse函数可以Traverse帮助我进行这样的优化,包括以下几行:

   traverse (someCombinator f g) xs
   

Answer 1

理论上可以优化此代码,但非常非常困难,因为f并且g可能会消耗不同数量的输入列表.只有当它们消耗相同的量,或者g总是消耗更多的列表f(反之亦然)时,才有可能执行优化.暂停问题可防止编译器在复杂代码中检测到此类情况.

仅在简单的情况下,例如,在内部使用f和内部g使用的情况下,foldr可以在没有进一步内省的情况下执行简单的优化.

这个traverse功能在这里没有帮助,因为没有合理的实现方式someCombinator(你怎么想把多个调用的as变成一个[a]没有严重黑客攻击？然后你回到你开始的地方).

你唯一的选择就是让f和g成文件夹,使他们有签名f :: a -> b -> b和g :: a -> c -> c,这意味着价值b和c可以逐步计算.然后\ a -> f a *** g a,您可以使用一个文件夹,您可以在常规(右边 - 在这种情况下)折叠使用.