有效地将功能应用于所有对

Question

我需要一个二阶函数pairApply，它将二进制函数f应用于列表式结构的所有唯一对，然后以某种方式组合它们。示例/草图：

pairApply (+) f [a, b, c] = f a b + f a c + f b c

一些研究让我相信Data.Vector.Unboxed可能会有很好的表现（我还需要快速访问特定元素）; Statistics.Sample也是必要的，它可以派上用场。

考虑到这一点，我有以下几乎编译：

import qualified Data.Vector.Unboxed as U      

pairElement :: (U.Unbox a, U.Unbox b)    
            => (U.Vector a)                    
            -> (a -> a -> b)                   
            -> Int                             
            -> a                               
            -> (U.Vector b)                    
pairElement v f idx el =
  U.map (f el) $ U.drop (idx + 1) v            

pairUp :: (U.Unbox a, U.Unbox b)   
       => (a -> a -> b)                        
       -> (U.Vector a)                         
       -> (U.Vector (U.Vector b))
pairUp f v = U.imap (pairElement v f) v 

pairApply :: (U.Unbox a, U.Unbox b)
          => (b -> b -> b)                     
          -> b                                 
          -> (a -> a -> b)                     
          -> (U.Vector a)                      
          -> b
pairApply combine neutral f v =
  folder $ U.map folder (pairUp f v) where
  folder = U.foldl combine neutral

这不编译的原因是没有U.Vector (U.Vector a))的Unboxed实例。我已经能够在其他情况下使用Data.Vector.Unboxed.Deriving创建新的未装箱实例，但我不确定在这种情况下它会如此简单（将其转换为元组对，其中第一个元素是所有内部向量连接而第二个是向量的长度，知道如何解压缩？）

我的问题可以分为两部分：

• 上面的实现是否有意义，或者是否有一些快速的库函数魔法等可以做得更容易？
• 如果是这样，是否有更好的方法来制作一个未装箱的矢量矢量而不是上面描绘的矢量？

请注意，我知道foldl可能不是最佳选择;一旦我完成了实施，我计划用几个不同的折叠进行基准测试。

Answer 1

没有办法为Unbox (U.Vector b)定义经典实例，因为这需要预先分配一个存储区，其中每个元素（即每个子向量！）具有相同的固定空间量。但总的来说，它们中的每一个都可能是任意大的，所以根本不可行。

原则上可以通过仅存储嵌套向量的展平形式以及额外的索引数组（每个子向量开始的位置）来定义该实例。 I once briefly gave this a try;就可变向量而言，它实际上似乎有点有希望，但是G.Vector实例也需要一个可变实现，这对于这种方法是没有希望的（因为任何改变一个子向量中元素数量的突变都需要移动它背后的一切） 。

通常，它只是不值得，因为如果单个元素向量不是很小，装箱它们的开销将无关紧要，即通常使用B.Vector (U.Vector b)是有意义的。

然而，对于您的应用程序，我根本不会这样做 - 没有必要将上层元素选项包装在单个三角形数组中。 （并且这样做会非常糟糕，因为它会使算法占用O（n²）内存而不是O（n），这就是所需要的。）

我会做以下事情：

pairApply combine neutral f v
 = U.ifoldl' (\acc i p -> U.foldl' (\acc' q -> combine acc' $ f p q)
                                   acc
                                   (U.drop (i+1) v) )
             neutral v

这几乎与明显的嵌套循环命令式实现相对应

pairApply(combine, b, f, v):
    for(i in 0..length(v)-1):
        for(j in i+1..length(v)-1):
            b = combine(b, f(v[i], v[j]);
    return b;

Answer 2

我的答案与leftaroundabout的嵌套循环命令式实现基本相同：

pairApply :: (Int -> Int -> Int) -> Vector Int -> Int
pairApply f v = foldl' (+) 0 [f (v ! i) (v ! j) | i <- [0..(n-1)], j <- [(i+1)..(n-1)]]
 where n = length v

据我所知，我认为这个实现没有任何性能问题。

非简单的非多态性。