有效地将函数应用于所有对

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)) 没有未装箱的实例。在其他情况下，我已经能够使用 Data.Vector.Unboxed.Deriving 创建新的未装箱实例，但我不确定在这种情况下是否会如此容易（将其转换为元组对，其中第一个元素是所有串联的内部向量第二个是向量的长度，知道如何解包吗？）

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

上面的实现是否有意义，或者是否有一些快速的库函数魔术等可以更容易地做到这一点？
如果是这样，是否有比上面草图更好的方法来制作未装箱的向量向量？

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

Answer 1

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

原则上可以通过仅存储嵌套向量的扁平形式加上额外的索引数组（每个子向量开始的位置）来定义该实例。 I once briefly gave this a try; it actually seems somewhat promising as far as immutable vectors are concerned, but a G.Vector 实例也需要一个可变的实现，这对于这种方法来说是没有希望的（因为任何改变一个子向量中元素数量的突变都需要将它后面的所有东西都移动）。

通常，这是不值得的，因为如果单个元素向量不是很小，那么装箱它们的开销就无关紧要了，即通常使用 B.Vector (U.Vector b).[=16 是有意义的=]

然而，对于您的应用程序，我根本不会这样做——没有必要将上面的元素选择包装在一个三角形数组中。（这样做对性能来说真的很糟糕，因为它使算法占用 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的nested-loops imperative implementation基本一样：

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

据我所知，我没有发现此实现有任何性能问题。

为简单起见，非多态。

有效地将函数应用于所有对

Apply function to all pairs efficiently

haskell

vector

fold