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

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

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

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

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

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

Answer 1

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

它可能在原则上有可能通过仅存储嵌套矢量的展平形式加索引的一个额外的阵列(其中每个子向量开始)来定义该实例.我曾经简单地试过这个 ; 就可变向量而言,它实际上似乎有点有希望,但是一个G.Vector实例也需要一个可变的实现,这对于这种方法是没有希望的(因为任何改变一个子向量中的元素数量的突变都需要移动它背后的一切).

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

然而,对于您的应用程序,我根本不会这样做 - 没有必要将上层元素选项包装在单个三角形数组中.(那将是非常糟糕的表现要做到这一点,因为它使算法取Ø(ñ ²)内存,而不是Ø(ñ),这是所有的需要.)

我会做以下事情:

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;