高效迭代Haskell中多个数组/列表的前缀

给定三个已排序的数组，我需要m从它们中挑选出总和最小的元素。一个额外的限制是它们中的至少r一个必须来自前两个。这是我的尝试：

solve :: [Int]->[Int]->[Int]->Int->Int->Int
solve xs ys zs m r = mini [ (xs'!!i) + (ys'!!j) + (zs'!!k) |
  i <- [max' (len ys - m) .. len xs],
  j <- [max' (r-i) .. len ys],
  k <- [max' (m-i-j) .. len zs],
  i+j+k == m,  
  i+j>=r
  ] where
      mini ws = if null ws then (-1) else minimum ws
      [xs',ys',zs'] = map (scanl (+) 0) [xs, ys, zs]
      max' x = max x 0
      len ws = min (length ws) m

（由于数组已排序，我正在考虑它们i,j,k满足约束的长度前缀，并使用 将它们相加scanl。）

我担心这是否太低效，因为!!. 另外，我想知道是否scanl有帮助。这种担忧是否有效，如果有效，我们该如何解决？

回答

merge :: Ord a => [a] -> [a] -> [a]
merge [] ys = ys
merge xs [] = xs
merge xs@(x:xs') ys@(y:ys')
  | x <= y = x : merge xs' ys
  | otherwise = y : merge xs ys'

solve :: (Ord a, Num a) => [a] -> [a] -> [a] -> Int -> Int -> a
solve xs ys zs m r = sum . take m  $ prefix ++ rest
  where
    (prefix, suffix) = splitAt r (merge xs ys)
    rest = merge suffix zs